跳到正文
返回集合与并发

集合与并发 整理

HashMap 的数组、链表和红黑树,怎么连起来理解?

按一次 put 的路径回答,避免只背“数组加链表加红黑树”。

先回答:JDK 8 HashMap 的一次 put,大致经历什么?

先处理哈希并计算桶的位置。空桶可以直接放入;非空桶需要检查键是否已存在,存在则替换值,否则沿链表或树查找、插入。插入新映射后,如果元素数量超过扩容阈值,可能触发扩容。树化还受桶内元素数量和整个数组容量共同影响。

为什么容量通常是 2 的幂

JDK 8 的桶下标计算使用 (n - 1) & hash,其中 n 是数组容量。容量按 2 的幂组织,扩容后原桶内的元素可以根据新增的那一位进行拆分,避免把扩容理解成重新调用每一个键的 hashCode。

默认负载因子是 0.75。它是空间与冲突概率之间的一种取舍,不表示数组里有 75% 的桶非空时才扩容。阈值主要与映射数量有关。

树化不是一句“到了 8 个就变树”

JDK 8 源码中的 TREEIFY_THRESHOLD 为 8,MIN_TREEIFY_CAPACITY 为 64。小数组遇到严重冲突时,通常优先尝试扩容,而非立刻树化。

具体触发点取决于插入路径中的计数和检查,不能只背一个数字后断言“第 8 个元素必定树化”。退化回链表也应结合删除、扩容拆分等路径理解,不要把阈值当成所有路径完全相同的规则。

键为什么要同时满足 equals 和 hashCode 约定

HashMap 先借助哈希定位,再判断键是否相等。如果两个 equals 相等的键却产生不同的 hashCode,就可能无法按预期找到已有映射。作为键的字段入表后发生变化,同样可能导致查找失败。

线程安全的回答边界

HashMap 不是线程安全集合。多个线程并发修改时,不能靠“JDK 8 已经修了某个问题”来保证正确性。需要根据读写模型选择外部同步、ConcurrentHashMap 或其他设计。涉及组合操作时,也要检查是否需要原子方法,而非把两个独立操作拼在一起。

延伸阅读

以上为个人整理。涉及版本实现和线上使用时,请结合对应文档与实际测试判断。