Java 面试小册 | HashMap 的 put 方法

面试官（张姐）：哈喽 malog！今天咱们聚焦下 HashMap 的源码细节 —— 这可是 Java 面试的 “必考题”，你平时有没有扒过它的 put 方法流程呀？

malog：张姐好！必须扒过～毕竟写业务代码天天用 HashMap，不搞懂源码总觉得心里没底哈哈。

问答环节

面试官（张姐）：那你先给我捋捋，HashMap 调用 put 方法时，底层的 putVal 是咋干活的？

malog：行！putVal 的流程大概分 “初始化→算索引→插数据→查扩容” 这几步～首先会先瞅 table 数组是不是空的，要是没初始化，就调用 resize () 整个默认长度 16 的数组；然后给 key 算 hash 值 —— 这里有个 “扰动算法”，把 key 的 hashCode 高 16 位和低 16 位异或一下，再和数组长度减 1 做位运算，算出要放的索引位置。要是这索引位置是空桶（table [i] == null），直接插新节点就行；要是非空，就分情况：要么 key 重复了直接覆盖 value，要么是红黑树节点就往树里插，要么是链表就遍历到尾巴插新节点 —— 插完还得看链表长度是不是超 8，不过光超 8 还不够，得数组长度也超 64 才会转红黑树，不然只是扩容～最后插完了要是 size 超过阈值（容量 ×0.75），就再 resize 扩容。

面试官（张姐）：细节挺到位！那我追问下：那个 “扰动算法” 到底为啥要搞个高 16 位和低 16 位异或？直接用 hashCode 不行吗？

malog：还真不行！比如数组初始长度是 16，(n-1) 就是 15（二进制是 00001111），要是直接用 hashCode 和它做位运算，只有低 4 位参与计算，高 16 位的特征就浪费了，很容易撞哈希冲突。把高 16 位和低 16 位异或，相当于让高位的 “特征” 也混到低位里，散列性更好，能少点冲突～

面试官（张姐）：懂了！那常有人说 “HashMap 链表长度到 8 就转红黑树”，这说法对吗？

malog：这是个常见误区！得满足两个条件：链表长度 > 8 且 数组长度 > 64。要是数组长度没到 64，就算链表长过 8，也不会转红黑树，而是触发扩容 —— 毕竟数组太小的时候树化，反而占内存，不如先扩容让数据更分散～

面试官（张姐）：那 put 完之后，啥时候会触发扩容？扩容是咋扩的？

malog：当 size（实际存储的键值对数量）超过阈值（threshold = 容量 × 负载因子，默认负载因子是 0.75）的时候，就会调用 resize () 扩容。扩容是把数组容量翻倍，然后把旧数组里的节点重新计算索引，迁移到新数组里 ——Java 8 之后迁移的时候还会顺便把链表拆成两个，效率比之前高不少。

面试官（张姐）：不错不错，源码细节吃得挺透！

重点问题和参考回答