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