Java中关于HashMap常见问题

HashMap数据结构面试里问 HashMap很多人张口就是“数组 链表 红黑树”。但再追问一句为什么容量必须是 2 的幂为什么链表到 8 还不一定树化扩容时元素到底怎么迁移很多人就开始背八股了。其实 HashMap 不用死记。你可以把它想成一个快递柜数组就是一排柜格负责快速定位hash决定包裹放哪个柜格柜格里已经有包裹了就叫哈希冲突那就排队形成链表队伍太长查询太慢就升级成红黑树柜子快装满了就扩容换一排更大的柜子重新分配。下面我们跟着一次put把 HashMap 的核心机制串起来。一、一次 put 到底发生了什么当你写下map.put(张三, 18);HashMap 大概做这几件事算出 key 的 hash根据 hash 和数组长度算出下标看这个位置是不是空的空就直接放不空就判断 key 是否相等相等就覆盖 value不相等就挂到链表或红黑树上元素太多就扩容。一句话数组负责定位链表/红黑树负责处理冲突扩容负责控制负载。二、下标是怎么算出来的HashMap 最终用这个公式算下标int index (n - 1) hash;n是数组容量。这里有两个关键点。第一容量必须是 2 的幂。因为当n是 2 的幂时n - 1的二进制低位全是 1。比如n 16n - 1 15二进制是1111n 32n - 1 31二进制是11111。这样(n - 1) hash就能均匀保留 hash 的低位效果类似取模但位运算更快。如果容量不是 2 的幂某些下标可能永远算不到桶分布会不均匀。所以就算你手动指定了一个不是 2 的幂的初始容量HashMap 也会帮你调整成最接近的、更大的 2 的幂。第二hash 会先扰动一下。HashMap 不是直接用key.hashCode()而是把 hash 的高位和低位混合一下让结果更分散减少冲突。你不用记具体代码记住目的就行让 hash 更散少撞车。三、冲突了怎么办算出下标后如果那个位置是空的直接放。如果不空就要处理冲突key 相等覆盖 valuekey 不相等挂到链表后面链表太长再考虑转红黑树。这里判断 key 是否相等不只看 hash还要用equals()。所以自定义对象当 key 时hashCode()和equals()要一起正确实现不然会出现“找不到 key”或者“两个不同 key 被当成同一个”的问题。四、链表什么时候变红黑树很多人只背“链表到 8 就变红黑树”这是不完整的。必须同时满足两个条件链表长度超过 8数组容量至少为 64。如果链表到了 8但数组容量还不到 64HashMap 不会树化而是先扩容。因为容量小的时候扩容分散冲突更划算树化本身也有额外开销。反过来红黑树节点减少到 6 时会退回链表。为什么是 6 不是 8因为留个缓冲避免在 7、8 附近来回转换。可以记成8 是树化线64 是容量门槛6 是退化线。红黑树也不用深入理解你只要知道它是一种自平衡的树查起来比长链表快。链表查询要一个个找红黑树能少走很多步。五、什么时候扩容默认情况下初始容量是 16负载因子是 0.75扩容阈值是16 × 0.75 12。当元素数量超过 12就触发扩容。新容量是原来的 2 倍。扩容最核心的动作是把旧数组里的元素搬到新数组。JDK 1.8 用了一个巧办法。容量翻倍后元素的新位置只有两种可能还在原来的下标或者变成“原下标 旧容量”。不用每个元素都重新算一遍完整下标。如果旧桶里是红黑树迁移时会先拆成两个链表再按新位置分配必要时重新树化。扩容的优点是降低冲突、提高查询效率缺点是要搬元素元素多时比较耗时。所以如果能预估元素数量初始化时给一个合适容量可以减少扩容次数。六、几个关键参数一张表记住参数默认值作用常见误区初始容量16桶数组初始长度不是随便设最终会调成 2 的幂负载因子0.75扩容阈值 容量 × 负载因子不是越大越好树化阈值8链表转红黑树条件之一还要容量 ≥ 64反树化阈值6红黑树退回链表留缓冲避免频繁转换最小树化容量64容量不够先扩容小容量树化不划算负载因子 0.75 是时间和空间的平衡太小会频繁扩容、浪费空间太大会冲突严重、查询变慢。七、常见误区面试别踩误区一链表到 8 一定变红黑树。不对还要看数组容量是否 ≥ 64。容量不够先扩容。误区二容量可以随便指定。HashMap 最终会把容量调整成 2 的幂因为下标计算依赖这个特性。误区三负载因子越大越好。负载因子大空间利用率高但冲突概率也高查询会变慢。误区四扩容只是把数组变大。扩容还要搬元素、重新分配位置成本不低。八、最后总结HashMap 的核心就三句话用数组快速定位(n - 1) hash算下标容量必须是 2 的幂。用链表/红黑树处理冲突冲突少挂链表冲突严重且容量够大才树化。用扩容控制负载超过阈值容量翻倍元素按规则迁移。所以 HashMap 平均能做到 O(1) 的查找、插入和删除不是因为它神奇而是因为它在数组定位、冲突处理和扩容之间做了一套平衡。