精华内容
下载资源
问答
  • ArrayList源码解析

    2020-05-24 11:14:23
    ArrayList源码解析

    来一道面试题:

    ArrayList<Integer> list = new ArrayList<>();
    list.add(5);
    list.add(4);
    list.add(3);
    list.add(2);
    list.add(1);
    list.remove(1);
    list.remove((Integer)2);

    list中,还剩下哪几个元素?

     

    带着这个问题,来看一下ArrayList的源码。

    ArrayList构造器总共有三种:

        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
    
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
    
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

    分别是无参构造器,设置初始化数组长度的构造器和可以设置初始化集合的构造器。

    一般使用的都是无参构造器,看一下无参构造器里面elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA分别是什么:

        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    
        transient Object[] elementData; // non-private to simplify nested class access

    DEFAULTCAPACITY_EMPTY_ELEMENTDATA是final类型的静态参数,使用static修饰,代表了如果创建多个ArrayList时,可以复用DEFAULTCAPACITY_EMPTY_ELEMENTDATA。值得注意的是,这里初始化时,elementData的初始大小是0。

    elementData就是一个普通的Object数组,它就是ArrayList的底层实现。

    继续看一下add方法:

        private int size;    
        private static final int DEFAULT_CAPACITY = 10;
    
        public boolean add(E e) {
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
        private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }

    ensureCapacityInternal是对数组进行扩容,保证当前的数组长度,装的下目前的数据。

    可以看到ensureCapacityInternal先判断elementData是否是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,如果是的话将取DEFAULT_CAPACITY和minCapacity的最大值作为数组的最小容量。size初始化时为0, 那么传入的形参minCapacity=1。DEFAULT_CAPACITY初始化为10,所以计算以后的minCapacity为10。

    再看ensureCapacityInternal函数,modCount记录的是ArrayList的修改次数,贯穿于整个ArrayList源码当中。然后将当前的数组长度与最小的可用容量作对比,如果数组长度不大于最小容量,就会使用grow函数对elementData进行扩容。

    grow里,oldCapacity记录了数组长度的原始值,大小是0。newCapacity是oldCapacity的1.5倍,这时也是0。也就是ArrayList每次进行扩容,都会将数组扩大1.5倍。这里形参minCapacity=10。会走进入到第一个判断条件里,将newCapacity赋值为10.

    最后使用Arrays.copyOf方法,对elementData进行复制和扩容。Arrays.copyOf方法底层使用c/c++实现,效率比java代码用for循环实现数组的复制要高很多,所以在遇到数组拷贝和扩容的时候,应当优先使用Arrays.copyOf方法。

    回到add函数里,ensureCapacityInternal对数组扩容后,保证了数组大小可以装的下新进来的数据,再将新数据放在数组第一个空闲位上,并返回true;

    为了回答文章开始的问题,还需要看一下remove函数,remove有两个重载的实现方法:

       public E remove(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    
            modCount++;
            E oldValue = (E) elementData[index];
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
    
    
        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
        private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }

    第一个remove方法接收int类型的指针,方法实现也很简单。第8、9行可以看出,若移除的元素不是最后一个元素,会将数组中移除元素位置后面的元素向前移动一位(即下面fastRemove函数的作用)。

    第二个remove方法接收Object类型的参数。若传入的对象为空,会移除当前数组中的null元素,并将后面的元素依次向前移动一位。若传入的对象非空,会查找数组中的元素是否与传入的Object相同,同样做fastRemove操作。

    看到这里,文章开头的问题已经有了答案。

    list.remove(1);
    list.remove((Integer)2);

    共调用了两次remove函数,第一个remove函数传入的类型是int类型,也就是按索引移除第2个元素(数组下标从0开始),第2个元素的值是4。第二个remove函数传入的Integer类型,是Object的子类型,会移除列表里值为2的元素。

    这样,列表里还剩下5,3,1三个元素。

     

     

     

     

    展开全文
  • ArrayList 源码解析

    2021-03-31 20:07:01
    ArrayList

    前提本文基于 JDK 1.8 分析,版本之间存在细节差异,但不影响大体思路。

    ArrayList

    前提预热

    学习这里两个函数的使用,因为在ArrayList中多次用到了。

    public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,int length);
    /*
    *参数:
    *   src:要复制的数组(源数组)
    *   srcPos:复制源数组的起始位置
    *   dest:目标数组
    *   destPos:目标数组的下标位置
    *   length:要复制的长度
    */
    
        public static int[] copyOf(int[] original, int newLength) {
            int[] copy = new int[newLength];
            System.arraycopy(original, 0, copy, 0,
                             Math.min(original.length, newLength));
            return copy;
        }
    
    类的申明
    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    

    线程不安全

    数组自能存储相同类型的元素;

    如果数组存对象,则存的是引用。

    标记性接口 标签

    RandomAcess 说明该类支持随机访问,数据底层基于数组实现。

    ​ 遍历方式: for 循环 否则:迭代器

    Cloneable 支持拷贝。

    ​ 直接使用 Object 中的clone方法为浅拷贝。且必须实现该接口。

    ​ 深拷贝 :

    ​ 浅拷贝:int 等基本类型有关。

    ​ 传值方式:

    ​ 拷贝的都是栈中的内容

    在这里插入图片描述

    java.io.Serializable 网络传输 写磁盘

    ​ serialVersionUID 类文件指纹。 写死就不会重新签名,因此不会导致文件反序列化失败。

    ​ 序列化 将对象写磁盘

    ​ 反序列化 反过来

    全局变量

    在这里插入图片描述

    private static final long serialVersionUID = 8683452581122892189L;
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//无参构造
    private static final Object[] EMPTY_ELEMENTDATA = {};//
    transient Object[] elementData; //实际存储元素的地方
    
    private int size;  // 实际元素个数
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//集合最大存储量,但实际并不是这样,只起到标记作用
    
    protected transient int modCount = 0; //当前集合被修改的次数
    

    transient 表示该属性不会被序列化

    构造器

    节省空间

     this.elementData = new Object[initialCapacity];
    

    在这里插入图片描述

       // 构造一个初始容量为10的空列表,见下面扩容机制的 add 方法 分析
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
           //构造一个具有指定初始容量的空列表。
        public ArrayList(int initialCapacity) {
            if (initialCapacity > 0) {//初始化参数 > 0, 直接 new 一个
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) {
                this.elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }
    
        public ArrayList(Collection<? extends E> c) {
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray可能(不正确)不返回Object
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);// Arrays 的 copyOf 函数
            } else {//elementData.length == 0
                //和 initialCapacity = 0 时,一个效果
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }
    

    为啥用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA ?

    可以起到节省空间,懒加载,同时还可以起到一定的标记作用。

    扩容机制
        public boolean add(E e) {
            //查看是否还有空余空间可以存储,如果没有就扩容
            //扩容后满足,数组原数组迁移; 扩容后溢出 - > OOM
            ensureCapacityInternal(size + 1);
            elementData[size++] = e;
            return true;
        }
    

    每次调用add()系列方法前都需要调用 ensureCapacityInternal(int minCapacity)

        // minCapacity = size + 1 作为参数传入
    	// private static final int DEFAULT_CAPACITY = 10;
    
    	private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
       	private static int calculateCapacity(Object[] elementData, int minCapacity) {
            //elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示经过无参构造后,还没有初次构件数组数组长度
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //DEFAULT_CAPACITY = 10, minCapacity = size + 1
                return Math.max(DEFAULT_CAPACITY, minCapacity);//返回较小的一个
            }
            //数组已经被构建了, 直接返回 size + 1
            return minCapacity;
        }
    
        //Explicit 精准
        private void ensureExplicitCapacity(int minCapacity) {
            //修改次数 + 1
            modCount++;
    
            // 判断 calculateCapacity() 的返回值 是否 > elementData.length(实际开辟空间长度)
            if (minCapacity - elementData.length > 0)//如果添加元素,则会没有地方存放,否则不进入
                //进行扩容,真实的去开辟,和确定是到底要扩容到多少
                grow(minCapacity);
        }
    
        //增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
        private void grow(int minCapacity) {
            // 拿到原来的实际长度
            int oldCapacity = elementData.length;
            // 创说中的扩容 1.5 倍的代码,将扩容后容量的理论值赋给 newCapacity
            int newCapacity = oldCapacity + (oldCapacity >> 1);// 0 + 0 / 2第一次并无起作用
    
            if (newCapacity - minCapacity < 0)
              //newCapacity < minCapacity (newCapacity 已近大于 Integer.MAX_VALUE,第一次扩容使用)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)//newCapacity > Integer.MAX_VALUE - 8
                //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
                newCapacity = hugeCapacity(minCapacity);//举步维艰的扩容,向Integer.MAX_VALUE迈进
            //扩容后转移数组,保证原先的数据
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
    
    	private static int hugeCapacity(int minCapacity) {
            //minCapacity = size + 1
            if (minCapacity < 0) // minCapacity 已经溢出了(size == Integer.MAX_VALUE)
                throw new OutOfMemoryError();
            //size + 1 >  MAX_ARRAY_SIZE  ----->    Integer.MAX_VALUE
            //size + 1 <= MAX_ARRAY_SIZE  ----->    MAX_ARRAY_SIZE
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }
    
    	o == null ? e == null, o.equals(e);
    	//为啥要判断 o 是否为 null
        public int indexOf(Object o) {
            if (o == null) {
                for (int i = 0; i < size; i++)
                    if (elementData[i]==null)
                        return i;
            } else {
                for (int i = 0; i < size; i++)
                    //if(o == null) 调用 o.equals(e) 抛出异常
                    if (o.equals(elementData[i]))
                        return i;
            }
            return -1;//没有找到 返回-1
        }
    
    删除函数
    指定索引
    	 public E remove(int index) {
                //检查 index 的下标是否合法 !(index < 0 || index >= this.size)
                rangeCheck(index);
                //检查是否该集合发生 (ArrayList.this.modCount != this.modCount)
                checkForComodification();
                //得到要删除的位置 (index) 数据
                E result = parent.remove(parentOffset + index);
                this.modCount = parent.modCount;
                //size -- ;
                this.size--;
                return result;
            }
    
    指定元素
        public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    
        private void fastRemove(int index) {//供 remove(Object o) 的形式
            /*
             * 专用的remove方法,跳过边界检查并且不返回已删除的值。不需要检查下标的原因就是再 Remove(Object o)中检查过了
             * 其余逻辑和 remove(int index) 一样
             */
    
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null;
        }
    
    删除指定索引范围
        protected void removeRange(int fromIndex, int toIndex) {
            modCount++;
            int numMoved = size - toIndex;//需要向左移动的数组项的数目
            System.arraycopy(elementData, toIndex, elementData, fromIndex,
                             numMoved);
            // help  GC
            int newSize = size - (toIndex-fromIndex);//计算删除的实际存储个数。
            for (int i = newSize; i < size; i++) {
                elementData[i] = null;
            }
            size = newSize;
        }
    
    清空
        public void clear() {//列表清空
            modCount++;
            // 为啥要依次遍历 ?   help  GC
            for (int i = 0; i < size; i++)
                elementData[i] = null;
            size = 0;
        }
    
    迭代器
        private class Itr implements Iterator<E> {
            int cursor;       // 下一个要返回的元素的索引,
            int lastRet = -1; // index of last element returned; -1 if no such
            
            int expectedModCount = modCount;//new  的时候初始化 很重要            					expectedModCount != modCount  说明 list 发生了改变
            
            Itr() {}//在 new 的时候被赋予 ‘0’值
            
            .......
            
           }
    
    获取下一个元素
           public E next() {
                //检查有没又发生改变, 改变了抛出异常
                checkForComodification();
                int i = cursor;
                if (i >= size)
                    throw new NoSuchElementException();
                Object[] elementData = ArrayList.this.elementData;//区别两个 elementData
                if (i >= elementData.length)
                    throw new ConcurrentModificationException();
                cursor = i + 1;
                return (E) elementData[lastRet = i];
            }
    
    删除当前元素
       public void remove() {
                // 如果 lastRet 小于 0 ,说明没有指向任何元素,抛出 IllegalStateException 异常
                if (lastRet < 0)
                    throw new IllegalStateException();
                // 校验是否数组发生了变化
                checkForComodification();
    
                try {
                    // 移除 lastRet 位置的元素
                    ArrayList.this.remove(lastRet);
                    // cursor 指向 lastRet 位置,因为被移了,所以需要后退下