Jdk7不同集合的扩容机制

集合类	初始容量	负载因子	扩容公式	扩容时机
ArrayList	10	无	新容量 = 旧容量 × 1.5	元素数量超过容量时
HashMap	16	0.75	新容量 = 旧容量 × 2	元素数量超过 容量 × 负载因子 时
HashSet	16	0.75	新容量 = 旧容量 × 2	元素数量超过 容量 × 负载因子 时
Vector	10	无	新容量 = 旧容量 + 增量 或 × 2	元素数量超过容量时
Hashtable	11	0.75	新容量 = 旧容量 × 2 + 1	元素数量超过 容量 × 负载因子 时

通过了解不同集合类的扩容机制，可以更好地选择和使用合适的集合类，避免频繁扩容带来的性能开销。

ArrayList

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;// newCapacity = oldCapacity + oldCapacity / 2int 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);
}

HashMap

头插法

void addEntry(int hash, K key, V value, int bucketIndex) {if ((size >= threshold) && (null != table[bucketIndex])) {// 旧容量 * 2resize(2 * table.length);hash = (null != key) ? hash(key) : 0;bucketIndex = indexFor(hash, table.length);}createEntry(hash, key, value, bucketIndex);
}

HashSet

通过HashMap实现的.

public HashSet() {map = new HashMap<>();}

Hashtable

protected void rehash() {HashtableEntry e, old;int i, index;int oldCapacity = table.length;HashtableEntry oldTable[] = table;// 新容量 = 旧容量 × 2 + 1int newCapacity = oldCapacity * 2 + 1;HashtableEntry newTable[] = new HashtableEntry[newCapacity];threshold = (int)(newCapacity * loadFactor);table = newTable;for (i = oldCapacity ; i-- > 0 ;) {for (old = oldTable[i] ; old != null ; ) {e = old;old = old.next;index = (e.hash & 0x7FFFFFFF) % newCapacity;e.next = newTable[index];newTable[index] = e;}}
}

Vector

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}