前言:通过源码分析 HashTable 的扩容机制。
调用链
rehash 方法源码
/**
* Increases the capacity of and internally reorganizes this
* hashtable, in order to accommodate and access its entries more
* efficiently. This method is called automatically when the
* number of keys in the hashtable exceeds this hashtable's capacity
* and load factor.
*/
@SuppressWarnings("unchecked")
protected void rehash() {
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
分析
- 计算新容量,新容量为 旧容量 * 2 + 1
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
// overflow-conscious code
// 新容量为 旧容量 * 2 + 1
int newCapacity = (oldCapacity << 1) + 1;
- 对计算得到的新容量进行修正
/**
* 如果新容量大于最大的数组长度(Integer的最大值 - 8),
* 则判断是否旧容量就是最大值了,如果是,直接返回,如果不是,则将新容量改为最大值后进行扩容操作
*/
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
- 生成新 Entry 数组
生成新的大容量 Entry 数组,注意还未赋值,所以里面只是一堆 null 引用,占用不了多大的空间
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
- 结构修改计数加 1
// 这个字段表明 HashTable 的内部结构被修改的次数,用于 Collection-views 中有关 HashTable 的 fast-fail 机制
modCount++;
- 计算负载容量
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
- 将新数组赋给 table
table = newMap;
- 将旧数组的内容复制到新数组中
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
// 重新计算在新数组中的索引位置
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
// 头插法,故新数组中链顺序与旧链相反
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
头插法具体过程如下图
小结
通过源码分析 HashTable 的扩容机制:
扩容后数组大小为 2 * 旧容量 + 1
头插法,新链顺序与旧链相反