- 散列函數
- 基于拉鍊法的散清單
- 實作
- 性能
- 基于線性探測法的散清單
如果所有的鍵都是小整數，則可以用一個數組來作為無序的符号表，将鍵作為數組的索引，數組中對應的位置儲存的值就是這個鍵對應的值。這樣就可以快速通路任意的鍵了。散清單就是基于這種方法，但它能夠處理更加複雜的資料類型。
使用散列的查找算法分為兩步：第一步需要通過散列函數将鍵轉換為數組的索引，理想情況下，根據索引就可以再擷取鍵對應的值了，但實際上會存在多個鍵的散列值指向同一個索引的情況，這時就需要進行第二步：處理碰撞沖突。
散列函數可以将鍵轉化為數組的索引。如果數組的容量為M，則散列函數就應該能夠将任意鍵轉換為數組範圍内的索引。合格的散列函數需要滿足如下條件：
- 一緻性，等價的鍵必然産生相等的散列值；
- 高效性，散列函數應該計算簡便，開銷很小
- 均勻性，能夠均勻地散列所有的鍵
Java為每種資料類型都内置了hashCode方法，它的傳回值是一個32位的整數。每一種資料類型的hashCode方法都與equals()方法一緻，即如果a.equals(b)，則a.hashCode()=b.hashCode()，但如果a.hashCode()=b.hashCode()，a不一定與b相等，因為會有碰撞問題，還需要用equals()方法進行判斷。預設的hashCode方法會傳回對象的記憶體位址，但這隻适用于很少的情況，Java為很多常用的資料類型重寫了hashCode()方法，比如String、Integer、Double、File等等。
在實作散清單時，需要将鍵映射為數組的索引，以下hash()方法是基于hashCode()的：
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
hashCode()的傳回值是32位整數，将其和0x7fffffff進行&運算，可以屏蔽符号位，變為一個31位的非負整數，然後與數組容量m取餘，可以保證散列值都落在數組的索引範圍内。m為素數時，散列值會更均勻。
在散列函數将鍵轉化為數組索引後，接下來要做的就是處理碰撞沖突。一種方法是将數組中的每個元素都指向一條連結清單，連結清單中的每個節點都存儲了散列值為該元素的索引的鍵值對。這種方法便是拉鍊法。要從基于拉鍊法的散清單中查找一個元素，首先根據散列值找到對應的連結清單，然後沿着連結清單順序查找相應的鍵。為了保證高效地查找，數組的容量M值應該足夠大，這樣得到的連結清單平均長度會比較短。
如下為基于拉鍊法的散清單的實作：
public class SeparateChainingHashST<Key, Value> {
private static final int INIT_CAPACITY = 4;
private int n; // count of k-v pairs
private int m; // size of hashtable
private SequentialSearchST<Key, Value>[] st;
public SeparateChainingHashST() {
this(INIT_CAPACITY);
}
public SeparateChainingHashST(int M) {
this.m = M;
st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
for (int i = 0; i < M; i++) {
st[i] = new SequentialSearchST();
}
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
public Value get(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to get() is null");
return (Value) st[hash(key)].get(key);
}
public void put(Key key, Value val) {
if (key == null)
throw new IllegalArgumentException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
// double table size if average length of list >= 10
if (n >= 10 * m)
resize(2 * m);
int i = hash(key);
if (!st[i].contains(key))
n++;
st[i].put(key, val);
}
public void delete(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to delete() is null");
int i = hash(key);
if (st[i].contains(key))
n--;
st[i].delete(key);
if (m > INIT_CAPACITY && size() < 2 * m)
resize(m / 2);
}
public void resize(int chains) {
SeparateChainingHashST<Key, Value> temp = new SeparateChainingHashST<Key, Value>(chains);
for (int i = 0; i < m; i++) {
for (Key key : st[i].keys()) {
temp.put(key, st[i].get(key));
}
}
this.m = temp.m;
this.n = temp.n;
this.st = temp.st;
}
public int size() {
return n;
}
}
數組的每個位置都指向一條可以順序查找的連結清單，連結清單的平均長度為n/m，平均長度越短，查找的效率越高，但所需的記憶體空間卻越大。此處通過resize方法将n/m的值（即連結清單的平均長度）控制在2~10之間。
public void put(Key key, Value val) {
...
// double table size if average length of list >= 10
if (n >= 10 * m)
resize(2 * m);
...
}
public void delete(Key key) {
...
if (m > INIT_CAPACITY && size() < 2 * m)
resize(m / 2);
}
理想情況下，散列函數能夠均勻并獨立地将所有的鍵散布于0到M-1之間，雖然在實際應用中無法找到一個完全滿足這一要求的散列函數，但通過實驗也可以驗證上述hash()方法得到的散布結果已經非常接近理想情況了，是以基于這一均勻散列假設分析得出的散清單的性能具有實際的參考意義。
基于均勻散列假設，連結清單的平均長度為n/m，那麼其性能特點與無序連結清單一緻：
- 未命中的查找和新插入元素時，都需要n/m次比較；
- 對于命中的查找，最壞情況為n/m次比較，在平均情況下，根據在之前對随機命中模式的分析，約需要與一半的元素進行比較。
另一種實作散清單的方式是用大小為M的數組儲存N個鍵值對，其中M>N，數組中的空位就可以用來解決碰撞問題。基于這種政策的的方法稱為開放位址散清單。線性探測法是這類方法中最簡單的一種。當出現碰撞時，就檢查散清單的下一個位置。具體運作中，查找一個元素時，如果散列值指向的的鍵和被查找的鍵相同，則查找命中；指向的鍵為空，則未命中；如果指向的鍵與被查找的鍵不同，則繼續與下一個位置比較。
public class LinerProbingHashST<Key, Value> {
private int n; // count of k-v pairs
private int m = 16; // size of hashtable
private Key[] keys;
private Value[] vals;
public LinerProbingHashST() {
this(16);
}
public LinerProbingHashST(int capaticy) {
keys = (Key[]) new Object[capaticy];
vals = (Value[]) new Object[capaticy];
}
private int hash(Key key) {
return (key.hashCode() & 0x7fffffff) % m;
}
public Value get(Key key) {
if (key == null)
throw new IllegalArgumentException("argument to get() is null");
for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key)) {
return vals[i];
}
}
return null;
}
public void put(Key key, Value val) {
if (key == null)
throw new IllegalArgumentException("first argument to put() is null");
// double table size if average length of list >= 10
if (n >= m / 2)
resize(2 * m);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % m) { //
if (keys[i].equals(key)) {
vals[i] = val;
return;
}
}
keys[i] = key;
vals[i] = val;
n++;
}
public void resize(int capacity) {
LinerProbingHashST<Key, Value> st = new LinerProbingHashST<Key, Value>(capacity);
for (int i = 0; i < m; i++) {
if (keys[i] != null) {
st.put(keys[i], vals[i]);
}
keys = st.keys;
vals = st.vals;
m = st.m;
}
}
public int size() {
return n;
}
}
在探測數組時，使用i = (i + 1) % m來改變索引的值，可以保證索引不會超出數組範圍，達到數組末尾時就會折回到開頭的位置。
在拉鍊法中，n/m表示連結清單的平均長度，一般大于1，但線上性探測法中，因為n必然小于等于m，是以n/m不會大于1。可以認為n/m是散清單的使用率。由于線性探測法通過探測某個位置是否為空來決定命中與否，是以使用率不允許達到1，否則就會出現無限循環。而且即便在使用率比較接近1時，散清單的性能已經變得非常差了。相關研究表明，在使用率小于0.5時，探測的次數約為1.5~2.5次。上面的實作中，在n>=m/2時，就會調用resize()将數組容量翻倍，以維持較低的使用率。
總結
可見不管是用哪種方式實作的散清單，都是在時間和空間之間做了權衡。如果沒有記憶體限制，即使資料量特别大，也可以直接将鍵作為一個超大數組的索引，這樣隻需通路記憶體一次就可以完成查找；如果沒有時間限制，也可以使用無序數組存儲資料，然後順序查找。而散清單則使用了适度的空間和時間并在這兩個極端之間取得了一種平衡。通過調整散清單的參數就可以在空間和時間之間做出取舍。
![Greenplum資料庫資料分片政策Hash分布——執行器行為[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)