一、散列思想
散串列的英文叫Hash Table，也叫哈希表或者Hash表，散串列用的是陣列支持按照下標隨機訪問資料的特性，所以散串列其實就是陣列的一種擴展，由陣列演化而來，可以說，如果沒有陣列，就沒有散串列，
散串列時間復雜度是O(1)的特性，我們通過散列函式把元素的鍵值映射為下標，然后將資料存盤在陣列中對應下標的位置，當我們按照鍵值查詢元素時，我們用同樣的散列函式，將鍵值轉化為陣列下標，從對應的陣列下標的位置取資料，
二、散列函式
散列函式在散串列中起著非常關鍵的作用，散列函式，顧名思義，它是一個函式，可以把它定義成hash(key),其中key表示元素的鍵值，hash(key)的值表示經過散列函式計算得到的散列值，
如何改造散列函式？散列函式設計的基本要求：
1、散列函式計算得到的散列值是一個非負整數；
2、如果key1=key2，那hash(key1)==hash(key2);
3、如果key1≠key2，那hash(key1)≠hash(key2)
解釋一下上述三點：其中，第一點理解起來應該沒有任何問題，因為陣列下標是從0開始的，所以散列函式生成的散列值也要是非負整數，第二點也很好理解，相同的key，經過散列函式得到的散列值也應該是相同的，
第三點看起來合情合理，但是在真實的情況下，要想找到一個不同key對應的散列值都不一樣的散列函式，幾乎是不可能的，即使像業界著名的MD5、SHA、CRC等哈希演算法，也無法完全避免這種散列沖突，而且，因為陣列的存盤空間有限，也會加大散列沖突的概率，
三、散列沖突
再好的散列函式也無法避免散列沖突，如何解決散列沖突呢？常用的散列沖突解決方法有兩類：開放尋址法（open addressing）和鏈表法（chaining）
1、開放尋址法
開放尋址法的核心思想是，如果出現了散列沖突，我們就重新探測一個空閑位置，將其插入，那如何重新探測新的位置呢？先講一個比較簡單的探測方法，線性探測（Linear Probing），
線性探測：當我們往散串列中插入資料時，如果某個資料經過散列函式散列之后，存盤位置已經被占用了，我們就就從當前位置開始，依次往后查找，看是否有空閑位置，直到找到為止，
從圖中可知，散串列大小為10，在元素x插入散串列之前，已經6個元素插入到散串列中，x經過Hash演算法之后，被散列到下標為7的位置，但是這個位置已經有資料了，所以就產生了沖突，于是就順序往后一個一個找，遍歷到尾部都沒有找到空閑的位置，于是從表頭開始找，直到找到空閑位置2，于是將其插入到這個位置，
線性探測法：當散串列中插入的資料越來越多時，散列沖突發生的可能性就會越來越大，空閑位置會越來越少，線性探測的時間就會越來越久，極端情況下，我們可能需要探測整個散串列，因此最壞時間復雜度為O(n)，
對于開發尋址法，除了線性探測方法之外，還有另外兩種比較經典的探測方法，二分探測(Quadratic probing)和雙重散列(Double hashing)，
不管采用哪種探測方法，當散串列中空間位置不多的時候，散列沖突的概率就會大大提高，一般情況下，為了盡可能保證散串列的操作效率，一般情況下，我們會盡可能保證散串列中有一定比例的空閑槽位，用裝載因子來表示空位的多少，
裝載因子的計算公式是：
散串列的裝載因子 = 填入表中的元素個數 / 散串列的長度
裝載因子越大，說明空閑位置越少，沖突越多，散串列的性能會下降，
2、鏈表法
鏈表法是一種更加常用的散列沖突解決辦法，相比開放尋址法，它要簡單很多，如下圖，在散串列中，每個桶（bucket）或者槽位（slot）會對應一條鏈表，所有散列值相同的元素都放到相同的操作對應的鏈表中，
插入的時候，只需要通過散列函式計算出對應的散列槽位，將其插入到對應鏈表中即可，所以插入的時間復雜度是O(1)，當查找一個元素時，我們同樣通過散列函式計算出對應的槽，然后遍歷鏈表查找，那查找的時間復雜度是多少呢？
實際上，查找的時間復雜度跟鏈表的長度k成正比，也就是O(k)，對于散列比較均勻的散列函式來說，理論上，k=n/m，其中n表示散列中資料的個數，m表示散串列中“槽”的個數，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/220971.html
標籤：其他
上一篇：C語言環境搭建
下一篇：Pandas概論