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