散串列利用陣列支持按下標隨機訪問的時候，時間復雜度為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) -
采用這種方式時，查詢資料首先在原來的散串列中查詢，如果沒有則在新表中查詢
-
-
轉載請注明原文地址：https://www.cnblogs.com/codespoon/p/13253849.html
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27717.html
標籤：其他