面试官问「讲讲 HashMap」,五分钟讲不下来的人很多。这篇把它拆成五个问题:长什么样、放进去经历了什么、什么时候长树、扩容怎么搬、为什么不是线程安全的。
HashMap 底层是 Node[] table——一排格子(桶),每个格子可以挂一条链表,链表太长还会变成红黑树:
table[0] → null
table[1] → K1 → K2 → K5 (链表,短)
table[2] → TreeNode 树 (链长≥8 且 数组≥64 才树化)
table[3] → null
快递柜类比:柜子编号由地址决定(hash),塞同一个柜子的包裹在柜里排成串(链表),串太长翻起来慢,就改成立体货架(红黑树),按序摆放二分查找。
关键参数背下来:默认容量 16、负载因子 0.75(装到 75% 就扩容)、树化阈值 8、退树化阈值 6、树化最小数组 64。
1. 算 hash:hashCode 的高 16 位异或低 16 位(扰动,让高位也参与定位,减少扎堆)
2. 定位桶:(n - 1) & hash——n 是 2 的幂时等价于取模,但位运算快
3. 桶空 → 直接放
4. 桶不空 → 桶头 key 相同就更新;是树就按树插;是链表就尾插到尾,插完链长 ≥8 尝试树化
5. 元素总数超过 容量 × 0.75 → 扩容两倍
注意第 4 步的「尝试树化」有陷阱:链长到 8 但数组不足 64 时,只扩容、不树化——小数组扎堆,加格子比分枝更划算。这是「树化双条件」,面试高频陷阱。
扩成两倍后,每个节点的新位置只有两种可能:原位置,或原位置 + 旧容量。判断只需看 hash & 旧容量 那一位是 0 还是 1——所以 JDK 8 把一条链拆成「低位链、高位链」两条,各自整体搬家,不用逐个重新散列。
为什么容量必须是 2 的幂?两个好处都来自位运算:(n-1) & hash 代替取模提速;扩容时新位置只由一个比特位决定。
JDK 7 扩容搬家用头插法(新节点插链头),搬到一半顺序会倒过来。两个线程同时扩容,一个刚取下 A 被挂起,另一个搬完了;恢复后继续插,A 指 B、B 又指 A——链表成环,之后 get 在环里转死循环,CPU 飙满。
JDK 8 两处修复:改尾插法(顺序不变,不会成环)+ 高低位拆分。但 HashMap 依然不是线程安全的:并发 put 仍会互相覆盖丢数据。多线程请用 ConcurrentHashMap(下一篇)。
1. 重写 equals 必须同时重写 hashCode。定位桶靠 hash,桶内比对靠 equals——两个「相等」的对象若 hash 不同,会进不同桶,get 永远找不到
2. key 要不可变。把可变对象当 key,放进去后再改它的字段,hash 变了,等于把包裹贴错了柜号,取不出来了
拿真实数字走一遍。旧容量 16,某节点 hash=21(二进制 10101):
21 & 15 = 10101 & 01111 = 00101 = 5第 5 位是 0 的节点呢?原地不动。所以一条链上的节点,按这一位分成「不动组」和「加 16 组」,整组搬迁。这就是「不用重算 hash」的全部含义——判断一个比特位,比重新散列便宜太多。
put 的镜像过程:
1. 同样的扰动 hash 定位桶
2. 先看桶头:hash 相等且(== 或 equals)→ 直接返回
3. 桶头是树 → 树查找,O(log n)
4. 是链表 → 顺着 next 逐个比对,比对条件依然是「hash 相等且 equals」
注意这个比对条件:先比 hash(int 比较,快),hash 相同才 equals(可能贵)。这也是「重写 equals 必须重写 hashCode」的性能理由——hash 不同的话,equals 根本不会被调用,两个「相等」对象各躺各的桶,查找直接落空。
HashMap 允许一个 null 键:null 没法调 hashCode,干脆固定落在 table[0],get 和 put 对 null key 都直奔 0 号桶。value 要几个 null 都行,没人管。
扰动可以手算验证:把 hashCode 高 16 位异或到低 16 位。设 hashCode 为 0x00020001,高 16 位是 2、低 16 位是 1,异或后得 0x00020003。多这一步为哪般?定位桶只看低几位——两个 hashCode 仅高位不同,本该散开却全挤一个桶。把高位掺进来,等于让 32 位都参与定位,扰动就是防扎堆的搅拌动作。
桶下标口诀 (n - 1) & hash:n=16 时掩码是 15,等价于 hash 对 16 取模,但位运算免除了除法。注意等价只对 2 的幂成立——这是容量必须 2 的幂的第一个理由,第二个(扩容一步定位)见上文搬家演算。面试被问「hash 函数做了什么优化」,答「高 16 位异或低 16 位的扰动函数」,正是这一句。
HashMap 的 null 键固定住 0 号桶,null 值随便放;Hashtable 两个都禁。差别在设计年代:Hashtable 出身早,取值靠「先 contains 判空再 get」的两步写法,并发下没法消歧,干脆一禁了之。这个取舍后来被 ConcurrentHashMap 继承(6.2 节讲过它的 null 禁令)。面试把这条因果链连起来答,是「懂得为什么」的信号。
HashMap 是「hash 定柜、链表串包、长了变树、满了翻倍搬家」的结构;2 的幂容量让定位和扩容都吃位运算红利,树化要过双条件,线程安全它从来不管。