- 散列函式
- 基于拉鏈法的散串列
- 實作
- 性能
- 基于線性探測法的散串列
- 實作
- 性能
如果所有的鍵都是小整數，則可以用一個陣列來作為無序的符號表，將鍵作為陣列的索引，陣列中對應的位置保存的值就是這個鍵對應的值，這樣就可以快速訪問任意的鍵了，散串列就是基于這種方法，但它能夠處理更加復雜的資料型別，
使用散列的查找演算法分為兩步：第一步需要通過散列函式將鍵轉換為陣列的索引，理想情況下，根據索引就可以再獲取鍵對應的值了，但實際上會存在多個鍵的散列值指向同一個索引的情況，這時就需要進行第二步：處理碰撞沖突，
散列函式
散列函式可以將鍵轉化為陣列的索引，如果陣列的容量為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()將陣列容量翻倍，以維持較低的使用率，
總結
可見不管是用哪種方式實作的散串列，都是在時間和空間之間做了權衡，如果沒有記憶體限制，即使資料量特別大，也可以直接將鍵作為一個超大陣列的索引，這樣只需訪問記憶體一次就可以完成查找；如果沒有時間限制，也可以使用無序陣列存盤資料，然后順序查找，而散串列則使用了適度的空間和時間并在這兩個極端之間取得了一種平衡，通過調整散串列的引數就可以在空間和時間之間做出取舍，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/137160.html
標籤：其他
上一篇：資料結構與演算法之兩種查找方法