HashMap的扩容机制
什么时候扩容：
网上总结的会有很多，但大多都总结的不够完整或者不够准确。大多数可能值说了满足我下面条件一的情况。
扩容必须满足两个条件：
1、 存放新值的时候当前已有元素的个数必须大于等于阈值
2、 存放新值的时候当前存放数据发生hash碰撞（当前key计算的hash值换算出来的数组下标位置已经存在值）
下面我们看源码，如下：
首先是put()方法
public V put(K key, V value) {
//判断当前Hashmap(底层是Entry数组)是否存值（是否为空数组）
if (table == EMPTY_TABLE) {
inflateTable(threshold);//如果为空，则初始化
}
//判断key是否为空
if (key == null)
return putForNullKey(value);//hashmap允许key为空
//计算当前key的哈希值
int hash = hash(key);
//通过哈希值和当前数据长度，算出当前key值对应在数组中的存放位置
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果计算的哈希位置有值（及hash冲突），且key值一样，则覆盖原值value，并返回原值value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//存放值的具体方法
addEntry(hash, key, value, i);
return null;
}
在put()方法中有调用addEntry()方法，这个方法里面是具体的存值，在存值之前还有判断是否需要扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
//1、判断当前个数是否大于等于阈值
//2、当前存放是否发生哈希碰撞
//如果上面两个条件否发生，那么就扩容
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容，并且把原来数组中的元素重新放到新数组中
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
如果需要扩容，调用扩容的方法resize()
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
//判断是否有超出扩容的最大值，如果达到最大值则不进行扩容操作
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
// transfer()方法把原数组中的值放到新数组中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
//设置hashmap扩容后为新的数组引用
table = newTable;
//设置hashmap扩容新的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer()在实际扩容时候把原来数组中的元素放入新的数组中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//通过key值的hash值和新数组的大小算出在当前数组中的存放位置
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
总结：Hashmap的扩容需要满足两个条件：当前数据存储的数量（即size()）大小必须大于等于阈值；当前加入的数据是否照成了hash冲突。
因为上面这两个条件，所以存在这种情况，就是hashmap在存值的时候（默认大小为16，负载因子0.75，阈值12），可能达到最后存满16个值的时候再存第17个值才会发生扩容现象，因为前16个值，每个值一个位置，并没有发生hash碰撞。
注：jdk版本1.7
版权声明：本文为yanzige原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。