HashMap底层实现原理：数组、链表和红黑树

面试官问「往 HashMap 里 put 一个键值对，底层发生了什么」，不少人只能答出数组加链表，再问扩容和红黑树就卡住了。hashmap底层实现原理 这条线拆开看，其实就五步。

先定桶位，hash 值要扰动一次

HashMap 内部是一个 Node 数组，默认容量 16。put 时先取 key 的 hashCode，再和它右移 16 位的结果做异或，让高位也参与寻址。下标用 (n - 1) & hash 计算，n 是 2 的幂，效果等同取模但快得多。所以容量永远取 2 的整数次幂，构造时传 10，实际会变成 16。

冲突挂链表，超过 8 个转红黑树

两个 key 落到同一个桶就走链表。JDK 8 里链表长度到 8、且数组长度不小于 64 时转红黑树，查询从 O(n) 降到 O(log n)；节点减到 6 再退回链表。数组还小时不急着树化，先扩容，这一点看源码里的 treeifyBin 很明显。

扩容卡在负载因子 0.75

元素个数超过容量乘 0.75 就触发 resize，容量翻倍。JDK 8 扩容不用重算 hash，只看 hash 和旧容量按位与的结果：为 0 留在原位，否则挪到原下标加旧容量处。一次扩容要搬一部分数据，能预估数量时最好在构造时给初始容量。

头插改尾插，但它仍然不安全

JDK 7 扩容用头插法，多线程下可能把链表接成环，CPU 直接跑满；JDK 8 改成尾插，环没了，并发 put 仍会丢数据。要共享写就用 ConcurrentHashMap，它用 CAS 加锁桶头节点，锁粒度比 Hashtable 小。

查找靠 hash 加 equals 两道关。get 的时候先比 hash 值，hash 相同再调用 equals 逐个比。所以只重写 equals 不重写 hashCode，两个内容相同的对象会落到不同桶里，HashMap 就找不到它。自定义对象当 key，这两个方法要一起改。

把 hashmap底层实现原理 记成一条链：算 hash、定桶位、冲突挂链、树化、到 0.75 扩容。面试答清这几步就够，想再深入就去读 JDK 8 源码里的 putVal 和 resize。