通過上一節(jié)的學習，我們知道，散列表的查詢效率并不能籠統(tǒng)地說成是 O(1)。它跟散列函數、裝載因子、散列沖突等都有關系。如果散列函數設計得不好，或者裝載因子過高，都可能導致散列沖突發(fā)生的概率升高，查詢效率下降。極端情況下，散列表就會退化為鏈表，查詢的時間復雜度就從 O(1) 急劇退化為 O(n)。

今天，來學習一下，如何設計一個可以應對各種異常情況的工業(yè)級散列表，來避免在散列沖突的情況下，散列表性能的急劇下降，并且能抵抗散列碰撞攻擊？

如何設計散列函數？

散列函數設計的好壞，決定了散列表沖突的概率大小，也直接決定了散列表的性能。那什么才是好的散列函數呢？

• 首先，散列函數的設計不能太復雜。過于復雜的散列函數，勢必會消耗很多計算時間，也就間接的影響到散列表的性能。

• 其次，散列函數生成的值要盡可能隨機并且均勻分布，這樣才能避免或者最小化散列沖突，而且即便出現沖突，散列到每個槽里的數據也會比較平均，不會出現某個槽內數據特別多的情況。

實際工作中，我們還需要綜合考慮各種因素。這些因素有關鍵字的長度、特點、分布、還有散列表的大小等。

散列函數的設計方法還有很多，比如直接尋址法、平方取中法、折疊法、隨機數法等，這些你只要了解就行了，不需要全都掌握。

裝載因子過大了怎么辦？

裝載因子越大，說明散列表中的元素越多，空閑位置越少，散列沖突的概率就越大。

不僅插入數據的過程要多次尋址或者拉很長的鏈，查找的過程也會因此變得很慢。

對于動態(tài)散列表來說，數據集合是頻繁變動的，我們事先無法預估將要加入的數據個數，所以我們也無法事先申請一個足夠大的散列表。隨著數據慢慢加入，裝載因子就會慢慢變大。當裝載因子大到一定程度之后，散列沖突就會變得不可接受。這個時候，我們該如何處理呢?

針對散列表，當裝載因子過大，超過某個閾值時，我們可以進行動態(tài)擴容，重新申請一個更大的散列表，將數據搬移到這個新散列表中（即一次性擴容，為低效擴容）。因為散列表的大小變了，數據的存儲位置也變了，所以我們需要通過散列函數重新計算每個數據的存儲位置。

實際上，對于動態(tài)散列表，隨著數據的刪除，散列表中的數據會越來越少，空閑空間會越來越多。如果我們對空間消耗非常敏感，我們可以在裝載因子小于某個值之后，啟動動態(tài)縮容。當然，如果我們更加在意執(zhí)行效率，能夠容忍多消耗一點內存空間，那就可以不用費勁來縮容了。

前面講到，當散列表的裝載因子超過某個閾值時，就需要進行擴容。裝載因子閾值需要選擇得當。如果太大，會導致沖突過多；如果太小，會導致內存浪費嚴重。

裝載因子閾值的設置要權衡時間、空間復雜度。如果內存空間不緊張，對執(zhí)行效率要求很高，可以降低負載因子的閾值；相反，如果內存空間緊張，對執(zhí)行效率要求又不高，可以增加負載因子的值，甚至可以大于 1。

如何避免低效地擴容？

大部分情況下，動態(tài)擴容的散列表插入一個數據都很快，但是在特殊情況下，當裝載因子已經到達閾值，需要先進行擴容，再插入數據，即一次性擴容。這個時候，插入數據就會變得很慢，甚至會無法接受。

為了解決一次性擴容耗時過多的情況，我們可以將擴容操作穿插在插入操作的過程中，分批完成。當裝載因子觸達閾值之后，我們只申請新空間，但并不將老的數據搬移到新散列表中。

當有新數據要插入時，我們將新數據插入新散列表中，并且從老的散列表中拿出一個數據放入到新散列表。每次插入一個數據到散列表，我們都重復上面的過程。經過多次插入操作之后，老的散列表中的數據就一點一點全部搬移到新散列表中了。這樣沒有了集中的一次性數據搬移，插入操作就都變得很快了。

