HashMap的底层原理及扩容过程

HashMap的扩容过程(jdk1.8版本)

HashMap的常见参数

initialCapacity 默认初始容量 值为16,最大容量值为2^30
loadFactor 默认加载因子 值为0.75f
threshold 阈值 默认值为16 *0.75 ，即容量*加载因子


这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，加载因子越大表示散列表的装填程度越高，反之愈小。

如果加载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果加载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下无需修改。

在jdk1.7中，hashmap的底层创建的是Entry[]数组，在实例化后，底层就创建了一个长度为16的Entry[]数组，此时的底层结构是数组+链表；在jdk1.8中，底层创建的是Node[]数组，底层在一开始并不会创建数组，在第一次调用put方法时，底层才会创建一个长度为16的Node[]数组，此时的底层结构是数组+链表+红黑树。

何时进行扩容？

HashMap使用的是懒加载，构造完HashMap对象后，只要不进行put 方法插入元素，HashMap并不会去初始化或者扩容table。

当首次调用put方法时，HashMap会发现table为空然后调用resize方法进行初始化。

put方法源码如下

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}


当添加完元素后，如果HashMap发现size（元素总数）大于threshold（阈值），则会调用resize方法进行扩容，然后把扩容后的数组放到新的数组中去。

若threshold（阈值）不为空，table的首次初始化大小为阈值，否则初始化为缺省值大小16。

当table需要扩容时，扩容后的table大小变为原来的两倍，接下来就是进行扩容后table的调整：

假设扩容前的table大小为2的N次方，有put方法可知，元素的table索引为其hash值的后N位确定

那么扩容后的table大小即为2的N+1次方，则其中元素的table索引为其hash值的后N+1位确定，比原来多了一位

因此，table中的元素只有两种情况：

1. 元素hash值第N+1位为0：不需要进行位置调整


2. 元素hash值第N+1位为1：调整至原索引的两倍位置

在resize方法中，第45行的判断即用于确定元素hashi值第N+1位是否为0：

• 若为0，则使用loHead与loTail，将元素移至新table的原索引处


• 若不为0，则使用hiHead与hiHead，将元素移至新table的两倍索引处

扩容或初始化完成后，resize方法返回新的table。

hashmap的resize方法源码

final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap <<1) oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr <<1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}