散清單（Hash Table）中的散列函數和散列沖突解決

散清單的英文叫“Hash Table”，平時也叫它“哈希表”或“Hash表”。散清單是用數組支援按照下标随機通路資料的特性。

将鍵（key）轉化為數組下标的映射方法就叫作散列函數，而散列函數計算得到的值就叫作散列值。

散列函數

定義為hash（key），其中key表示元素的鍵值，hash（key）的值表示經過散列函數計算得到的散列值。

散列函數設計的基本要求：

    1 散列函數計算得到的散列值是一個非負整數。

    2 如果key1 = key2，那hash( key1 ) == hash( key2 )。

    3 如果key1 ≠ key2，那hash( key1 ) ≠ hash( key2 )。

散列沖突

在真實情況下要想找到一個不同的key對應的散列值都不一樣的散列函數，幾乎是不可能的，無法完全避免散列沖突，常用的散列沖突的解決方法有兩類，開放尋址法（open addressing）和連結清單法（chaining）。

1 開放尋址法

核心思想：如果出現了散列沖突，就重新探測一個空閑位置，将其插入。

探測方法：線性探測（Linear probing）、二次探測（Quadratic probing）、雙重探測（Double hashing）

    1）線性探測：往散清單中插入資料時，如果某個資料經過散列函數散列之後，存儲位置已經被占用了，我們就從目前位置開始，依次往後查找，看是否有空閑位置，直到找到位置。

        hash(key)+0，hash(key)+1，hash(key)+2 ……

    2）二次探測：每次探測的步長變成原來的二次方。

        hash(key)+0，hash(key)+1^2 ，hash(key)+2^2 ……

    3）雙重探測：使用一組散列函數，依次使用散列函數，直到找到空閑的存儲位置。

        hash1(key)，hash2(key)，hash3(key) ……

為了盡可能保證散清單的操作效率，一般會盡可能保證散清單中有一定比例的空閑槽位，用裝載因子來表示空位的多少。裝載因子越大，說明空閑位置越少，沖突越多，散清單的性能會下降。

散清單的裝載因子 = 填入表中的元素個數 / 散清單的長度

2 連結清單法

在散清單中，每個桶或者槽會對應一條連結清單，通過散列函數計算出對應的散列槽位，所有散列值相同的元素都放到相同槽位對應的連結清單中。