集合深度学习03—ArrayList核心源码

一、ArrayList实现类JDK1.7源码

1. 构造方法

调用无参构造器，调用本类带参构造器，初始值为10

transient：不可序列化。
Object类型的数组，所有 list 可以存任意类型，因为是Object，所有类的父类。
size：数组中的有效数据。

不就相当于 Object[ ] elementDates = new Objectp[10]
数组初始化，长度为10。

对应内存。
size为0是还没有 有效元素。

2. 添加元素

在当前有效位末尾加一个元素
有效位++

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5

指定位置添加元素

    public void add(int index, E element) {
    	// 范围检查
        rangeCheckForAdd(index);
        //自动扩容机制
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    
    private void rangeCheckForAdd(int index) {
    //只可以在 [ 0 , size ] 里选位置
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 放满了，装不下了，就得扩容了

新手小伙伴会问 list 怎么会放满呢？
ArrayList 底层是数组啊，数组有大小。只是自动扩容，不深究看不到。
LinkedList底层是链表，不会满

    public boolean add(E e) {
    	//自动扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5
6

内容保证能力
如果超出当前数组长度，就要扩容，并且把这个 minCapacity值 传入

1. newCapacity=oldCapacity+(oldCapacity>>1)
   右移，就是除 2
   所以新容量至少是原来的 1.5 倍
2. 如果新容量还没有传来的容量大，则用传来的容量
3. 如果新容量比int最大值-8还大

如果比int最大值还大，则用int最大值，否则用int最大值-8

4. 复制原数组元素到新数组
5. 老数组指向新数组

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     * 要分配的数组的最大大小。
     * 一些 VM 在数组中保留一些标题字。
     * 尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超过 VM 限制
     * 所以尝试分配小一点的
     */
   private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE:MAX_ARRAY_SIZE;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

二、ArrayList实现类JDK1.8源码

底层依旧是Object类型的数组
size依旧是有效长度

    transient Object[] elementData; // non-private to simplify nested class access

    private int size;
1
2
3

1.构造方法

JDK1.8数组初始化时为空数组，不再指定初始大小

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
1
2
3
4

2. 添加方法

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
1
2
3
4
5

确保内部容量

   private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }  
1
2
3

计算容量
如果是空数组，则取 当前容量 和 默认容量10 比较，取最大值

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static final int DEFAULT_CAPACITY = 10;
  
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
1
2
3
4
5
6
7
8
9

确保显示容量
如果计算出来的容量 比 当前实际容量大，就扩容

   private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
1
2
3
4
5
6

自动扩容

1. newCapacity=oldCapacity+(oldCapacity>>1)
   右移，就是除 2
   所以新容量至少是原来的 1.5 倍
2. 如果新容量还没有传来的容量大，则用传来的容量
3. 如果新容量比int最大值-8还大

如果比int最大值还大，则用int最大值，否则用int最大值-8

4. 复制原数组元素到新数组
5. 老数组指向新数组

    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);
    }
    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     * 要分配的数组的最大大小。
     * 一些 VM 在数组中保留一些标题字。
     * 尝试分配更大的数组可能会导致 OutOfMemoryError：请求的数组大小超过 VM 限制
     * 所以尝试分配小一点的
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

三、总结

JDK1.7时 底层是数组，在调用构造器的时候，数组长度初始化为10，扩容的时候为1.5倍。

JDK1.8时 底层还是数组，在调用构造器的时候，底层数组为 { }，空数组，在调用add方法后，底层数组才重新赋值为新数组，新数组的长度为10

好处是节省内存，在add后才创建长度为10的数组。