JAVA集合的扩容机制

ArrayList

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

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

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

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

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()。

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

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

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

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

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

LinkedList

典型的双链表。

结构如下：

// 头指针
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()拷贝数组。

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 ...

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

HashMap

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

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

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

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】），则进行扩容。

扩容的时候，默认会新建一个新数组，新数组的大小是老数组的两倍。

通过 （n - 1）& hash 可以定位到数组的下标，当然，此时n （数组的长度）被定义为 2^n。

当然，当红黑树中的节点下降到 UNTREEIFY_THRESHOLD（也就是6）时，就退化为链表。 

不直接设置为7就变为链表是为了避免如果一直在边界值变来变去的化，导致一直链化和树化来回切换，影响性能，起到一个缓冲的作用。