先给结论因为要用 (n-1)代替取模。n 是 2 的幂时n-1的二进制全是 1位与的结果刚好等价于取模而且比取模快。但更值钱的理由在扩容那一步多数人不知道。一个很常见的初始化很多团队写代码时都会这么干已知要放 1000 个元素于是new HashMap(1000)心想一次分配到位省一次扩容。实际上它还是会扩一次。原因在后面第 4 节看完就明白为什么阿里巴巴的开发手册建议写成new HashMap(expectedSize / 0.75 1)。扩容不是小事。一次 resize 要重新分配一个两倍大的数组再把所有元素搬过去数据量大的时候这是一次明显的停顿。缓存类的 Map 如果初始化容量没算对启动阶段可能连续扩三四次。先把问的是哪一层搞清楚HashMap 底层实现其实是把四个问题打包在一起问数据结构长什么样hash 值怎么算的拿到 hash 之后怎么定位到数组下标容量不够时怎么扩容。多数人只会答第一层。第三层和第四层才藏着 2 的幂这个答案。逐层拆开数据结构数组加链表链表太长变红黑树JDK 1.8 的 HashMap 是数组table、链表、红黑树的组合。每个数组位置叫一个桶哈希冲突的元素挂在同一个桶上形成链表。链表长了查询会退化成 O(n)所以 1.8 加了树化链表长度超过 8并且数组长度达到 64链表转成红黑树查询变成 O(log n)。注意是两个条件同时满足。数组还没到 64 的时候优先做的是扩容而不是树化因为扩容能直接把冲突分散开代价通常比建树低。反过来树上的元素减少到 6 时会退化成链表。为什么不是 8中间留了 1 的缓冲避免某个桶的元素数在 8 附近反复横跳导致来回转换。hash 值一次高位异或// JDK 1.8 java.util.HashMap static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把 hashCode 的高 16 位和低 16 位做异或结果还是 32 位。这一步叫扰动。它的目的不是让 hash 更随机。真正的原因是数组长度比较小的时候定位下标只用到低位高 16 位完全不参与。如果两个 key 的低位一样、高位不同它们会撞到同一个桶。异或之后高位的信息被混进了低位冲突概率就降下来了。HashMap 只在这一处做了扰动没有用多重哈希那种更重的算法。这是个取舍多花一次异或的代价换大部分场景下的冲突改善够了。定位下标用位与取代取模// JDK 1.8putVal 里的定位 // n table.length int index (n - 1) hash;取模的正经写法是hash % n。位运算比取模快但两者等价有个前提n必须是 2 的幂。n 是 16n-1是 15二进制1111。任何数跟1111做与运算结果就是它最低 4 位的值范围 0 到 15正好是取模的结果。n 是 10n-1是 9二进制1001。做与运算之后第 2 位和第 3 位永远是 0也就是说下标 2、3、4、5、6、7 里有好几个永远空着。一半的桶浪费了冲突率直接翻倍。这就是必须是 2 的幂最直接的技术理由。扩容这才是 2 的幂真正的价值这部分是被答得最薄的一层。容量从 16 扩到 32(n-1) hash里的掩码从1111变成11111多参与了一位。于是每个元素的新下标只有两种可能原下标不变或者原下标加上旧容量16。判断条件极简单看 hash 在那新增的一位上是 0 还是 1// JDK 1.8 resize 里的拆分逻辑简化后 if ((e.hash oldCap) 0) { // 新下标 原下标留在 lo 链 } else { // 新下标 原下标 oldCap进 hi 链 }一次位与就能决定去向不用重新算 hash不用重新取模。好处还不止省了一次运算。因为同一条链上的元素只可能分到两个桶里JDK 1.8 直接把原来那条链拆成 lo 和 hi 两条各自挂到新位置链上元素的相对顺序还能保持原样。这顺手解决了 1.7 头插法导致的扩容死循环问题。如果容量不是 2 的幂这套拆分逻辑完全不成立每个元素都得老老实实重算一遍模。扩容是 HashMap 最贵的操作成本翻一倍是很难接受的。顺带说初始化那件事。构造时传入的初始容量会被tableSizeFor往上取整到最近的 2 的幂// JDK 1.8把任意正整数变成 它的最小 2 的幂 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; }传入 1000得到 1024。但扩容阈值是1024 * 0.75 768放到第 769 个元素时就触发扩容了。所以想放 1000 个元素又不扩容初始值得写成1000 / 0.75 1约等于 1335。面试官在等的那句答完 (n-1)比取模快及格了。但这句话任何背过八股的人都会说没有区分度。真正让人抬眼的是这一句取模快只是顺带的收益2 的幂真正解决的是扩容成本。正因为容量翻倍时掩码只多一位每个元素的新下标只有两种可能判断只需要一次位与JDK 1.8 才能把一条链拆成两条直接搬走不用逐个 rehash。顺带说一句负载因子取 0.75 也是有依据的。源码注释里给了个数在理想的随机 hash 下桶里的元素数服从泊松分布负载因子 0.75 时链表长度达到 8 的概率大约是千万分之六小到可以忽略。所以 8 这个树化阈值不是拍脑袋定的。第二段尤其加分因为大多数人只会背默认 0.75说不出它是怎么来的。五个常见误区误区一以为 new HashMap(1000) 就不会扩容会扩。容量被上调到 1024但阈值是 1024 乘 0.75等于 768。要按预期元素数除以 0.75 再加 1 来给初始值。误区二以为链表长度超过 8 就树化还要数组长度达到 64。没到 64 时优先扩容因为那时候冲突多半是容量不够造成的。误区三以为元素少于 8 就从红黑树退回来退化阈值是 6。中间留的缓冲是为了避免在临界点反复转换。**误区四把扰动函数说成让哈希更均匀**它解决的是低位信息不足的问题。数组小的时候只有低几位参与运算高 16 位被混下来才有意义。**误区五以为 1.8 的 HashMap 线程不安全只是数据覆盖**死循环确实被尾插法解决了但并发 put 依然会丢数据并发扩容也有风险。要线程安全还是得用 ConcurrentHashMap。至于用 Hashtable我一般不选全表一把锁并发下退化得很厉害。这条看你们的具体场景我给不了死结论。速查表参数取值为什么默认初始容量162 的幂 (n-1)可用负载因子0.75泊松分布下链长达 8 概率约千万分之六扩容倍数2 倍掩码只多一位拆分成本最低树化阈值链表 8 且数组 ≥ 64优先扩容扩容解决不了再建树退化阈值6留缓冲避免临界反复转换扰动h ^ (h 16)让高 16 位参与低位运算关于本文HashMap 这条线还有几道没写为什么线程不安全、1.7 头插法死循环的完整过程、ConcurrentHashMap 从分段锁到 CAS 加 synchronized 的演进。J014 会讲 ConcurrentHashMap那篇和这篇连着看会顺很多。我会接着更新。感兴趣的话可以留个关注方便下次找。另外完整的十二个模块Java / C / Go / JVM / MySQL / Redis / MQ / 分布式 / 事务 / 网络 / 系统设计 / 项目深挖我整理成了一份手册每题都标了考察点和加分答法。【草丛后端架构】持续分享后端架构与底层原理。
先给结论因为要用 (n-1)代替取模。n 是 2 的幂时n-1的二进制全是 1位与的结果刚好等价于取模而且比取模快。但更值钱的理由在扩容那一步多数人不知道。一个很常见的初始化很多团队写代码时都会这么干已知要放 1000 个元素于是new HashMap(1000)心想一次分配到位省一次扩容。实际上它还是会扩一次。原因在后面第 4 节看完就明白为什么阿里巴巴的开发手册建议写成new HashMap(expectedSize / 0.75 1)。扩容不是小事。一次 resize 要重新分配一个两倍大的数组再把所有元素搬过去数据量大的时候这是一次明显的停顿。缓存类的 Map 如果初始化容量没算对启动阶段可能连续扩三四次。先把问的是哪一层搞清楚HashMap 底层实现其实是把四个问题打包在一起问数据结构长什么样hash 值怎么算的拿到 hash 之后怎么定位到数组下标容量不够时怎么扩容。多数人只会答第一层。第三层和第四层才藏着 2 的幂这个答案。逐层拆开数据结构数组加链表链表太长变红黑树JDK 1.8 的 HashMap 是数组table、链表、红黑树的组合。每个数组位置叫一个桶哈希冲突的元素挂在同一个桶上形成链表。链表长了查询会退化成 O(n)所以 1.8 加了树化链表长度超过 8并且数组长度达到 64链表转成红黑树查询变成 O(log n)。注意是两个条件同时满足。数组还没到 64 的时候优先做的是扩容而不是树化因为扩容能直接把冲突分散开代价通常比建树低。反过来树上的元素减少到 6 时会退化成链表。为什么不是 8中间留了 1 的缓冲避免某个桶的元素数在 8 附近反复横跳导致来回转换。hash 值一次高位异或// JDK 1.8 java.util.HashMap static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }把 hashCode 的高 16 位和低 16 位做异或结果还是 32 位。这一步叫扰动。它的目的不是让 hash 更随机。真正的原因是数组长度比较小的时候定位下标只用到低位高 16 位完全不参与。如果两个 key 的低位一样、高位不同它们会撞到同一个桶。异或之后高位的信息被混进了低位冲突概率就降下来了。HashMap 只在这一处做了扰动没有用多重哈希那种更重的算法。这是个取舍多花一次异或的代价换大部分场景下的冲突改善够了。定位下标用位与取代取模// JDK 1.8putVal 里的定位 // n table.length int index (n - 1) hash;取模的正经写法是hash % n。位运算比取模快但两者等价有个前提n必须是 2 的幂。n 是 16n-1是 15二进制1111。任何数跟1111做与运算结果就是它最低 4 位的值范围 0 到 15正好是取模的结果。n 是 10n-1是 9二进制1001。做与运算之后第 2 位和第 3 位永远是 0也就是说下标 2、3、4、5、6、7 里有好几个永远空着。一半的桶浪费了冲突率直接翻倍。这就是必须是 2 的幂最直接的技术理由。扩容这才是 2 的幂真正的价值这部分是被答得最薄的一层。容量从 16 扩到 32(n-1) hash里的掩码从1111变成11111多参与了一位。于是每个元素的新下标只有两种可能原下标不变或者原下标加上旧容量16。判断条件极简单看 hash 在那新增的一位上是 0 还是 1// JDK 1.8 resize 里的拆分逻辑简化后 if ((e.hash oldCap) 0) { // 新下标 原下标留在 lo 链 } else { // 新下标 原下标 oldCap进 hi 链 }一次位与就能决定去向不用重新算 hash不用重新取模。好处还不止省了一次运算。因为同一条链上的元素只可能分到两个桶里JDK 1.8 直接把原来那条链拆成 lo 和 hi 两条各自挂到新位置链上元素的相对顺序还能保持原样。这顺手解决了 1.7 头插法导致的扩容死循环问题。如果容量不是 2 的幂这套拆分逻辑完全不成立每个元素都得老老实实重算一遍模。扩容是 HashMap 最贵的操作成本翻一倍是很难接受的。顺带说初始化那件事。构造时传入的初始容量会被tableSizeFor往上取整到最近的 2 的幂// JDK 1.8把任意正整数变成 它的最小 2 的幂 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; }传入 1000得到 1024。但扩容阈值是1024 * 0.75 768放到第 769 个元素时就触发扩容了。所以想放 1000 个元素又不扩容初始值得写成1000 / 0.75 1约等于 1335。面试官在等的那句答完 (n-1)比取模快及格了。但这句话任何背过八股的人都会说没有区分度。真正让人抬眼的是这一句取模快只是顺带的收益2 的幂真正解决的是扩容成本。正因为容量翻倍时掩码只多一位每个元素的新下标只有两种可能判断只需要一次位与JDK 1.8 才能把一条链拆成两条直接搬走不用逐个 rehash。顺带说一句负载因子取 0.75 也是有依据的。源码注释里给了个数在理想的随机 hash 下桶里的元素数服从泊松分布负载因子 0.75 时链表长度达到 8 的概率大约是千万分之六小到可以忽略。所以 8 这个树化阈值不是拍脑袋定的。第二段尤其加分因为大多数人只会背默认 0.75说不出它是怎么来的。五个常见误区误区一以为 new HashMap(1000) 就不会扩容会扩。容量被上调到 1024但阈值是 1024 乘 0.75等于 768。要按预期元素数除以 0.75 再加 1 来给初始值。误区二以为链表长度超过 8 就树化还要数组长度达到 64。没到 64 时优先扩容因为那时候冲突多半是容量不够造成的。误区三以为元素少于 8 就从红黑树退回来退化阈值是 6。中间留的缓冲是为了避免在临界点反复转换。**误区四把扰动函数说成让哈希更均匀**它解决的是低位信息不足的问题。数组小的时候只有低几位参与运算高 16 位被混下来才有意义。**误区五以为 1.8 的 HashMap 线程不安全只是数据覆盖**死循环确实被尾插法解决了但并发 put 依然会丢数据并发扩容也有风险。要线程安全还是得用 ConcurrentHashMap。至于用 Hashtable我一般不选全表一把锁并发下退化得很厉害。这条看你们的具体场景我给不了死结论。速查表参数取值为什么默认初始容量162 的幂 (n-1)可用负载因子0.75泊松分布下链长达 8 概率约千万分之六扩容倍数2 倍掩码只多一位拆分成本最低树化阈值链表 8 且数组 ≥ 64优先扩容扩容解决不了再建树退化阈值6留缓冲避免临界反复转换扰动h ^ (h 16)让高 16 位参与低位运算关于本文HashMap 这条线还有几道没写为什么线程不安全、1.7 头插法死循环的完整过程、ConcurrentHashMap 从分段锁到 CAS 加 synchronized 的演进。J014 会讲 ConcurrentHashMap那篇和这篇连着看会顺很多。我会接着更新。感兴趣的话可以留个关注方便下次找。另外完整的十二个模块Java / C / Go / JVM / MySQL / Redis / MQ / 分布式 / 事务 / 网络 / 系统设计 / 项目深挖我整理成了一份手册每题都标了考察点和加分答法。【草丛后端架构】持续分享后端架构与底层原理。
