02 HashMap 扩容为什么是 2 的幂？先搞懂二进制的秘密（小白也能看懂）

昨天我写了篇 HashMap 扩容原理的文章后台收到好多留言说二进制那段完全看不懂。我说服了。确实你要是没接触过二进制位运算直接看那段就像看天书。所以今天专门写一篇不讲代码、不讲原理、不讲红黑树——只讲一件事为什么 2 的幂减 1 的二进制全是 1以及这到底有什么用。保证你读完能去饭桌上跟同事吹牛。不保证你能撩到妹子。一、先来点生活的——假设你开了个饭馆你开了一家小饭馆只有 16 张桌子编号 0 到 15。每进来一个客人你要把他安排到一张桌子上。怎么安排最简单的办法拿客人的手机尾号除以 16看余数。手机尾号 20 → 20 ÷ 16 1 余 4 → 坐 4 号桌 ✅ 手机尾号 50 → 50 ÷ 16 3 余 2 → 坐 2 号桌 ✅ 手机尾号 87 → 87 ÷ 16 5 余 7 → 坐 7 号桌 ✅ 手机尾号 16 → 16 ÷ 16 1 余 0 → 坐 0 号桌 ✅不管你门牌号多大这么一算最后总是在 0-15 之间。这个除以几看余数的操作写代码的话叫取模符号是%。比如47 % 16 15意思是 47 对 16 取模余数是 15。而 HashMap 干的事跟这差不多——它要把任意一个 key 的 hash 值塞到一个固定大小的数组里。hash 值可能非常大数组只有 16 个坑位。怎么办取个模让它一定落在 0-15 之间。二、但计算机有个见不得人说的毛病——它讨厌除法正常人类算 47 ÷ 16 2 余 15随口就能出来。但计算机不一样。计算机加法快、减法快、位移也快——唯独除法慢得要命。你让它算一下 47 ÷ 16它得把二进制搬来搬去算好几步。写 HashMap 的工程师就想有没有一种办法不用除法也能算出余数有但有个条件——你的桌子数量必须是 2 的幂就是 2、4、8、16、32、64、128 这种数。三、2 的幂有个神奇属性我们来做一个简单的观察。拿出下面几个数把它们转成二进制十进制 二进制 ──────────────────────────────── 16 → 0001 0000 15 → 0000 1111 ← 16-1 32 → 0010 0000 31 → 0001 1111 ← 32-1 64 → 0100 0000 63 → 0011 1111 ← 64-1发现规律没有2 的幂减 1二进制全部是一串 1。16 - 1 15 →1111末尾 4 个 132 - 1 31 →11111末尾 5 个 164 - 1 63 →111111末尾 6 个 1那如果是 10 张桌子10 不是 2 的幂十进制 二进制 ──────────────────────────────── 10 → 0000 1010 9 → 0000 1001 ← 有 0 有 1不全为 1看出差别了吧。2 的幂减 1 全 1不是 2 的幂减 1 不全 1。就这一行差别决定了一切。四、跟全 1 的数做与运算等于完美取模先说下按位与符号是什么。很简单两个二进制数逐个位置比较1 1 1 两个都是 1结果是 1 1 0 0 有一个是 0结果就是 0 0 1 0 0 0 0就四个字双 1 才 1零就零。OK现在我们来一个神奇的实验。随便拿一个数比如 47。然后用 47 跟 151111末尾 4 个 1做按位与47 → 10 1111 32 8 4 2 1 47 15 → 00 1111 8 4 2 1 15末尾全是 1 ————————————————————————— → 00 1111 8 4 2 1 15按位与结果是 15而 47 ÷ 16 的余数你也知道是多少没错也是 15再试一个用 23 和 15 做按位与23 → 01 0111 16 4 2 1 23 15 → 00 1111 8 4 2 1 15 ————————————————————————— → 00 0111 4 2 1 7结果是 7。23 ÷ 16 1 余 7。又对了怎么回事为什么跟 15末尾 4 个 1做按位与就等于对 16 取模你可以这样想15 的二进制是1111一共 4 位都是 1。你随便拿一个二进制数跟1111做按位与——等于你用一块板子把这个数高位左边的位全部挡住只漏出最低的 4 位。漏出来的 4 位这个数是多少就等于原数对 16 取模的余数。就像你在一排 8 个灯泡的最右边 4 个上挡了一块透明的板子——你能看见的灯泡有多少它就是余数。完美。五、如果不是 2 的幂——板子就漏了好现在把桌子数换成 10不是 2 的幂。10 - 1 9。9 的二进制是1001。再用同一个 47 跟 9 做按位与47 → 10 1111 9 → 00 1001 注意bit 2 的位置是 0 ——————————————————————————— → 00 1001 8 1 9按位与结果是 9。但 47 ÷ 10 4 余 7应该是 7 不是 9。结果错了为什么因为 9 的二进制1001有一个 0 在中间。你拿它做按位与那个位置对应的原数47 的 bit 2 1直接被清零了——信息被吃掉了。就像你在灯泡前面放了一块有一个洞的板子——你能看见的灯泡不全是最低 4 位而是零零散散的几个。看到的数字当然不准。六、一张图给你看明白✅ 16 张桌子2 的幂 16-115 的二进制 → 0000 1111全1 47 15 → 保留低4位 → 15 → 47%1615 ✅ ❌ 10 张桌子不是 2 的幂 10-19 的二进制 → 0000 1001有0 47 9 → 丢失bit2 → 9 → 47%107 ❌七、所以回到最初的问题HashMap 扩容为什么是 2 的幂因为它是 2 的幂减 1 后二进制全 1。全 1 之后按位与等价于取模。不用除法就是算得快。那为什么不干脆写成 16、32、64 这种数就行还要问为什么因为有人会问那为啥不能是 100。答案就是上面说的——100 减 1 等于 9999 的二进制是1100011不是全 1。用它做按位与会丢失信息结果对不上。所以结论很简单不是为了炫技不是因为数学好纯粹是因为——计算机讨厌除法而 2 的幂恰好提供了一个不用除法的捷径。八、看不懂没关系。先记住这三句话取模 把大数映射到固定范围就像手机尾号对 16 取余一定落在 0-152 的幂减 1 二进制末尾全是 116→15→111132→31→11111末尾全 1 的数和任何数做按位与 取模 不用除法、速度快记住这三句下次面试官问为什么 HashMap 扩容是 2 的幂你别背答案你就这样给他从头推到尾——他会觉得你不只懂 HashMap你连二进制底层都懂。这就是面试官想要的信号。下一篇回归正题Redis 集群被问 Gossip 协议面试官到底想听什么关注我每天早上八点更新。如果觉得有帮助点个关注支持一下。我最近整理了一份《大厂面试老兵资料包》里面有评分表、高频场景题还有今年新出的AIGC面试题都是200多场面试里一点点攒的市面上没人这么整理过。需要的朋友私信我回复「666」我发你领取方式。