加關注可以第一時間接收數據結構系列文章，覺得不錯可以轉發和點贊，謝謝支持
通過上一節的學習，我們知道，散列表的查詢效率並不能籠統地說成是 O(1)。它跟散列函數、裝載因子、散列衝突等都有關係。如果散列函數設計得不好，或者裝載因子過高，都可能導致散列衝突發生的概率升高，查詢效率下降。
在極端情況下，有些惡意的攻擊者，還有可能通過精心構造的數據，使得所有的數據經過散列函數之後，都散列到同一個槽裡。如果我們使用的是基於鏈表的衝突解決方法，那這個時候，散列表就會退化為鏈表，查詢的時間複雜度就從 O(1) 急劇退化為 O(n)。
如果散列表中有 10 萬個數據，退化後的散列表查詢的效率就下降了 10 萬倍。更直接點說，如果之前運行 100 次查詢只需要 0.1 秒，那現在就需要 1 萬秒。這樣就有可能因為查詢操作消耗大量 CPU 或者線程資源，導致系統無法響應其他請求，從而達到拒絕服務攻擊（DoS）的目的。這也就是散列表碰撞攻擊的基本原理。
今天，我們就來學習一下，如何設計一個可以應對各種異常情況的工業級散列表，來避免在散列衝突的情況下，散列表性能的急劇下降，並且能抵抗散列碰撞攻擊？
如何設計散列函數？
散列函數設計的好壞，決定了散列表衝突的概率大小，也直接決定了散列表的性能。那什麼才是好的散列函數呢？
首先，散列函數的設計不能太複雜。過於複雜的散列函數，勢必會消耗很多計算時間，也就間接的影響到散列表的性能。其次，散列函數生成的值要儘可能隨機並且均勻分佈，這樣才能避免或者最小化散列衝突，而且即便出現衝突，散列到每個槽裡的數據也會比較平均，不會出現某個槽內數據特別多的情況。
實際工作中，我們還需要綜合考慮各種因素。這些因素有關鍵字的長度、特點、分佈、還有散列表的大小等。散列函數各式各樣，我舉幾個常用的、簡單的散列函數的設計方法，讓你有個直觀的感受。
第一個例子就是我們上一節的學生運動會的例子，我們通過分析參賽編號的特徵，把編號中的後兩位作為散列值。我們還可以用類似的散列函數處理手機號碼，因為手機號碼前幾位重複的可能性很大，但是後面幾位就比較隨機，我們可以取手機號的後四位作為散列值。這種散列函數的設計方法，我們一般叫作“數據分析法”。
第二個例子就是上一節的開篇思考題，如何實現 Word 拼寫檢查功能。這裡面的散列函數，我們就可以這樣設計：將單詞中每個字母的ASCll 碼值“進位”相加，然後再跟散列表的大小求餘、取模，作為散列值。比如，英文單詞 nice，我們轉化出來的散列值就是下面這樣：
hash("nice")=(("n" - "a") * 26*26*26 + ("i" - "a")*26*26 + ("c" - "a")*26+ ("e"-"a")) / 78978
實際上，散列函數的設計方法還有很多，比如直接尋址法、平方取中法、摺疊法、隨機數法等，這些你只要瞭解就行了，不需要全都掌握。
裝載因子過大了怎麼辦？
我們上一節講到散列表的裝載因子的時候說過，裝載因子越大，說明散列表中的元素越多，空閒位置越少，散列衝突的概率就越大。不僅插入數據的過程要多次尋址或者拉很長的鏈，查找的過程也會因此變得很慢。
對於沒有頻繁插入和刪除的靜態數據集合來說，我們很容易根據數據的特點、分佈等，設計出完美的、極少衝突的散列函數，因為畢竟之前數據都是已知的。
對於動態散列表來說，數據集合是頻繁變動的，我們事先無法預估將要加入的數據個數，所以我們也無法事先申請一個足夠大的散列表。隨著數據慢慢加入，裝載因子就會慢慢變大。當裝載因子大到一定程度之後，散列衝突就會變得不可接受。這個時候，我們該如何處理呢？
還記得我們前面多次講的“動態擴容”嗎？你可以回想一下，我們是如何做數組、棧、隊列的動態擴容的。
針對散列表，當裝載因子過大時，我們也可以進行動態擴容，重新申請一個更大的散列表，將數據搬移到這個新散列表中。假設每次擴容我們都申請一個原來散列表大小兩倍的空間。如果原來散列表的裝載因子是 0.8，那經過擴容之後，新散列表的裝載因子就下降為原來的一半，變成了 0.4。
針對數組的擴容，數據搬移操作比較簡單。但是，針對散列表的擴容，數據搬移操作要複雜很多。因為散列表的大小變了，數據的存儲位置也變了，所以我們需要通過散列函數重新計算每個數據的存儲位置。
你可以看我圖裡這個例子。在原來的散列表中，21 這個元素原來存儲在下標為 0 的位置，搬移到新的散列表中，存儲在下標為 7 的位置。
對於支持動態擴容的散列表，插入操作的時間複雜度是多少呢？前面章節我已經多次分析過支持動態擴容的數組、棧等數據結構的時間複雜度了。所以，這裡我就不囉嗦了，你要是還不清楚的話，可以回去複習一下。
插入一個數據，最好情況下，不需要擴容，最好時間複雜度是 O(1)。最壞情況下，散列表裝載因子過高，啟動擴容，我們需要重新申請內存空間，重新計算哈希位置，並且搬移數據，所以時間複雜度是 O(n)。用攤還分析法，均攤情況下，時間複雜度接近最好情況，就是 O(1)。
實際上，對於動態散列表，隨著數據的刪除，散列表中的數據會越來越少，空閒空間會越來越多。如果我們對空間消耗非常敏感，我們可以在裝載因子小於某個值之後，啟動動態縮容。當然，如果我們更加在意執行效率，能夠容忍多消耗一點內存空間，那就可以不用費勁來縮容了。
我們前面講到，當散列表的裝載因子超過某個閾值時，就需要進行擴容。裝載因子閾值需要選擇得當。如果太大，會導致衝突過多；如果太小，會導致內存浪費嚴重。
裝載因子閾值的設置要權衡時間、空間複雜度。如果內存空間不緊張，對執行效率要求很高，可以降低負載因子的閾值；相反，如果內存空間緊張，對執行效率要求又不高，可以增加負載因子的值，甚至可以大於 1。
如何避免低效地擴容？
我們剛剛分析得到，大部分情況下，動態擴容的散列表插入一個數據都很快，但是在特殊情況下，當裝載因子已經到達閾值，需要先進行擴容，再插入數據。這個時候，插入數據就會變得很慢，甚至會無法接受。
我舉一個極端的例子，如果散列表當前大小為 1GB，要想擴容為原來的兩倍大小，那就需要對 1GB 的數據重新計算哈希值，並且從原來的散列表搬移到新的散列表，聽起來就很耗時，是不是？
如果我們的業務代碼直接服務於用戶，儘管大部分情況下，插入一個數據的操作都很快，但是，極個別非常慢的插入操作，也會讓用戶崩潰。這個時候，“一次性”擴容的機制就不合適了。
為了解決一次性擴容耗時過多的情況，我們可以將擴容操作穿插在插入操作的過程中，分批完成。當裝載因子觸達閾值之後，我們只申請新空間，但並不將老的數據搬移到新散列表中。
當有新數據要插入時，我們將新數據插入新散列表中，並且從老的散列表中拿出一個數據放入到新散列表。每次插入一個數據到散列表，我們都重複上面的過程。經過多次插入操作之後，老的散列表中的數據就一點一點全部搬移到新散列表中了。這樣沒有了集中的一次性數據搬移，插入操作就都變得很快了。
這期間的查詢操作怎麼來做呢？對於查詢操作，為了兼容了新、老散列表中的數據，我們先從新散列表中查找，如果沒有找到，再去老的散列表中查找。
通過這樣均攤的方法，將一次性擴容的代價，均攤到多次插入操作中，就避免了一次性擴容耗時過多的情況。這種實現方式，任何情況下，插入一個數據的時間複雜度都是 O(1)。
如何選擇衝突解決方法？
上一節我們講了兩種主要的散列衝突的解決辦法，開放尋址法和鏈表法。這兩種衝突解決辦法在實際的軟件開發中都非常常用。比如，Java 中 LinkedHashMap 就採用了鏈表法解決衝突，ThreadLocalMap 是通過線性探測的開放尋址法來解決衝突。那你知道，這兩種衝突解決方法各有什麼優勢和劣勢，又各自適用哪些場景嗎？
1. 開放尋址法
我們先來看看，開放尋址法的優點有哪些。
開放尋址法不像鏈表法，需要拉很多鏈表。散列表中的數據都存儲在數組中，可以有效地利用 CPU 緩存加快查詢速度。而且，這種方法實現的散列表，序列化起來比較簡單。鏈表法包含指針，序列化起來就沒那麼容易。你可不要小看序列化，很多場合都會用到的。我們後面就有一節會講什麼是數據結構序列化、如何序列化，以及為什麼要序列化。
我們再來看下，開放尋址法有哪些缺點。
上一節我們講到，用開放尋址法解決衝突的散列表，刪除數據的時候比較麻煩，需要特殊標記已經刪除掉的數據。而且，在開放尋址法中，所有的數據都存儲在一個數組中，比起鏈表法來說，衝突的代價更高。所以，使用開放尋址法解決衝突的散列表，裝載因子的上限不能太大。這也導致這種方法比鏈表法更浪費內存空間。
所以，我總結一下，當數據量比較小、裝載因子小的時候，適合採用開放尋址法。這也是 Java 中的ThreadLocalMap使用開放尋址法解決散列衝突的原因。
2. 鏈表法
首先，鏈表法對內存的利用率比開放尋址法要高。因為鏈表結點可以在需要的時候再創建，並不需要像開放尋址法那樣事先申請好。實際上，這一點也是我們前面講過的鏈表優於數組的地方。
鏈表法比起開放尋址法，對大裝載因子的容忍度更高。開放尋址法只能適用裝載因子小於 1 的情況。接近 1 時，就可能會有大量的散列衝突，導致大量的探測、再散列等，性能會下降很多。但是對於鏈表法來說，只要散列函數的值隨機均勻，即便裝載因子變成 10，也就是鏈表的長度變長了而已，雖然查找效率有所下降，但是比起順序查找還是快很多。
還記得我們之前在鏈表那一節講的嗎？鏈表因為要存儲指針，所以對於比較小的對象的存儲，是比較消耗內存的，還有可能會讓內存的消耗翻倍。而且，因為鏈表中的結點是零散分佈在內存中的，不是連續的，所以對 CPU 緩存是不友好的，這方面對於執行效率也有一定的影響。
當然，如果我們存儲的是大對象，也就是說要存儲的對象的大小遠遠大於一個指針的大小（4 個字節或者 8 個字節），那鏈表中指針的內存消耗在大對象面前就可以忽略了。
實際上，我們對鏈表法稍加改造，可以實現一個更加高效的散列表。那就是，我們將鏈表法中的鏈表改造為其他高效的動態數據結構，比如跳錶、紅黑樹。這樣，即便出現散列衝突，極端情況下，所有的數據都散列到同一個桶內，那最終退化成的散列表的查找時間也只不過是 O(logn)。這樣也就有效避免了前面講到的散列碰撞攻擊。
所以，我總結一下，基於鏈表的散列衝突處理方法比較適合存儲大對象、大數據量的散列表，而且，比起開放尋址法，它更加靈活，支持更多的優化策略，比如用紅黑樹代替鏈表。
工業級散列表舉例分析
剛剛我講了實現一個工業級散列表需要涉及的一些關鍵技術，現在，我就拿一個具體的例子，Java 中的 HashMap 這樣一個工業級的散列表，來具體看下，這些技術是怎麼應用的。
1. 初始大小
HashMap 默認的初始大小是 16，當然這個默認值是可以設置的，如果事先知道大概的數據量有多大，可以通過修改默認初始大小，減少動態擴容的次數，這樣會大大提高 HashMap 的性能。
2. 裝載因子和動態擴容
最大裝載因子默認是 0.75，當 HashMap 中元素個數超過 0.75*capacity（capacity 表示散列表的容量）的時候，就會啟動擴容，每次擴容都會擴容為原來的兩倍大小。
3. 散列衝突解決方法
HashMap 底層採用鏈表法來解決衝突。即使負載因子和散列函數設計得再合理，也免不了會出現拉鍊過長的情況，一旦出現拉鍊過長，則會嚴重影響 HashMap 的性能。
於是，在 JDK1.8 版本中，為了對 HashMap 做進一步優化，我們引入了紅黑樹。而當鏈表長度太長（默認超過 8）時，鏈表就轉換為紅黑樹。我們可以利用紅黑樹快速增刪改查的特點，提高 HashMap 的性能。當紅黑樹結點個數少於 8 個的時候，又會將紅黑樹轉化為鏈表。因為在數據量較小的情況下，紅黑樹要維護平衡，比起鏈表來，性能上的優勢並不明顯。
4. 散列函數
散列函數的設計並不複雜，追求的是簡單高效、分佈均勻。我把它摘抄出來，你可以看看。
int hash(Object key) {
int h = key.hashCode()；
return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
}
其中，hashCode() 返回的是 Java 對象的 hash code。比如 String 類型的對象的 hashCode() 就是下面這樣：
public int hashCode() {
int var1 = this.hash;
if(var1 == 0 && this.value.length > 0) {
char[] var2 = this.value;
for(int var3 = 0; var3 < this.value.length; ++var3) {
var1 = 31 * var1 + var2[var3];
}
this.hash = var1;
}
return var1;
}
解答開篇
今天的內容就講完了，我現在來分析一下開篇的問題：如何設計的一個工業級的散列函數？如果這是一道面試題或者是擺在你面前的實際開發問題，你會從哪幾個方面思考呢？
首先，我會思考，何為一個工業級的散列表？工業級的散列表應該具有哪些特性？
結合已經學習過的散列知識，我覺得應該有這樣幾點要求：
支持快速的查詢、插入、刪除操作；
內存佔用合理，不能浪費過多的內存空間；
性能穩定，極端情況下，散列表的性能也不會退化到無法接受的情況。
如何實現這樣一個散列表呢？根據前面講到的知識，我會從這三個方面來考慮設計思路：
設計一個合適的散列函數；
定義裝載因子閾值，並且設計動態擴容策略；
選擇合適的散列衝突解決方法。
關於散列函數、裝載因子、動態擴容策略，還有散列衝突的解決辦法，我們前面都講過了，具體如何選擇，還要結合具體的業務場景、具體的業務數據來具體分析。不過只要我們朝這三個方向努力，就離設計出工業級的散列表不遠了。
內容小結
上一節的內容比較偏理論，今天的內容側重實戰。我主要講了如何設計一個工業級的散列表，以及如何應對各種異常情況，防止在極端情況下，散列表的性能退化過於嚴重。我分了三部分來講解這些內容，分別是：如何設計散列函數，如何根據裝載因子動態擴容，以及如何選擇散列衝突解決方法。
關於散列函數的設計，我們要儘可能讓散列後的值隨機且均勻分佈，這樣會盡可能地減少散列衝突，即便衝突之後，分配到每個槽內的數據也比較均勻。除此之外，散列函數的設計也不能太複雜，太複雜就會太耗時間，也會影響散列表的性能。
關於散列衝突解決方法的選擇，我對比了開放尋址法和鏈表法兩種方法的優劣和適應的場景。大部分情況下，鏈表法更加普適。而且，我們還可以通過將鏈表法中的鏈表改造成其他動態查找數據結構，比如紅黑樹，來避免散列表時間複雜度退化成 O(n)，抵禦散列碰撞攻擊。但是，對於小規模數據、裝載因子不高的散列表，比較適合用開放尋址法。
對於動態散列表來說，不管我們如何設計散列函數，選擇什麼樣的散列衝突解決方法。隨著數據的不斷增加，散列表總會出現裝載因子過高的情況。這個時候，我們就需要啟動動態擴容。
閱讀更多 xiuxiuing 的文章
