java_1.8 ArrayList 源代码解析

1. ArrayList默认值在1.8不在像之前的那样直接开10个空间

 java 1.6

 // ArrayList带容量大小的构造函数。
 16     public ArrayList(int initialCapacity) {
 17         super();
 18         if (initialCapacity < 0)
 19             throw new IllegalArgumentException("Illegal Capacity: "+
 20                                                initialCapacity);
 21         // 新建一个数组
 22         this.elementData = new Object[initialCapacity];
 23     }
 24 
 25     // ArrayList构造函数。默认容量是10。
 26     public ArrayList() {
 27         this(10);
 28     }

java 1.8

 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }


 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};


 //这段代码来自DenseIntMapImpl类，目前不知道该类的作用是什么
 private void extend( int index )
    {
        if (index >= list.size()) {
            list.ensureCapacity( index + 1 ) ;
            int max = list.size() ;
            while (max++ <= index)
                list.add( null ) ;
        }
    }

  
 public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

private void ensureExplicitCapacity(int minCapacity) {
         modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

 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);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
        //如果是用户指定大小超限了那么按Int最大值，否则是int最大值-8，目前不知道为什么-8
    }

2. indexOf 竟然连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.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

3. 深拷贝

 public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

4.获取元素

//arraylist底层都是使用这个函数来访问指定下标的值，问题是default修饰无法在包外访问
E elementData(int index) {
        return (E) elementData[index];
    }


 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }


 public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

5.removeAll和retainAll写的真的牛

    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                //这个boolean和这个contains用的牛
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

6.后续研究一下System.arraycopy以及Arrays.copyOf 这两个经常出现在底层，研究一下这两个数组复制的底层源码