关于java:ArrayList剖析

大家天天在用 List，ArrayList 一般来讲应该是程序员用的最多的汇合类了。

咱们明天钻研一下 ArrayList。

总体来讲，从底层数据结构或者源码的角度看，List 比 Map 或者 Set 要简略。

底层数据结构

ArryList 其实就是可变长数组。

初始化的时候，能够指定容量，不指定容量的话，ArrayList 被初始化为空数组，首次存入数据的时候才进行容量初始化，初始化最小容量为 10。

ArrayList 的容量管制

每次存入数据到 ArrayList 的时候，首先查看容量：

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

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

如果 ArrayList 容量不能满足本次数据存储的要求的话，调用 grow 办法扩容：

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

grow 办法首先查看原容量扩容 1.5 倍是否能满足要求，能满足则扩容到原来的 1.5 倍，否则扩容到能满足数据存入要求的容量。

扩容后调用 Arrays.copyOf(elementData, newCapacity) 把旧的数据 copy 到扩容后的新数组。Arrays.copyof 办法其实也是调用 System.arraycopy 办法实现 copy。

数据存入

调用 add（E e）办法在 ArrayList 尾部追加数据。
调用 addAll(Collection<? extends E> c) 在 ArrayList 尾部追加汇合 c 中的所有数据。

ArrayList 反对追加数据到其指定地位（通过调用办法 add(int index, E element)），底层通过调用 System.arraycopy 办法实现。

钻研 ArrayList 源码会发现其中大量应用 System.arraycopy 办法，所以，尽管 ArrayList 其实就是数组操作，然而性能也不至于太差。

获取数据

应用 ArrayList 的时候咱们个别会有两种获取数据的需要，一种就是获取指定地位的数据，通过 get(int index) 办法获取，因为 ArrayList 其实就是数组，所以，获取指定地位的数据效率十分高，工夫复杂度为 O(1)。

另外一种就是判断是否蕴含某一数据，调用 contains(Object o) 办法：

public boolean contains(Object o) {return indexOf(o) >= 0;
    }


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

其实猜都能猜到他必须要遍历数组了，所以效率不会太高。

其余

读源码的目标除了从底层彻底理解其工作原理之外，还有一个重要的目标就是学习最最 NB 的 JAVA 程序员的编码思维和习惯。

比方开释内存：

   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
    }

比方代码重用：

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

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

retainAll 是只保留参数汇合中的数据，removeAll 则正好相同，移除参数汇合中的数据，两个办法目标正好相同，则通过调用 batchRemove、传递 complement 为 true 或 false 达到目标。

值得每个尤其是老手程序员认真学习。

晚安！