記得有次跟朋友聊哈希表他突然問了一句Hashtable擴容為什么是2倍1而不是直接2倍我當時愣了一下因為這問題表面上問的是一個擴容公式實際牽扯到的卻是哈希表設(shè)計里最核心的三件事容量選擇、取模分布、rehash代價。這篇文章就把這個問題徹底拆開來講。不管你是準備面試還是在做底層存儲、緩存類設(shè)計搞清楚它你對哈希表的理解都會往前走一大截。1. Hashtable的擴容規(guī)則到底長什么樣1.1 翻倍1在源碼里是怎么寫的Hashtable是Java里最早出現(xiàn)的哈希表實現(xiàn)默認初始容量11默認負載因子0.75。當你往里放第9個元素時因為閾值是(int)(11 × 0.75) 8size一旦超過閾值就會觸發(fā)擴容。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; // 遍歷舊表的所有桶和鏈表重新計算每個節(jié)點的下標 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)仍然是負數(shù)不能直接當數(shù)組下標所以源碼用位運算保證結(jié)果永遠非負。這個細節(jié)很多人第一眼會忽略。1.2 三種容量策略的對比哈希表的容量選擇業(yè)界其實有三條明顯不同的路線實現(xiàn)初始容量擴容規(guī)則容量特征定位方式Hashtable11舊容量×21奇數(shù)多數(shù)時候接近素數(shù)按容量取模%HashMap16舊容量×2永遠為2的冪按容量減1做位與部分C容器/教科書實現(xiàn)任意尋找下一個素數(shù)嚴格素數(shù)按容量取模%從這張表能看出Hashtable走的是“素數(shù)/奇數(shù)派”路線但沒用“找下一個素數(shù)”這種嚴格做法而是找了一個計算成本極低的近似公式。HashMap走的是另一條路讓容量永遠為2的冪用(n - 1) hash替代取模運算速度更快但前提是哈希值本身要足夠隨機。搞清楚這三派就知道2倍1絕不是隨手寫的數(shù)字它是Hashtable在“素數(shù)質(zhì)量”和“遷移開銷”之間做的一個折中。2. 為什么容量要避開合數(shù)取模分布的決定性因素2.1 取模是如何決定元素的位置哈希表本質(zhì)上就是一個數(shù)組元素最終落在哪個桶里靠的是“哈希值對數(shù)組長度取?！?。下標 哈希值 % 數(shù)組長度。這個式子決定了不同長度的表對哈希值的“消化方式”完全不同。長度是2的冪時取?？梢灾苯訉懗晌贿\算但這意味著只有哈希值的低幾位生效高位信息在進入桶之前就被扔掉了。長度是普通整數(shù)時必須老老實實做除法求余計算雖然慢一點但哈希值的每一位都對最終下標有貢獻。這兩者的差別在數(shù)據(jù)規(guī)律性面前會被急劇放大。用個生活類比把一批人按身高余數(shù)分配到門洞門洞高度是16那余數(shù)只能是0到15。但如果所有人的身高都是4的倍數(shù)那你永遠只會在0、4、8、12這四個門洞見到人。規(guī)律本身和門洞高度不互質(zhì)時分布就會塌縮。2.2 2的冪容量讓哪些哈希值撞車以容量16為例hash 15只保留哈希值低4位。假設(shè)有一組對象的哈希值分別是0、4、8、12、16、20、24、28、32……取模16之后結(jié)果永遠是0、4、8、12這四個數(shù)循環(huán)。也就是說數(shù)組里4個桶堆成鏈表其余12個桶完全空著。如果把容量放大到1024而數(shù)據(jù)步長是256那么哈希值取模1024后只會落在0、256、512、768四個桶。桶內(nèi)鏈表越長查找性能下降越厲害退化速度遠超預期。這種“數(shù)據(jù)步長剛好是容量因子”的情況在真實系統(tǒng)里一點都不罕見數(shù)據(jù)庫自增ID按固定間隔生成、批量任務編號按塊劃分、內(nèi)存分配按對齊地址組織、緩存行的連續(xù)數(shù)據(jù)寫入都可能生產(chǎn)出這種規(guī)律性極強的哈希值。這些場景撞上2的冪容量幾乎等于等著碰撞。2.3 素數(shù)容量為什么能攤平哈希的規(guī)律性把容量換成17同樣一組0、4、8、12、16、20……取模17結(jié)果就變成了0、4、8、12、16、3、7、11、15、2、6、10、14、1、5、9、13。你會發(fā)現(xiàn)前17個數(shù)正好把0到16的所有桶全部踩了一遍一個都沒落下然后才開始下一輪循環(huán)。原因很簡單因為4和17互質(zhì)。只要“步長”和“容量”互質(zhì)這個等差數(shù)列在一輪遍歷中就會覆蓋全部槽位。容量是素數(shù)時任何不能被容量整除的步長都天然與容量互質(zhì)所以素數(shù)容量對幾乎所有規(guī)律性步長都有“免疫能力”。提示如果步長恰好等于容量當然還是會全部落到同一個桶。但現(xiàn)實中“步長恰好等于表長”發(fā)生的概率極低遠低于“步長是2的冪倍數(shù)”這種對齊型災難。選素數(shù)容量就是在用最小代價防御最高概率的坑。2.4 容量與哈希函數(shù)到底誰更決定分布質(zhì)量大多數(shù)人把分布均勻歸功于hashCode寫得好這個理解只對了一半。hashCode均勻指的是它在整個int范圍內(nèi)均勻但落到具體的m個桶時還得靠取模來壓縮。如果容量是2的冪壓縮過程只保留低位高位信息等于白算。HashMap為什么要引入擾動函數(shù)把高16位異或到低16位就是為了救一把低位不夠隨機的情況。Hashtable沒有做任何擾動它選擇用素數(shù)容量來兜底。取模素數(shù)這個過程天然會讓哈希值的高位參與最終下標計算。所以同一個平庸的哈希值序列放進Hashtable分布可能還行放進沒有擾動的2的冪哈希表就會惡化。這不代表hashCode不重要而是說在你無法控制Key的哈希規(guī)律時素數(shù)容量是最后一層有效防御。3. 為什么是2倍1一個工程與數(shù)學的折中3.1 直接找下一個素數(shù)行不行如果只看“容量應該是素數(shù)”這個結(jié)論一個很自然的想法是那每次擴容時直接找下一個素數(shù)不就行了比如11下一個素數(shù)是13。這道數(shù)學題做起來沒問題但工程上非常不劃算。原因有三。第一11到13只增加2個槽位擴容閾值從8變成9幾乎沒留出多少緩沖空間很快又會觸發(fā)下一次擴容。第二rehash本身就是全量遷移頻繁擴容等于頻繁做O(n)操作整體性能被拖垮。第三每次擴容都要額外做素數(shù)判定不管用試除法還是篩法都增加了不必要的計算開銷。所以Hashtable選擇了更聰明的近似方案不追求嚴格的素數(shù)表長只要求“容量變大、且變?yōu)槠鏀?shù)”。從11開始的擴容序列是11、23、47、95、191、383、767。其中11、23、47都是素數(shù)95是合數(shù)但95和767也都是奇數(shù)。奇數(shù)意味著排除了最危險的因子2已經(jīng)躲開了大部分對齊型災難。這就是2倍1公式存在的意義用極低的計算成本換一個接近素數(shù)的容量。3.2 2n1的奇數(shù)傳承和相鄰容量互質(zhì)2倍1這個公式有兩個非常重要的數(shù)學性質(zhì)平時很少有人展開講。第一個是“奇數(shù)傳承”。如果舊容量是奇數(shù)那2 × 奇數(shù) 1 偶數(shù) 1 奇數(shù)所以新容量也一定是奇數(shù)。Hashtable初始容量11是奇數(shù)于是整個生命周期里的每一次擴容容量都永遠是奇數(shù)。這保證了取模運算永遠不會退化成只取低位的位與操作。第二個是“相鄰容量互質(zhì)”。設(shè)舊容量為n新容量為2n1。如果某個數(shù)d能同時整除n和2n1那么d也一定能整除(2n1) - 2n 1所以d只能是1。換句話說任意相鄰兩次擴容得到的容量一定互質(zhì)。這意味著rehash時元素的新下標不會在舊下標附近簡單平移而是被徹底打散近似重新做了一次均勻分布。從11到23從23到47從47到95每對相鄰容量都互質(zhì)遷移效果非常理想。3.3 配合0.75負載因子的實際效果Hashtable默認負載因子0.75不是隨便定的。擴容閾值等于容量乘以負載因子向下取整。初始容量11時閾值是8元素到第9個觸發(fā)擴容到23新閾值變成17再放18個元素時擴容到47。這個節(jié)奏保證了表內(nèi)平均桶負載始終不高鏈表短查找近似常數(shù)時間。為什么0.75而不是0.5或者0.9因為0.5雖然鏈表更短但空間浪費一半0.9空間利用率高但鏈表開始變長沖突概率上升。0.75是多年工程經(jīng)驗沉淀出來的平衡點。Hashtable的2倍1擴容在0.75負載因子配合下每次擴容后都留出了接近當前容量一半的空余空間給后續(xù)插入留足緩沖。3.4 Hashtable為什么不換成HashMap那套2的冪方案這個問題要結(jié)合歷史來看。Hashtable是JDK 1.0時期就出現(xiàn)的類擴容邏輯沿襲了傳統(tǒng)教科書里“素數(shù)表長”的做法并且一直保持兼容。HashMap是JDK 1.2才出現(xiàn)的它出生得晚有空間選擇更激進的2的冪方案配合位運算獲得吞吐優(yōu)勢。官方后來沒有大改Hashtable的底層原因也簡單Hashtable是線程安全的方法都加了synchronized在今天的高并發(fā)場景里已經(jīng)有更合適的替代品。既然不再承擔主戰(zhàn)場任務也就沒必要把底層結(jié)構(gòu)翻新一遍。所以我們不能簡單說2倍1落后它代表的是哈希表設(shè)計里“素數(shù)容量派”的經(jīng)典思路與HashMap的“位運算派”是兩種哲學。4. 動手驗證規(guī)律哈希在兩種容量下的分布差異4.1 實驗設(shè)計與模擬代碼聊完理論我建議你親自跑一遍驗證。下面這段Java代碼構(gòu)造了68個規(guī)律哈希值分別是0、4、8、12……然后分別用容量16和容量17計算下標統(tǒng)計每個桶的元素數(shù)量。選擇68是因為它同時覆蓋了兩種數(shù)據(jù)的多個循環(huán)能清晰看到差距。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素數(shù)取模 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 (素數(shù)) ); for (int i 0; i 17; i) { System.out.println(bucket i : buckets17[i]); } } }4.2 結(jié)果對比與解讀運行結(jié)果按數(shù)學推導完全可預期容量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方案下某些尾部數(shù)據(jù)會一直命中長鏈表熱點集中CPU緩存命中率也會很差容量17方案把熱點攤到所有桶整體表現(xiàn)平穩(wěn)得多。真實HashMap還會做一次擾動但擾動無法改變“步長是容量因子”這個根本結(jié)構(gòu)沖突只能緩解隨機性較好數(shù)據(jù)的下沉。4.3 為什么平時不容易感受到這種差異很多人用HashMap多年都沒見過這種退化是因為String、UUID這類對象的hashCode在高位和低位都足夠雜亂取模后依舊均勻。只有數(shù)值型Key、固定步長數(shù)據(jù)才容易露餡。我之前處理過一個批量導數(shù)據(jù)的模塊主鍵是一組按固定間隔生成的ID。數(shù)據(jù)進入一個容量為2的冪的臨時Map后某個桶的鏈表一度長到幾千查詢直接卡頓到秒級。后來把初始容量換成接近素數(shù)的值同樣數(shù)據(jù)量下最長鏈表只有個位數(shù)。那次之后我對“容量影響分布”這件事有了真正的體感。5. 面試追問與日常避坑5.1 擴容后所有元素都要重新計算下標嗎要。容量變了下標函數(shù)跟著變舊下標作廢所有Entry必須重新計算。Hashtable的rehash會遍歷舊表每個桶和每條鏈表用(hash 0x7FFFFFFF) % newCapacity算出新位置再頭插進新表。整個過程是O(n)所以擴容是哈希表最主要的性能損耗點。HashMap在JDK 8里做了一點優(yōu)化因為容量是2的冪元素的新位置要么是原下標要么是原下標加舊容量靠哈希值的某一位就能判斷省掉了重新取模。Hashtable的容量不保證是2的冪享受不到這個紅利。這也是它在極端場景下性能弱于HashMap的客觀原因之一。5.2 2倍擴容一定比2倍1差嗎不能這么簡單下結(jié)論。HashMap的2倍擴容配合擾動函數(shù)與位運算在隨機哈希數(shù)據(jù)上性能更優(yōu)Hashtable的2倍1配合取模在規(guī)律性數(shù)據(jù)上分布更穩(wěn)。它們解決的核心問題不同。真到了你自己設(shè)計哈希表的時候如果數(shù)據(jù)主鍵有明顯對齊規(guī)律素數(shù)容量值得選如果數(shù)據(jù)哈希足夠隨機又追求極限速度2的冪加位運算更合適。5.3 面試怎么組織這道題的答案這道題面試里高頻出現(xiàn)我建議按下面這條線回答第一步說明Hashtable用的是取模定位容量選擇直接影響分布質(zhì)量。第二步解釋為什么容量要盡量是素數(shù)或奇數(shù)本質(zhì)是規(guī)避數(shù)據(jù)步長與容量共因子導致的桶塌縮。第三步解釋為什么不直接找下一個素數(shù)因為擴容增量小、還要做素數(shù)判定、頻繁遷移不劃算。第四步說明2倍1的兩個性質(zhì)奇數(shù)永遠傳承相鄰容量必然互質(zhì)。第五步對比HashMap的2的冪方案指出兩種流派各有利弊。這樣答既展示了源碼細節(jié)又體現(xiàn)了對哈希表整體設(shè)計的理解。5.4 實戰(zhàn)中如何決定自己的哈希表容量策略最后給幾條實操建議。用Java干活時優(yōu)先用HashMap或者ConcurrentHashMap沒必要自己實現(xiàn)哈希表。如果確實需要自己設(shè)計哈希表或緩存先想清楚Key的步長是否規(guī)律規(guī)律性強就往素數(shù)容量靠。初始化容量別給100、1000這種整十合數(shù)給127、257、503這類素數(shù)或奇數(shù)成本幾乎為零。自定義Key時認真實現(xiàn)hashCode容量策略只能兜底替代不了好哈希。大批量數(shù)據(jù)加載前提前估算元素總量和負載因子的關(guān)系盡量避免擴容。我記得第一次手推那段等差序列的取模表格時才真正理解“互質(zhì)”這兩個字在哈希表里的分量。后來在實際系統(tǒng)中遇到2的冪容量下鏈表瘋長的案例再回頭看這個面試題覺得它一點也不八股。它背后是一個很樸素的思想哈希表的性能不只由哈希函數(shù)決定表長大的數(shù)學性質(zhì)同樣關(guān)鍵。下次有人再問你這個問題別急著背答案把11和23、16和17這幾個數(shù)字拿出來擺一擺答案其實全寫在里面。