HashMap关键知识点总结

HashMap 作为一个 java 程序员天天都使用的类，但是如果被问一些关键问题的时候，自己好像知道，但是更多的是自己好像又说不明白怎么回事。而这些关键的知识点往往再某些时候变得非常重要，比如性能优化的时候。

下面我对以下几个方面来进行说明：

1. 为何 table 的大小必须是 2 的幂
2. 扩容
3. 树化和反树化

为何table的大小必须是2的幂

hash & oldCap==0，则不一定，数据还停留在原来的位置。如果hash & oldCap!=0 则需要移动到原桶 + oldCap的位置。

扩容

hashmap 何时进行扩容呢？

当 hashmap 中的元素大于 负载因子*tablesize 的时候，这个时候就会触发扩容。并且扩容为上一次的 2 倍。

当然你也可以手动设置初始 tablesize 的大小，都会调用tableSizeFor，这个方法使不管你的初始的 tablesize 是否为 2 的幂，都会变成 2 的幂。

这里有个需要注意的点：

在 hashmap 放数据之前， threshold 其实就是等于 tablesize 的容量的，当进行第一次 put 的时候会调用 resize，这个时候才会 threshold=factory*capacity;

具体的内容如下

树化和反树化

树化必须同时满足以下两个条件：

1. 链表中的元素个数必须大于等于 8；
2. tablesize 的大小必须大于等于 64；

树化的目的是为了平衡内存空间和查询效率；毕竟树的维护还是很重，所以当数据量少的时候要尽量避免树化。

反树化的过程，很多人写成了当节点小于 6 的时候就会反树化，其实准确的来说应是如下的逻辑

1
2
3
4
5
6
7
8
if (root == null
    || (movable
        && (root.right == null
            || (rl = root.left) == null
            || rl.left == null))) {
    tab[index] = first.untreeify(map);  // too small
    return;
}

root == null：树被删到空，直接退回链表（其实就是没有树了）。

movable && (...)：当允许调整这个桶（movable 为 true，正常删除场景）并且树已经“太小/太浅”*时，退回链表。 这里用的是*结构性检查而不是显式计数：

• root.right == null：右子树都没了 → 过小
• root.left == null：左子树都没了 → 过小
• root.left.left == null：左子树深度不够（形如 4～5 个节点的瘦树）→ 过小

下面是常见的问题

• Previous
  A Tutorial of Clickhouse
• Next
  多线程的基本概念