8.散列表：散列函數、衝突解決與擴容策略
散列表利用數組支援按下標隨機訪問的時候，時間複雜度為O(1)的特性，
-
存儲時通過散列函數把鍵值轉化為下標，將數據存儲在數組中對應下標的位置
-
查詢時也同樣利用散列函數計算出下標，取出數據
-
散列表三個關鍵
-
散列函數：hash值儘可能分布均勻，同時不能太複雜影響效率
-
裝載因子：根據響應時間是否敏感控制大小（執行效率vs記憶體空間）
-
衝突解決：保證最壞情況下的查詢效率，抵禦散列表碰撞攻擊（跳錶、紅黑樹）
-
-
散列函數設計的基本要求
-
散列值是一個非負整數
-
如果
key1 = key2，那麼hash(key1) == hash(key2)（相同鍵值映射到相同表項） -
如果
key1 != key2，那麼hash(key1) != hash(key2)（但散列衝突是無法完全避免的） -
構造哈希函數的幾個方法
-
數字分析法：數據關鍵字存在分布比較均勻的若干位，那麼將這若干位提取出作為哈希地址（如學號長六位：年級-班級-序號，顯而易見可以將序號抽取出作為學號的哈希地址）。
-
平方區中法：取關鍵字平方的中間幾位作為哈希地址，這樣哈希地址與關鍵字的多位值均有關，使得分布較均勻。
-
摺疊法：將關鍵字分割成長度相同的多段，然後將它們的疊加和作為哈希值。這種方法和平方取中理念相同，使關鍵字各位值都對哈希值有影響。
-
除留餘數法：將關鍵字除以一個不大於哈希表長度的正整數P，所得餘數作為哈希地址。這種方法的好壞取決於P的選取，實踐證明，當P取小於哈希表長的最大質數時，產生的哈希函數較好。Java1.8中String對象的哈希函數採用變體的摺疊法加除留餘數法
-
-
-
裝載因子
-
表示散列表中空位的多少
-
散列表的裝載因子 = 填入表中的元素個數 / 散列表的長度
-
當散列表的裝載因子超過某個閾值時，就需要進行擴容。如果記憶體空間不緊張，對執行效率要求較高，可以降低裝載因子的閾值；相反，如果記憶體空間緊張，對執行的效率要求又不高，可以適當增加閾值，甚至可以大於1
-
-
散列衝突解決
-
開放定址法
-
線性探測：當發生散列衝突後，從當前位置開始，依次往後找，直到找到或到達空閑位置為止（這種方法需要注意刪除時不能直接將值設為空，查找時遇到空會結束查找，使得後面的數據無法被探測到）
-
二次探測：線性探測的步長為1，二次探測步長為原來的二次方
-
雙重散列：使用一組散列函數，第一組散列衝突了換第二組……
-
-
鏈表法：所有散列值相同的元素放到相應槽位的鏈表中。當然，這裡鏈表可以換成跳錶、紅黑樹等效率更高的數據結構
-
-
擴容策略：當負載因子達到設定的閾值那麼就需要擴容操作來防止散列表查詢性能下降
-
一次性擴容：需要擴容時申請一個n倍當前大小的空間，將原來散列表的所有數據全部重新計算散列值，加入到新表中，最後將要插入的新值加入。
-
有了前面數組插入分析的基礎，這種方式散列表插入的均攤時間複雜度為
O(1) -
這種策略下，大多數時候插入數據都很快，但在需要擴容時，插入數據就會變得很慢，甚至無法接受（假設當前散列表大小1GB，那插入時需要重新計算1GB數據的哈希值，並移到新的散列表，聽起來就十分耗時）
-
-
穿插擴容：將擴容過程穿插在插入過程中。負載達到閾值後，新數據都插入新散列表中並且從原來的散列表取出一個數據插入新表，經過多次插入過程，原來的散列表就慢慢的轉移到新表中了
-
插入時間複雜度仍為
O(1) -
採用這種方式時，查詢數據首先在原來的散列表中查詢，如果沒有則在新表中查詢
-
-
轉載請註明原文地址：//www.cnblogs.com/codespoon/p/13253849.html