這期間的查詢操作怎么來做呢？對于查詢操作，為了兼容了新、老散列表中的數據，我們先從新散列表中查找，如果沒有找到，再去老的散列表中查找。

通過這樣均攤的方法，將一次性擴容的代價，均攤到多次插入操作中，就避免了一次性擴容耗時過多的情況。這種實現方式，任何情況下，插入一個數據的時間復雜度都是 O(1)。

如何選擇沖突解決方法？

開放尋址法和鏈表法，這兩種沖突解決辦法在實際的軟件開發(fā)中都非常常用。比如，Java 中 LinkedHashMap 就采用了鏈表法解決沖突，ThreadLocalMap 是通過線性探測的開放尋址法來解決沖突。那你知道，這兩種沖突解決方法各有什么優(yōu)勢和劣勢，又各自適用哪些場景嗎？

1. 開放尋址法

優(yōu)：散列表中的數據都存儲在數組中，可以有效地利用 CPU 緩存加快查詢速度。而且，這種方法實現的散列表，序列化起來比較簡單。

缺：刪除數據的時候比較麻煩，需要特殊標記已經刪除掉的數據。而且，在開放尋址法中，所有的數據都存儲在一個數組中，比起鏈表法來說，沖突的代價更高。所以，使用開放尋址法解決沖突的散列表，裝載因子的上限不能太大。這也導致這種方法比鏈表法更浪費內存空間。

總結：當數據量比較小、裝載因子小的時候，適合采用開放尋址法。這也是 Java 中的 ThreadLocalMap 使用開放尋址法解決散列沖突的原因。

2. 鏈表法

優(yōu)：首先，鏈表法對內存的利用率比開放尋址法要高。因為鏈表結點可以在需要的時候再創(chuàng)建，并不需要像開放尋址法那樣事先申請好。這一點也是鏈表優(yōu)于數組的地方。

鏈表法比起開放尋址法，對大裝載因子的容忍度更高。開放尋址法只能適用裝載因子小于 1 的情況。接近 1 時，就可能會有大量的散列沖突，導致大量的探測、再散列等，性能會下降很多。但是對于鏈表法來說，只要散列函數的值隨機均勻，即便裝載因子變成 10，也就是鏈表的長度變長了而已，雖然查找效率有所下降，但是比起順序查找還是快很多。

缺：鏈表因為要存儲指針，所以對于比較小的對象的存儲，是比較消耗內存的，還有可能會讓內存的消耗翻倍。而且，因為鏈表中的結點是零散分布在內存中的，不是連續(xù)的，所以對 CPU 緩存是不友好的，這方面對于執(zhí)行效率也有一定的影響。

當然，如果我們存儲的是大對象，也就是說要存儲的對象的大小遠遠大于一個指針的大?。? 個字節(jié)或者 8 個字節(jié)），那鏈表中指針的內存消耗在大對象面前就可以忽略了。

實際上，我們對鏈表法稍加改造，可以實現一個更加高效的散列表。那就是，我們將鏈表法中的鏈表改造為其他高效的動態(tài)數據結構，比如跳表、紅黑樹。這樣，即便出現散列沖突，極端情況下，所有的數據都散列到同一個桶內，那最終退化成的散列表的查找時間也只不過是 O(logn)。這樣也就有效避免了前面講到的散列碰撞攻擊。

總結：基于鏈表的散列沖突處理方法比較適合存儲大對象、大數據量的散列表，而且，比起開放尋址法，它更加靈活，支持更多的優(yōu)化策略，比如用紅黑樹代替鏈表。

工業(yè)級散列表舉例分析

剛剛講了實現一個工業(yè)級散列表需要涉及的一些關鍵技術，現在就拿一個具體的例子，Java 中的 HashMap 這樣一個工業(yè)級的散列表，來具體看下，這些技術是怎么應用的。

• 初始大小

