JAVA集合的扩容机制

ArrayList

java">List<Integer> list = new ArrayList<>();

不指定初始长度，默认刚开始赋值{}空集合，当 add 时，初始长度为 10。

java">// 初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

当超过10之后，每次扩容为原来的 1.5 倍。核心方法是 grow()。

java">private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity >> 1           /* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}
}

每次扩容都是使用 Arrays.copyOf() 拷贝旧数组，然后操作新数组，最终替换掉旧数组。

Arrays.copyOf() 底层最终调用的是 System.arraycopy()。

java">System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));

System.arraycopy() 就是ArrayList增删改慢的原因。

java">List<Integer> list = new ArrayList<>(11);

若设置了初始容量，则只是最开始的值变了，其他都是一样的。

第一次扩容得到的值是 16。

LinkedList

典型的双链表。

结构如下：

java">// 头指针
transient Node<E> first;// 前一个指针    
transient Node<E> last;private static class Node<E> {E item;Node<E> next;Node<E> prev;Node(Node<E> prev, E element, Node<E> next) {this.item = element;this.next = next;this.prev = prev;}
}

Vector

当不指定初始容量时，默认也是 10，并且如果没有指定 capacityIncrement（也就是每次扩容的大小时），每次默认扩容之前的一倍。当然也跟 ArrayList 一样，会使用Arrays.copyOf()拷贝数组。

java">public Vector() {this(10);
}public Vector(int initialCapacity) {this(initialCapacity, 0);
}private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */capacityIncrement > 0 ? capacityIncrement : oldCapacity/* preferred growth */);return elementData = Arrays.copyOf(elementData, newCapacity);
}

比如以下的指定，容量依次是 12 16 20 ...

java">List<Integer> a = new Vector<>(12, 4);

HashMap

注意此分析是针对JDK1.8的。

java">	//HashMap的默认初始长度16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //HashMap的最大长度2的30次幂static final int MAXIMUM_CAPACITY = 1 << 30;//HashMap的默认加载因子0.75static final float DEFAULT_LOAD_FACTOR = 0.75f;//HashMap链表升级成红黑树的临界值static final int TREEIFY_THRESHOLD = 8;//HashMap红黑树退化成链表的临界值static final int UNTREEIFY_THRESHOLD = 6;//HashMap链表升级成红黑树第二个条件：HashMap数组(桶)的长度大于等于64static final int MIN_TREEIFY_CAPACITY = 64;//HashMap底层Node桶的数组transient Node<K,V>[] table;//扩容阈值，当你的hashmap中的元素个数超过这个阈值，便会发生扩容//threshold = capacity * loadFactorint threshold;

HashMap 是懒加载，第一次 put 时，才会进行初始化节点数组，初始容量是 16（也就是Node[16]）。

java">static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}
}

当节点哈希冲突时，刚开始的时候是使用链表解决，当链表中的节点数量超过 TREEIFY_THRESHOLD （也就是8）时，进化为红黑树（避免导致因为链表数量太大导致查询不再是O(1)），但是需要注意：在数组中的总 size 没有超过 MIN_TREEIFY_CAPACITY（64）时，优先考虑的是扩容，而不是树化。当数组中的键值对数量 size（我们通常获取map的长度就是通过这个值） 超过了阈值 threshold（capacity * loadFactor【默认值开始就是 16 * 0.75 = 12】），则进行扩容。