散清單
散清單在查找當中使用非常廣泛（本文當然也還會說明删除等其他操作）
本文主要說明散清單的兩種解決沖突的辦法
散清單查找
散清單：對于很多複雜類型的鍵值，我們可以用一個數組來實作無序的符号表，将鍵值通過散列函數轉化作為數組的索引，查找即對數組進行查找（這裡就需要解決沖突）。
散清單的實作分為兩步：
1. 散列函數：
将資料的鍵值轉化為數組的一個索引的一個函數。理想情況下，當然是所有的鍵值，均對應不同的數組索引。但是更多的是，多個不同的鍵值，通過散列函數之後，有了相同的數組索引，這時候就需要解決這些同意數組索引的不同鍵值的确定問題。
2. 解決沖突
這是對于上一步驟産生相同的數組索引問題的解決，主要有兩種解決沖突的辦法。
1>拉鍊法
2>線性探測法
散列函數
對于不同類型的資料，構造不同的散列函數，當然是最好的。
下面主要是三種常用的散列函數的構造：
-
平方取中法
——先通過求關鍵字的平方值擴大相近數的差别，然後根據表長度取中間的幾位數作為散列函數值。
——這種方式中間的幾位數都和關鍵字的每一位都有關，産生的散列位址較為的均勻。
-
折疊法
——将關鍵字分割成相同的幾位數(最後一位可不同)，然後去這幾部分的疊加和。
——折疊法一般是和除留餘法一起使用的。
-
除留餘數法
——取關鍵字被某個不大于散清單表長 m 的數 p 除後所得的餘數為散列位址。即 hash(k) = k mod p, p < m。不僅可以對關鍵字直接取模，也可在折疊法、平方取中法等運算之後 取模。
——對 p 的選擇很重要，一般取素數或 m ，若 p 選擇不好，容易産生碰撞。
對于一些常用的資料類型：如正整數，浮點數，字元串，組合鍵等。
1>正整數：最常用的就是除留餘數法。
2>浮點數：通常是将鍵值表示為二進制，再使用除留餘數法。（Java就是這樣處理的）
3>字元串：除留餘數法，将字元串的每個字元使用charAt()轉化為char值，即是一個非負的16位整數。這種辦法確定了字元串的每個字元都能起到作用。
4>組合鍵：與處理String類似，将每個鍵值都混合起來，在進行散列函數的處理。
拉鍊法
-
拉鍊法原理
将大小為M的數組中的每個索引都指向一個連結清單，這樣對于産生沖突的元素，就都存儲在了數組對應索引的連結清單中。這樣查找時，就需要先找到數組對應的索引中，再對索引中的連結清單進行順序查找，就能找到目标元素。
查找算法—散清單 - Java實作（隻貼關鍵代碼）
//put(Key,Value)
// double table size if average length of list >=
if (n >= *m) resize(*m);
int i = hash(key);
//judege key is not null
if (!st[i].contains(key))
n++;
st[i].put(key, val);
//delete(Key)
int i = hash(key);
if (st[i].contains(key)) n--;
st[i].delete(key);
// halve table size if average length of list <=
if (m > INIT_CAPACITY && n <= *m) resize(m/2);
線性探測法
-
線性探測法原理
使用大小為M的數組儲存N個鍵值對，用數組中的空位來解決沖突的辦法。
當發生碰撞時（數組的索引已經被前面的鍵值所占有），我們直接檢查散清單的下一個位置（将索引值+K），這樣的線性探測，隻會有三種結果：
1>命中，該位置的鍵與查找鍵相同；
2>未命中，鍵空；
3>未命中，鍵值不相同繼續查找，索引+K。
如圖：
查找算法—散清單 其中K值不同，也分為不同的線性探測法：
（ 1 ） d i ＝ 1 ， 2 ， 3 ，——線性探測再散列；
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2，——二次探測再散列；
（ 3 ） d i ＝ 僞随機序列 ，——僞随機再散列；
- Java實作
//put(Key,Value)
// double table size if 50% full
if (n >= m/) resize(*m);
int i;
for (i = hash(key); keys[i] != null; i = (i + ) % m) {
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
n++;
//delete(Key)
// find position i of key
int i = hash(key);
while (!key.equals(keys[i])) {
i = (i + ) % m;
}
// delete key and associated value
keys[i] = null;
vals[i] = null;
// rehash all keys in same cluster
i = (i + ) % m;
while (keys[i] != null) {
// delete keys[i] an vals[i] and reinsert
Key keyToRehash = keys[i];
Value valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + ) % m;
}
n--;
// halves size of array if it's 12.5% full or less
if (n > && n <= m/) resize(m/);
assert check();