hashmap结构
数组下标计算
当数组长度正好是 2的n次方时。
即,当数组长度正好是 2的n次方时,%运算可以转换为 & 运算,效率更高。
hash函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash冲突
当key1和key2 hash值相等时(hash冲突),导致下标一样，这时hashmap采用尾插法将key2插入到key1的尾部
image.png
put流程
image.png
hashmap链表转红黑树时机
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//链表长度大于等于 TREEIFY_THRESHOLD
treeifyBin(tab, hash);
break;
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//桶数组容量大于等于 MIN_TREEIFY_CAPACITY
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
