hashmap采用数组+链表+红黑树三级结构，以链地址法解决哈希冲突：冲突元素存于同桶链表中；链表长度≥8且数组长度≥64时树化为红黑树，节点≤6时退化回链表；通过哈希扰动和2的幂容量配合(n−1)&hash提升散列均匀性；负载因子0.75触发翻倍扩容以降低整体冲突。
HashMap 用链地址法解决哈希冲突，核心是“数组 + 链表 + 红黑树”三级结构。
链地址法是基础方案
当不同 key 经过哈希计算后落到同一个数组下标（桶）时，它们不会覆盖，而是被串成一条链表。每个桶位置存储的是链表头节点（Node 类型），后续节点通过 next 指针连接。这样冲突的元素都保留在同一个桶里，只是逻辑上拉长了查找路径。
红黑树优化长链表查询
链表太长会导致最坏 O(n) 查找效率。JDK 1.8 引入树化机制：当某个桶中链表长度 ≥ 8 且 当前数组长度 ≥ 64 时，链表自动转为红黑树。树结构让查找、插入、删除稳定在 O(log n)。反过来，如果树中节点数 ≤ 6，又会退化回链表——避免频繁切换开销。
哈希扰动降低冲突概率
冲突少，链表就短。HashMap 不直接用 key.hashCode()，而是先做扰动：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
这个操作把高16位异或进低16位，让高位也参与索引计算，显著提升散列均匀性。配合数组长度始终是 2 的幂次方（如 16、32、64…），再用 (n − 1) & hash 快速取下标，进一步减少低位重复导致的聚集冲突。
扩容缓解整体冲突压力
当元素总数超过 容量 × 负载因子（默认 0.75） 时触发扩容，数组长度翻倍（如从 16 → 32）。所有已有元素重新计算哈希并分配到新桶中。桶变多、密度下降，冲突自然减少。注意：扩容是全量重哈希，有一定开销，所以初始容量设合理能避免频繁扩容。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
