13.散清單(中)1. 如何設計散列函數2.裝載因子過大怎麼辦3.如何避免低效地擴容4.如何選擇沖突解決方法5.工業級散清單的特性&設計

文章目錄

• 1. 如何設計散列函數
• • 1.1 散列函數設計不能太複雜
  • 1.2 散列函數生成的值要盡可能随機并且均勻分布
• 2.裝載因子過大怎麼辦
• 3.如何避免低效地擴容
• 4.如何選擇沖突解決方法
• 5.工業級散清單的特性&設計
• • 5.1 Java HashMap工業級連結清單實作
  • • 5.1.1 初始大小
    • 5.1.2 裝載因子和動态擴容
    • 5.1.3 散列沖突解決方法
    • 5.1.4 散列行數
  • 5.2 工業級散清單應該由哪些特性？
  • 5.3 如何實作？

如何打造一個工業級水準的散清單？如何設計一個可以應對各種異常情況的工業級散清單，來避免在散列沖突的情況下，散清單性能的急劇下降，并且能抵抗散列碰撞攻擊？

1. 如何設計散列函數

1.1 散列函數設計不能太複雜

​ 過于複雜的散列函數，勢必會消耗很多的計算時間們也就間接地影響散清單的性能。

1.2 散列函數生成的值要盡可能随機并且均勻分布

2.裝載因子過大怎麼辦

裝載因子越大，說明清單中的元素越多，空閑位置就越少，散列沖突的機率就越大，不僅插入資料的過程要多次尋址或者拉很長的鍊，查找的過程也會是以變得很慢。
           

​ 插入一個資料，最好情況下，不需要擴容，最好時間複雜度為O(1).

​ 最壞的情況，散清單裝載因子過高，重新擴容，我們需要重新申請存儲空間，涉及到三方面：

• 重新擴容
• 重新計算哈希位置

• 搬移資料

  ，時間複雜度為O(1), 用攤還分析法，時間複雜度為O(1).

  裝載因子閥值需要選擇得當。如果太大，會導緻沖突過多；如果太小，會導緻記憶體浪費嚴重。需要權衡時空複雜度：

  • 如果空間緊張，對執行效率要求又不高，可以增加負載因子，設定可以大于1.
  • 反之，對執行效率要求很高，對記憶體空間不敏感，則可以降低負載因子.

3.如何避免低效地擴容

​ 大部分情況下，動态擴容的散清單插入一個資料都很快，但是在特殊情況下，當裝載因子已經達到門檻值，需要先進行擴容，再插入資料。這個時候，插入資料就會變得很慢， 甚至會無法接受。

​ 舉一個極端例子，當散清單目前大小為1GB, 要想擴容為原來的兩倍大小，那麼就需要對1GB的資料重新計算哈希值，并且從原來的散清單版移到新的散清單，很耗時。

​ 為了解決這個問題，可以将擴容操作穿插在插入操作的過程中，分批完成。當裝載因子觸發門檻值後，我們隻重新申請空間，但并不将老的資料搬移到新的散清單中。

​ 當有新的資料插入時，首先将新的資料插入新的散清單中，并且從老的散清單中拿出一個資料放入新散清單。每插入一個資料到散清單，我們都重發上面的過程。經過多次插入操作後，老的散清單中的資料就一點一點全部搬遷至新的散清單中了。這樣沒有一次性資料搬移。插入操作就會變得很快。

​ 對于這期間的查找，相容，先從新散清單中查找，沒有找到，再去老散清單中找。通過這樣将操作均攤到多次的方法，避免了一次性擴容耗時過多的情況，是以時間複雜度為O(1).

4.如何選擇沖突解決方法

• 開放尋址法

  e.g. ThreadLocalMap

  • 優點
    • 資料全部在數組中，可以有效地利用CPU緩存加快查詢速度
    • 序列化簡單，連結清單法包含指針，序列化比較困難
  • 缺點
    • 删除資料麻煩，需要特殊标記
    • 沖突代價太高，是以裝載因子上限不能太大，這也導緻這種方法比連結清單法更浪費記憶體空間
  • 适用場景
    • 資料量小
    • 裝載因子小

• 連結清單發

  e.g. LinkedHashMap

  • 優點
    • 連結清單結點可以在需要時再建立，并不需要像開放尋址那樣事先申請好，是以記憶體利用較開放尋址法高
    • 對大裝載因子容忍度更高，隻要散列函數值均勻分布，即便裝載因子變成10，也就是連結清單的長度變長，雖然效率有所下降，但是比起順序查找還是快和很多
  • 缺點
    • 需要存儲指針，如果儲存資料本身不大，會導緻記憶體翻倍的情況出現
    • 連結清單結點零散分布，對CPU緩存不友好，對執行效率也有一定影響
  • 适用場景
    • 存儲大對象、大資料量
    • 靈活，可以支援多種優化政策，比如用紅黑樹代替連結清單

5.工業級散清單的特性&設計

5.1 Java HashMap工業級連結清單實作

5.1.1 初始大小

​ 預設16，可調整。如果大機率知道數量有多大，可以修改預設值，避免resize數量，這樣會大大提高性能.

5.1.2 裝載因子和動态擴容

​ 預設裝載因子為0.75, 達到門檻值會擴容為原來2倍。

5.1.3 散列沖突解決方法

​ 使用連結清單法。Jdk1.8中，進行了進一步優化。當連結清單長度太長(預設超過8), 連結清單就轉為紅黑樹. 可以利用紅黑樹快速增删改查的特點，提高HashMap的性能。當紅黑樹節點小于8個時，又退化為連結清單。因為在資料量較小的情況下，紅黑樹要維護平衡，比起連結清單，性能上優勢并不明顯。

5.1.4 散列行數

​ 設計并不複雜，最求的是簡單高效，分布均勻。

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
           

5.2 工業級散清單應該由哪些特性？

• 支援快速查詢，插入，删除操作
• 記憶體占用合理，不能浪費太多的記憶體空間
• 性能穩定，極端情況下，散清單的成本效益也不會退化到無法接受的情況

5.3 如何實作？

可以從下面三個方面來考慮設計思路：

• 設計一個合适的散列函數
• 定義裝載因子門檻值，并設計動态擴容政策
• 選擇合适的散列沖突解決方法