HashMap 默認的初始大小是 16，當然這個默認值是可以設置的，如果事先知道大概的數據量有多大，可以通過修改默認初始大小，減少動態(tài)擴容的次數，這樣會大大提高 HashMap 的性能。

• 裝載因子和動態(tài)擴容

最大裝載因子默認是 0.75，當 HashMap 中元素個數超過 0.75*capacity（capacity 表示散列表的容量）的時候，就會啟動擴容，每次擴容都會擴容為原來的兩倍大小。

• 散列沖突解決方法

HashMap 底層采用鏈表法來解決沖突。即使負載因子和散列函數設計得再合理，也免不了會出現拉鏈過長的情況，一旦出現拉鏈過長，則會嚴重影響 HashMap 的性能。

于是，在 JDK1.8 版本中，為了對 HashMap 做進一步優(yōu)化，我們引入了紅黑樹。而當鏈表長度太長（默認超過 8）時，鏈表就轉換為紅黑樹。我們可以利用紅黑樹快速增刪改查的特點，提高 HashMap 的性能。當紅黑樹結點個數少于 8 個的時候，又會將紅黑樹轉化為鏈表。因為在數據量較小的情況下，紅黑樹要維護平衡，比起鏈表來，性能上的優(yōu)勢并不明顯。

• 散列函數

散列函數的設計并不復雜，追求的是簡單高效、分布均勻。我把它摘抄出來，你可以看看。

其中，hashCode() 返回的是 Java 對象的 hash code。

開篇解答

如何設計的一個工業(yè)級的散列函數？

如果這是一道面試題或者是擺在你面前的實際開發(fā)問題，你會從哪幾個方面思考呢？

首先，要思考何為一個工業(yè)級的散列表？工業(yè)級的散列表應該具有哪些特性？

• 支持快速的查詢、插入、刪除操作；

• 內存占用合理，不能浪費過多的內存空間；

• 性能穩(wěn)定，極端情況下，散列表的性能也不會退化到無法接受的情況。

如何實現這樣一個散列表呢？根據前面講到的知識，從這三個方面來考慮設計思路：

• 設計一個合適的散列函數；

• 定義裝載因子閾值，并且設計動態(tài)擴容策略；

• 選擇合適的散列沖突解決方法。

結合具體的業(yè)務場景、具體的業(yè)務數據來具體分析。只要我們朝這三個方向努力，就離設計出工業(yè)級的散列表不遠了。

內容小結

上一節(jié)的內容比較偏理論，今天的內容側重實戰(zhàn)。主要講了如何設計一個工業(yè)級的散列表，以及如何應對各種異常情況，防止在極端情況下，散列表的性能退化過于嚴重。分了三部分來講解這些內容，分別是：如何設計散列函數，如何根據裝載因子動態(tài)擴容，以及如何選擇散列沖突解決方法。

關于散列函數的設計，我們要盡可能讓散列后的值隨機且均勻分布，這樣會盡可能地減少散列沖突，即便沖突之后，分配到每個槽內的數據也比較均勻。除此之外，散列函數的設計也不能太復雜，太復雜就會太耗時間，也會影響散列表的性能。

對于動態(tài)散列表來說，不管我們如何設計散列函數，選擇什么樣的散列沖突解決方法。隨著數據的不斷增加，散列表總會出現裝載因子過高的情況。這個時候，我們就需要啟動動態(tài)擴容。

關于散列沖突解決方法的選擇，對比了開放尋址法和鏈表法兩種方法的優(yōu)劣和適應的場景。大部分情況下，鏈表法更加普適。而且，我們還可以通過將鏈表法中的鏈表改造成其他動態(tài)查找數據結構，比如紅黑樹，來避免散列表時間復雜度退化成 O(n)，抵御散列碰撞攻擊。但是，對于小規(guī)模數據、裝載因子不高的散列表，比較適合用開放尋址法。

課后思考

在你熟悉的編程語言中，哪些數據類型底層是基于散列表實現的？散列函數是如何設計的？散列沖突是通過哪種方法解決的？是否支持動態(tài)擴容？