记得有次跟朋友聊哈希表他突然问了一句Hashtable扩容为什么是2倍1而不是直接2倍我当时愣了一下因为这问题表面上问的是一个扩容公式实际牵扯到的却是哈希表设计里最核心的三件事容量选择、取模分布、rehash代价。这篇文章就把这个问题彻底拆开来讲。不管你是准备面试还是在做底层存储、缓存类设计搞清楚它你对哈希表的理解都会往前走一大截。1. Hashtable的扩容规则到底长什么样1.1 翻倍1在源码里是怎么写的Hashtable是Java里最早出现的哈希表实现默认初始容量11默认负载因子0.75。当你往里放第9个元素时因为阈值是(int)(11 × 0.75) 8size一旦超过阈值就会触发扩容。Hashtable的扩容逻辑叫rehash()核心只有一句话新容量等于旧容量的2倍再加1。对应到源码大概是这个样子protected void rehash() { int oldCapacity table.length; Entry?,?[] oldMap table; // 这里就是那道“2倍1”公式 int newCapacity (oldCapacity 1) 1; if (newCapacity - MAX_ARRAY_SIZE 0) { if (oldCapacity MAX_ARRAY_SIZE) return; newCapacity MAX_ARRAY_SIZE; } Entry?,?[] newMap new Entry?,?[newCapacity]; modCount; threshold (int) Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE 1); table newMap; // 遍历旧表的所有桶和链表重新计算每个节点的下标 for (int i oldCapacity; i-- 0; ) { for (EntryK,V old oldMap[i]; old ! null; ) { EntryK,V e old; old old.next; int index (e.hash 0x7FFFFFFF) % newCapacity; e.next newMap[index]; newMap[index] e; } } }oldCapacity 1就是旧容量乘2再1所以称为2倍1扩容。真正决定元素位置的代码是这两行newCapacity (oldCapacity 1) 1和index (e.hash 0x7FFFFFFF) % newCapacity。注意 0x7FFFFFFF不是取绝对值而是把符号位清零。因为Math.abs(Integer.MIN_VALUE)仍然是负数不能直接当数组下标所以源码用位运算保证结果永远非负。这个细节很多人第一眼会忽略。1.2 三种容量策略的对比哈希表的容量选择业界其实有三条明显不同的路线实现初始容量扩容规则容量特征定位方式Hashtable11旧容量×21奇数多数时候接近素数按容量取模%HashMap16旧容量×2永远为2的幂按容量减1做位与部分C容器/教科书实现任意寻找下一个素数严格素数按容量取模%从这张表能看出Hashtable走的是“素数/奇数派”路线但没用“找下一个素数”这种严格做法而是找了一个计算成本极低的近似公式。HashMap走的是另一条路让容量永远为2的幂用(n - 1) hash替代取模运算速度更快但前提是哈希值本身要足够随机。搞清楚这三派就知道2倍1绝不是随手写的数字它是Hashtable在“素数质量”和“迁移开销”之间做的一个折中。2. 为什么容量要避开合数取模分布的决定性因素2.1 取模是如何决定元素的位置哈希表本质上就是一个数组元素最终落在哪个桶里靠的是“哈希值对数组长度取模”。下标 哈希值 % 数组长度。这个式子决定了不同长度的表对哈希值的“消化方式”完全不同。长度是2的幂时取模可以直接写成位运算但这意味着只有哈希值的低几位生效高位信息在进入桶之前就被扔掉了。长度是普通整数时必须老老实实做除法求余计算虽然慢一点但哈希值的每一位都对最终下标有贡献。这两者的差别在数据规律性面前会被急剧放大。用个生活类比把一批人按身高余数分配到门洞门洞高度是16那余数只能是0到15。但如果所有人的身高都是4的倍数那你永远只会在0、4、8、12这四个门洞见到人。规律本身和门洞高度不互质时分布就会塌缩。2.2 2的幂容量让哪些哈希值撞车以容量16为例hash 15只保留哈希值低4位。假设有一组对象的哈希值分别是0、4、8、12、16、20、24、28、32……取模16之后结果永远是0、4、8、12这四个数循环。也就是说数组里4个桶堆成链表其余12个桶完全空着。如果把容量放大到1024而数据步长是256那么哈希值取模1024后只会落在0、256、512、768四个桶。桶内链表越长查找性能下降越厉害退化速度远超预期。这种“数据步长刚好是容量因子”的情况在真实系统里一点都不罕见数据库自增ID按固定间隔生成、批量任务编号按块划分、内存分配按对齐地址组织、缓存行的连续数据写入都可能生产出这种规律性极强的哈希值。这些场景撞上2的幂容量几乎等于等着碰撞。2.3 素数容量为什么能摊平哈希的规律性把容量换成17同样一组0、4、8、12、16、20……取模17结果就变成了0、4、8、12、16、3、7、11、15、2、6、10、14、1、5、9、13。你会发现前17个数正好把0到16的所有桶全部踩了一遍一个都没落下然后才开始下一轮循环。原因很简单因为4和17互质。只要“步长”和“容量”互质这个等差数列在一轮遍历中就会覆盖全部槽位。容量是素数时任何不能被容量整除的步长都天然与容量互质所以素数容量对几乎所有规律性步长都有“免疫能力”。提示如果步长恰好等于容量当然还是会全部落到同一个桶。但现实中“步长恰好等于表长”发生的概率极低远低于“步长是2的幂倍数”这种对齐型灾难。选素数容量就是在用最小代价防御最高概率的坑。2.4 容量与哈希函数到底谁更决定分布质量大多数人把分布均匀归功于hashCode写得好这个理解只对了一半。hashCode均匀指的是它在整个int范围内均匀但落到具体的m个桶时还得靠取模来压缩。如果容量是2的幂压缩过程只保留低位高位信息等于白算。HashMap为什么要引入扰动函数把高16位异或到低16位就是为了救一把低位不够随机的情况。Hashtable没有做任何扰动它选择用素数容量来兜底。取模素数这个过程天然会让哈希值的高位参与最终下标计算。所以同一个平庸的哈希值序列放进Hashtable分布可能还行放进没有扰动的2的幂哈希表就会恶化。这不代表hashCode不重要而是说在你无法控制Key的哈希规律时素数容量是最后一层有效防御。3. 为什么是2倍1一个工程与数学的折中3.1 直接找下一个素数行不行如果只看“容量应该是素数”这个结论一个很自然的想法是那每次扩容时直接找下一个素数不就行了比如11下一个素数是13。这道数学题做起来没问题但工程上非常不划算。原因有三。第一11到13只增加2个槽位扩容阈值从8变成9几乎没留出多少缓冲空间很快又会触发下一次扩容。第二rehash本身就是全量迁移频繁扩容等于频繁做O(n)操作整体性能被拖垮。第三每次扩容都要额外做素数判定不管用试除法还是筛法都增加了不必要的计算开销。所以Hashtable选择了更聪明的近似方案不追求严格的素数表长只要求“容量变大、且变为奇数”。从11开始的扩容序列是11、23、47、95、191、383、767。其中11、23、47都是素数95是合数但95和767也都是奇数。奇数意味着排除了最危险的因子2已经躲开了大部分对齐型灾难。这就是2倍1公式存在的意义用极低的计算成本换一个接近素数的容量。3.2 2n1的奇数传承和相邻容量互质2倍1这个公式有两个非常重要的数学性质平时很少有人展开讲。第一个是“奇数传承”。如果旧容量是奇数那2 × 奇数 1 偶数 1 奇数所以新容量也一定是奇数。Hashtable初始容量11是奇数于是整个生命周期里的每一次扩容容量都永远是奇数。这保证了取模运算永远不会退化成只取低位的位与操作。第二个是“相邻容量互质”。设旧容量为n新容量为2n1。如果某个数d能同时整除n和2n1那么d也一定能整除(2n1) - 2n 1所以d只能是1。换句话说任意相邻两次扩容得到的容量一定互质。这意味着rehash时元素的新下标不会在旧下标附近简单平移而是被彻底打散近似重新做了一次均匀分布。从11到23从23到47从47到95每对相邻容量都互质迁移效果非常理想。3.3 配合0.75负载因子的实际效果Hashtable默认负载因子0.75不是随便定的。扩容阈值等于容量乘以负载因子向下取整。初始容量11时阈值是8元素到第9个触发扩容到23新阈值变成17再放18个元素时扩容到47。这个节奏保证了表内平均桶负载始终不高链表短查找近似常数时间。为什么0.75而不是0.5或者0.9因为0.5虽然链表更短但空间浪费一半0.9空间利用率高但链表开始变长冲突概率上升。0.75是多年工程经验沉淀出来的平衡点。Hashtable的2倍1扩容在0.75负载因子配合下每次扩容后都留出了接近当前容量一半的空余空间给后续插入留足缓冲。3.4 Hashtable为什么不换成HashMap那套2的幂方案这个问题要结合历史来看。Hashtable是JDK 1.0时期就出现的类扩容逻辑沿袭了传统教科书里“素数表长”的做法并且一直保持兼容。HashMap是JDK 1.2才出现的它出生得晚有空间选择更激进的2的幂方案配合位运算获得吞吐优势。官方后来没有大改Hashtable的底层原因也简单Hashtable是线程安全的方法都加了synchronized在今天的高并发场景里已经有更合适的替代品。既然不再承担主战场任务也就没必要把底层结构翻新一遍。所以我们不能简单说2倍1落后它代表的是哈希表设计里“素数容量派”的经典思路与HashMap的“位运算派”是两种哲学。4. 动手验证规律哈希在两种容量下的分布差异4.1 实验设计与模拟代码聊完理论我建议你亲自跑一遍验证。下面这段Java代码构造了68个规律哈希值分别是0、4、8、12……然后分别用容量16和容量17计算下标统计每个桶的元素数量。选择68是因为它同时覆盖了两种数据的多个循环能清晰看到差距。public class HashCapacityDemo { public static void main(String[] args) { int total 68; int[] buckets16 new int[16]; int[] buckets17 new int[17]; for (int i 0; i total; i) { int hash i * 4; // 容量16等价于只取低4位 buckets16[hash 15]; // 容量17素数取模 buckets17[Math.floorMod(hash, 17)]; } System.out.println( capacity16 (2的幂) ); for (int i 0; i 16; i) { System.out.println(bucket i : buckets16[i]); } System.out.println( capacity17 (素数) ); for (int i 0; i 17; i) { System.out.println(bucket i : buckets17[i]); } } }4.2 结果对比与解读运行结果按数学推导完全可预期容量16时0号桶17个元素、4号桶17个、8号桶17个、12号桶17个其余12个桶全是0。容量17时17个桶每个恰好4个元素。容量16分布容量17分布桶017每个桶4桶417每个桶4桶817每个桶4桶1217每个桶4其余12个桶0全部17个桶均匀覆盖这两种方案下的平均链表长度一个是17一个是4差距接近4倍。如果这是个缓存表容量16方案下某些尾部数据会一直命中长链表热点集中CPU缓存命中率也会很差容量17方案把热点摊到所有桶整体表现平稳得多。真实HashMap还会做一次扰动但扰动无法改变“步长是容量因子”这个根本结构冲突只能缓解随机性较好数据的下沉。4.3 为什么平时不容易感受到这种差异很多人用HashMap多年都没见过这种退化是因为String、UUID这类对象的hashCode在高位和低位都足够杂乱取模后依旧均匀。只有数值型Key、固定步长数据才容易露馅。我之前处理过一个批量导数据的模块主键是一组按固定间隔生成的ID。数据进入一个容量为2的幂的临时Map后某个桶的链表一度长到几千查询直接卡顿到秒级。后来把初始容量换成接近素数的值同样数据量下最长链表只有个位数。那次之后我对“容量影响分布”这件事有了真正的体感。5. 面试追问与日常避坑5.1 扩容后所有元素都要重新计算下标吗要。容量变了下标函数跟着变旧下标作废所有Entry必须重新计算。Hashtable的rehash会遍历旧表每个桶和每条链表用(hash 0x7FFFFFFF) % newCapacity算出新位置再头插进新表。整个过程是O(n)所以扩容是哈希表最主要的性能损耗点。HashMap在JDK 8里做了一点优化因为容量是2的幂元素的新位置要么是原下标要么是原下标加旧容量靠哈希值的某一位就能判断省掉了重新取模。Hashtable的容量不保证是2的幂享受不到这个红利。这也是它在极端场景下性能弱于HashMap的客观原因之一。5.2 2倍扩容一定比2倍1差吗不能这么简单下结论。HashMap的2倍扩容配合扰动函数与位运算在随机哈希数据上性能更优Hashtable的2倍1配合取模在规律性数据上分布更稳。它们解决的核心问题不同。真到了你自己设计哈希表的时候如果数据主键有明显对齐规律素数容量值得选如果数据哈希足够随机又追求极限速度2的幂加位运算更合适。5.3 面试怎么组织这道题的答案这道题面试里高频出现我建议按下面这条线回答第一步说明Hashtable用的是取模定位容量选择直接影响分布质量。第二步解释为什么容量要尽量是素数或奇数本质是规避数据步长与容量共因子导致的桶塌缩。第三步解释为什么不直接找下一个素数因为扩容增量小、还要做素数判定、频繁迁移不划算。第四步说明2倍1的两个性质奇数永远传承相邻容量必然互质。第五步对比HashMap的2的幂方案指出两种流派各有利弊。这样答既展示了源码细节又体现了对哈希表整体设计的理解。5.4 实战中如何决定自己的哈希表容量策略最后给几条实操建议。用Java干活时优先用HashMap或者ConcurrentHashMap没必要自己实现哈希表。如果确实需要自己设计哈希表或缓存先想清楚Key的步长是否规律规律性强就往素数容量靠。初始化容量别给100、1000这种整十合数给127、257、503这类素数或奇数成本几乎为零。自定义Key时认真实现hashCode容量策略只能兜底替代不了好哈希。大批量数据加载前提前估算元素总量和负载因子的关系尽量避免扩容。我记得第一次手推那段等差序列的取模表格时才真正理解“互质”这两个字在哈希表里的分量。后来在实际系统中遇到2的幂容量下链表疯长的案例再回头看这个面试题觉得它一点也不八股。它背后是一个很朴素的思想哈希表的性能不只由哈希函数决定表长大的数学性质同样关键。下次有人再问你这个问题别急着背答案把11和23、16和17这几个数字拿出来摆一摆答案其实全写在里面。