List和Set区别底层原理解析

表面上可能都知道，List可重复且有序，Set不可重复且无序，那怎么实现呢？

我们直接分析下ArrayList

ArrayList其实就是一个可扩容的动态数组，一般的数组是不可以扩容的，那么ArrayList其实就是个复制赋值的思路。
看源码有个点要注意：

transient Object[] elementData;

transient是可以被序列化，但是我们知道ArrayList是可以被序列化的，为什么呢？
在readObject中和writeObject重新赋值了数组元素，可以对其进行序列化，可以看到只有size>0才会被序列化，这就是这么设计的原因。

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

扩容的具体实现，右移一位相当于扩大50%

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

所以List就是基于数组递增实现的。

Set会稍微复杂一些，是基于hashSet和treeSet实现的。

hashSet就是对hashMap的包装
treeSet是基于treeMap的实现