先讲个真事。几年前我面一个哥们简历上写着“精通 Java 集合框架”。我问了他这道题他张嘴就来“为了减少哈希冲突扩容时不需要重新计算索引位置。”对标准答案一个字不差。然后我问了他第二句——“那 HashMap 的容量为什么不能设成 100100 不是 2 的幂但也能用啊。”他愣住了。沉默了三秒之后说了句大实话“没想过。”那次面试他没挂但我对他的评价从“扎实”降到了“背过”。标准答案是什么这道题随便找个面经都能找到标准答案大概是这么几句HashMap 的容量用 2 的幂是因为(n - 1) hash等价于hash % n位运算比取模运算快。扩容的时候也不需要对每个元素重新算哈希值元素要么留在原位要么移到「原位 旧容量」的位置。这些都是对的。但如果你只答到这一层——面试官不会说你错但他会接着往下挖。因为他在乎的根本不是你知不知道结论而是你有没有真的搞懂为什么。面试官真正在考你什么我当面试官的时候这道题其实在测三件事。第一件位运算和取模到底什么关系这是一个很多同学卡住的地方。我尽量讲得简单点。先看一个生活例子假设有个大转盘转盘上有 16 个格子编号 0 到 15。你闭着眼睛扔飞镖飞镖落在几号格子你根本不知道因为镖可能落在范围外。怎么让它永远落在 0-15 之间很简单你拿编号对 16 取余数编号 20 → 20 ÷ 16 1 余 4 → 落在 4 号格子 编号 50 → 50 ÷ 16 3 余 2 → 落在 2 号格子 编号 16 → 16 ÷ 16 1 余 0 → 落在 0 号格子这个“除以 16 取余数”就是取模HashMap 本质上要干的就是这件事——把任意一个 key 的 hash 值映射到数组的某个位置。那为什么 HashMap 不用%而用因为计算机做除法取模本质是除法比做位运算慢了不是一个数量级。但位运算有个限制——操作符不能直接替代%除非你的除数是 2 的幂。我举个例子你就懂了。假设数组长度是 1616 的二进制是1 0000。16 - 1 1515 的二进制是1111。现在有一个 hash 值比如 47它的二进制是10 1111。拿 47 和 15 做按位与47 → 10 1111 (32 8 4 2 1 47) 15 → 00 1111 (8 4 2 1 15) ————————————————————————————————————————— → 00 1111 (8 4 2 1 15)得到 15。你再用 47 除以 16 取余数47 ÷ 16 2 余 15。结果一样为什么会一样因为 15 的二进制全是一串 1跟它做按位与就相当于只保留了 hash 值的低 4 位。而保留低 4 位恰好就等于对 16 取模。如果长度不是 2 的幂会怎样比如长度是 1010 - 1 9, 9 的二进制是 1001 47 → 10 1111 9 → 00 1001 ————————————————————————————————————————— → 00 1001 (9)但 47 ÷ 10 4 余 7。结果对不上了因为 9 的二进制不是全 1低位有 0按位与的时候把它“吃掉”了造成了不均匀。所以结论很简单容量必须是 2 的幂是因为只有 2 的幂减 1 的二进制全是 1才能用代替%。第二件扩容迁移为什么不需要重算面试官听到你说“扩容时不需要重新算哈希位置”——他真正想确认的是你理不理解为什么不需要重算。扩容的时候数组长度从 16 变成 32。原来用 hash 的低 4 位决定位置现在用低 5 位。关键来了——低 4 位跟原来一样多出来的只是第 5 位。如果第 5 位是 0位置不变如果第 5 位是 1位置变成原位置 oldCap。JDK 源码里是这么写的。直接看resize()方法中的关键部分// JDK 1.8 HashMap.resize() 扩容迁移逻辑 NodeK,V loHead null, loTail null; // 低位链表位置不变 NodeK,V hiHead null, hiTail null; // 高位链表位置 oldCap NodeK,V next; do { next e.next; // 关键判断e.hash oldCap // 如果结果是 0说明新增的那一位是 0位置不变 // 如果结果不是 0说明新增的那一位是 1位置要变 if ((e.hash oldCap) 0) { // 保持原位加入低位链表 if (loTail null) loHead e; else loTail.next e; loTail e; } else { // 移到新位置原位置 旧容量加入高位链表 if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); // 低位链表放回原位 if (loTail ! null) { loTail.next null; newTab[j] loHead; } // 高位链表放到 j oldCap 的位置 if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }这段代码是整个扩容优化的精华。它没有对每个元素重新计算 hash 位置它只做了一件事——拿e.hash oldCap看那一个新增的 bit 是 0 还是 1。举个例子原来长度是 160001 0000 hash 值假设是 230001 0111 扩容前hash (16-1) 23 15 0001 0111 0000 1111 0111 位置 7 扩容后长度是 320010 0000 扩容后新位置 23 (32-1) 23 31 0001 0111 0001 1111 1 0111 位置 23 看23 7 16 原位置 7 旧容量 16 为什么因为 hash 的第 5 位从 0 开始数是 1所以加上 oldCap。而e.hash oldCap就是专门用来检查“新增的那一位是 0 还是 1”的e.hash 23 → 0001 0111 oldCap 16 → 0001 0000 ————————————————————————————————————————— 0001 0000 ≠ 0 → 第 5 位是 1要迁移到高位JDK 1.7 是怎么干的1.7 没有这个优化它老老实实对每个元素重新hash % newCapacity。这也是为什么 JDK 1.8 的扩容效率高很多。第三件JDK 1.7 扩容为什么会死循环这个属于加分项。如果你在回答了 1.8 的优化后能主动提到 1.7 的死循环问题面试官会非常舒服。JDK 1.7 扩容时的transfer()方法用的是头插法——新元素插到链表头部。源码长这样// JDK 1.7 HashMap.transfer() —— 头插法会形成环形链表 void transfer(Entry[] newTable, boolean rehash) { int newCapacity newTable.length; for (EntryK,V e : table) { while (null ! e) { EntryK,V next e.next; // ① 先记下下一个节点 if (rehash) { e.hash null e.key ? 0 : hash(e.key); } int i indexFor(e.hash, newCapacity); e.next newTable[i]; // ② 把 e 的 next 指向新数组当前位置的头 newTable[i] e; // ③ 把 e 放到新数组当前位置的头部 e next; // ④ 继续处理下一个 } } }为什么头插法会死循环假设两个线程同时触发扩容线程 A 在执行到第 ① 句后被挂起线程 B 完成了全部扩容操作。等线程 A 恢复执行时链表的方向已经被翻转了A 拿着旧的 next 指针继续跑最终 A→B 和 B→A 互相指向对方形成一个环形链表。下次有人调用get()的时候遍历链表永远走不到头CPU 直接飙到 100%。JDK 1.8 改成了尾插法不会反转链表顺序死循环问题也就不存在了。tableSizeFor一个被严重低估的骚操作还有一个很多人不知道的点——当你new HashMap(10)的时候实际容量不是 10是 16。因为 HashMap 的构造器里调了一个叫tableSizeFor()的方法它会自动把你传的数向上取到第一个大于等于它的 2 的幂。源码就这么几行// JDK 1.8 HashMap.tableSizeFor() // 作用返回第一个大于等于 cap 的 2 的幂 // 你传 10 → 返回 16 // 你传 20 → 返回 32 static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }这个算法非常优雅。它的思路是先减 1然后通过不断右移再或运算把最高位 1 后面的所有位都变成 1最后加 1 就得到了 2 的幂。举个例子cap 10 → 二进制 1010第一步n cap - 1 9 → 1001 第二步n | n 1 → 1001 | 0100 1101 第三步n | n 2 → 1101 | 0011 1111 第四步n | n 4 → 1111 | 0000 1111 ... 后面几步不变 最后n 1 1111 1 10000 16面试的时候如果你能提一句“对了tableSizeFor 的那个移位算法还挺巧妙的”——面试官就知道你翻过源码不是背的。8 年老兵说句实话这道题我问了几百次我把面试者分三档你可以对号入座第一档只答“减少哈希冲突”——及格线。说明看过面经但没钻进去。第二档能答出“位运算代替取模快”“扩容时位置不用重算”——不错了。大部分面试官会翻篇问下一题。第三档在第二档的基础上随口加一句“因为 (n-1) 的二进制全 1按位与就是保留 hash 低位等价于取模”。只多了 20 个字面试官直接在心里把你的评级从“背过面经”调成“基础扎实”。如果再能提到 JDK 1.7 的头插法死循环和 tableSizeFor 的移位算法——恭喜这道题的满分就已经拿到了。我这么多年面试最大的感受就是面试官和你无冤无仇不会故意刁难你。他只是在找一个信号一个能让他确定“这个人真的懂不是背的”的信号。你多说的那一句话往往就是那个信号。你面试的时候被问到过这道题吗你是怎么答的来留言区唠唠