故事场景：小区门口的智能快递柜
你家小区门口有一排智能快递柜。快递员老王每天要往柜子里塞几百个包裹，住户凭包裹单号来取件。这排柜子怎么存、怎么取，藏着的就是 HashMap 的全部底层原理。面试官问 HashMap，其实就是在问：这排柜子是怎么运作的？
第一幕：格口与编号（数组 + hash 定位）
柜子一共有 16 个格口（这就是 HashMap 的初始容量 16）。每个包裹送来，老王先根据包裹单号算一个”柜号”：
- 先算单号的哈希值（
key.hashCode()）； - 再做一次”扰动”：把哈希值的高 16 位和低 16 位异或一下（
h ^ (h >>> 16)）。为啥？因为真正定位格口时只用得上低几位，扰动是把高位的信息也”搅”进低位，省得单号相近的包裹全挤到一个格口； - 最后用
(格口数 - 1) & hash算出格口号。注意这里用的是位与而不是取模——前提是格口数必须是 2 的幂，这样(n-1)恰好是低位全 1 的掩码，结果均匀又飞快。
故事解读： 格口阵列就是数组——按编号直达，O(1)。编号算法就是 hash 函数——负责把包裹均匀撒到各个格口，别都堵在一处。
第二幕：两个包裹算出了同一个格口（链表与哈希冲突）
总有这么巧的事：两个包裹算出来的格口号一样。这在柜子界叫”占位”，在 HashMap 里叫哈希冲突。解决办法简单粗暴：同一个格口里的包裹排成一队（链表），取件时先定位格口，再顺着队伍一件件核对单号（equals()）。
编号怎么算、单号怎么核对，我在上一篇《hashCode与equals的区别？一个”寻宝故事”让你彻底开悟！》里用失物招领处的故事讲透了，这篇是它的姊妹篇，建议连着看。
队伍排短了没事，排长了取件就得一件件翻，速度从 O(1) 退化成 O(n)。这就引出了第三幕。
第三幕：队伍太长，格口升级成智能货架（红黑树化）
JDK 8 给柜子定了条规矩：某个格口的队伍超过 8 件包裹，并且格口总数不少于 64，就把这个格口的队伍改造成一架智能分拣货架（红黑树），查找从顺着队伍挨个翻，变成二分定位，O(log n)。
几个高频追问，这里一并答了：
- 为什么偏偏是 8？ 因为在负载因子 0.75 下，哈希分布近似泊松分布，一个桶里冲突到 8 个的概率只有约百万分之六。阈值定 8，是数学算出来的，不是拍脑袋。队伍缩回 6 以下，则退化回链表（阈值 6，留个缓冲带防反复横跳）。
- 为什么格口不到 64 时优先扩容而不是树化？ 队伍长也可能是柜子太少、大家被迫挤在一起。这时候先扩建柜子更划算，所以源码里桶数小于 64 时，哪怕队伍超了 8，也先扩容。
第四幕：柜子整体不够用了（扩容）
16 个格口，规矩是占用超过 75%（负载因子 0.75）就扩建：新柜子数量翻倍到 32，所有包裹重新分格口。
- 为什么是 0.75？ 太小（如 0.5）柜子浪费，太大（如 1.0）冲突排长队。0.75 是空间和时间的经典折中。
- 重新分格口有个妙招： 扩容后容量是 2 的幂翻倍，包裹的新格口要么还是原格口，要么是”原格口 + 旧容量”，看 hash 的多出来的那一位是 0 还是 1 即可，链表顺势拆成高低两队，不用重新算 hash。这也是 JDK 8 的优化，JDK 7 是老老实实全部重算的。
代码里长这样
Map<String, String> map = new HashMap<>();
map.put("单号A", "张三的包裹");
// 定位格口的核心逻辑（示意）
// hash = (key == null)? 0: (h = key.hashCode()) ^ (h >>> 16)
// index = (n - 1) & hash
顺带记住：key 为 null 时 hash 记 0，永远放 0 号格口——所以 HashMap 允许一个 null 键，而 Hashtable 连这个机会都不给（直接 NPE），这也是面试爱问的对比点之一。
面试追问速答区
- 为什么容量必须是 2 的幂？ 为了让
(n-1) & hash等价于取模且分布均匀。构造时传个 17 进去，源码也会帮你向上取整到 32（tableSizeFor）。 - JDK 7 和 8 的区别？ 7 是数组+链表、头插法，多线程扩容时链表可能成环、CPU 100%；8 改成尾插法，并加了红黑树。
- HashMap 线程安全吗？ 不安全。多线程读写请用
ConcurrentHashMap，别抱侥幸心理。 - 负载因子能改大吗？ 能，但冲突会变多；除非你内存实在金贵，别动这个默认值。
简单粗暴地说： HashMap 就是一排”会自己扩建、个别格口还能升级货架”的快递柜——数组管定位，链表管冲突，红黑树管极端情况，扩容管总量。
怎么样，老铁！下次面试官再问”聊聊 HashMap 底层”，你就把这排快递柜搬出来，从格口讲到扩容，保准他听得连连点头。
顺手安利：平时算个哈希、转个时间戳、验个 JSON，我做了个在线工具箱 itupload.cn，打开就用，不用装软件。