集合–ArrayList

主要内容基于 JDK 1.8 下的特性，总结于《阿里面试问了ArrayList，都问了啥？》

先聊一聊基本概念：

底层是用数组实现
查询快，增删慢
不是线程安全，但是效率高

为什么遍历快？

论遍历要比 LinkedList 快，因为是用数组实现，内部内存连续，而 CPU 的局部性的机制会缓存连续的内存地址，大幅降低了读取内存的开销。

为什么线程不安全还要用？

因为日常开发中查询是用的最多的，不太会频繁的进行增删，如果增删频繁的话就用 LinkedList，如果想要线程安全的话那么就用 Vector ，这也是他们仨主要的区别。

ArrayList 的扩容机制

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

从源代码中就能很好看出，JDK1.8的扩容效率很高，因为采用了位运算右移 1 位，因为计算机中都是补码的二进制嘛，所以右移 1 位就相当于 / 2，那么这里就是 1.5 倍扩容，如果还是不够就按设置的最小容量扩容。

JDK 1.7 和 JDK 1.8 初始化的区别

ArrayList 在 1.7 以前初始化时会调用 this(10) 来直接初始化一个容量为 10 的数组，而在 1.7 及以后初始化时默认走了一个空数组，在第一次 add 后容量才会变成默认容量 10。

为什么增删慢呢？

阅读源码就可以知道，在指定下标处增加或者删除元素时，都是 copy 数组，无非是增加时是把 index 以后的数组复制到 index+1 的位置，而删除时就是直接把 index 后的数组复制到 index-1 的位置，直接覆盖掉，然后把最后置为 null。

ArrayList(int initialCapacity) 会不会初始化数组？

源码部分：

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

可以看到的确初始化了一个数组，但是 list 的 size 并没有初始化还是 0 ，所以当你 set( 5 ,1) （随便挑个值）的时候，它的第一行代码就是检查 index 下标和 size 的关系，这时就会报下标越界的异常

结论就是会初始化数组，但没有初始化 list

ArrayList 删除一定慢吗？

不一定，看删除的位置离末尾的距离，ArrayList 很适合作堆栈，pop、push 都不会涉及数据的移动，所以也不适合作队列，因为涉及的数据移动太多，但是数组适合做队列。

想要线程安全就使用 Vector（它的扩容机制是翻倍，并不是 1.5 倍），实现很简单就是把方法都加上 synchronized 关键字，或者也可以用 Collections.synchronizeList 来包装成线程安全的 list。