《算法導(dǎo)論》第三部分 數(shù)據(jù)結(jié)構(gòu) 略過棧 隊列 鏈表,我們到了 散列表
散列表是最常用的數(shù)據(jù)結(jié)構(gòu)之一,特別是 ruby js等動態(tài)語言在語法層次上對它進(jìn)行了支持。只是在java中,有那么點點繞(每次使用的時候,心里會疙瘩一下,不知道你們有沒有這種感覺)。
本章真是糾結(jié),因為看得懂的以前都看過,不懂的現(xiàn)在還是看不懂。 還好看不懂的部分都是加星號的。
散列表是這樣一個東西:它能以key為索引保存東西, 然后在需要的時候嗖的一下就能找出來,灰常地快:)
@Testpublic void test() {HashTable ht = new HashTable();Object o1 = new Object();ht.put("o1", o1);Object o2 = new Object();ht.put("o2", o2);assertEquals(o1, ht.get("o1"));assertEquals(o2, ht.get("o2"));}
get方法要在常量時間內(nèi)找到需要的東西。O(1) <--- 要這樣的復(fù)雜度
先不管這些,但至少HashTable看起來像這樣:
public class HashTable {public void put(String key, Object value) {//...}public Object get(String key) {//...return null;}}
上面的代碼當(dāng)然是通不過測試的(PS: 請先忘記java.util.HashTable)
要想get足夠快,那么最好是跟據(jù) key 直接計算出存儲位置, 然后就能一下子找到啦。
差不多像這樣:
public class HashTable {private Object[] table = new Object[1000];public void put(String key, Object value) {int hash = hash(key.hashCode());if (table[hash] == null) {table[hash] = value;} else{throw new RuntimeException("撞車?yán)玻趺崔k?");}}public Object get(String key) {int hash = hash(key.hashCode());return table[hash];}private int hash(int hashCode) {return -1; // 這里需要返回一個數(shù) [0, table.length - 1]}}
運行測試,數(shù)組越界, 因為我們還未實現(xiàn) hash 這個方法。
hash 的作用是把關(guān)鍵字等可能地散列到 table 中去
有除法散列,乘法散列,等等。
先試一個除法散列:
private int hash(int hashCode) {int capacity = table.length;return hashCode % capacity;}
capacity 不應(yīng)該是 2 的冪, 否則的話值為hashCode的低 k 位, 高位就會浪費掉,可能會造成很多碰撞
可以選擇2的整數(shù)冪不大接近的質(zhì)數(shù)。
現(xiàn)在運行測試,是通過滴:)
但是等等, 有時候我們需要這樣:
@Testpublic void test2() {HashTable ht = new HashTable();Object o1 = new Object();ht.put("o1", o1);Object anotherO1 = new Object();ht.put("o1", anotherO1); // 更新assertEquals(anotherO1, ht.get("o1"));}
我們需要重構(gòu)代碼,把key也給保存起來。
首先添加一個結(jié)構(gòu), 保存key 和value
public class HashTable {public static class Entry {private String key;private Object value;public Entry(String key, Object value) {this.key = key;this.value = value;}public String getKey() {return key;}public Object getValue() {return value;}}private Entry[] table = new Entry[1000]; // 原來的Object[] 改成 Entry[]
重構(gòu)put
public void put(String key, Object value) {int hash = hash(key.hashCode());if (table[hash] == null || table[hash].getKey().equals(key)) {table[hash] = new Entry(key, value);} else{throw new RuntimeException("撞車?yán)?,怎么辦?");}}
重構(gòu)get
可以看到,測試又通過了:)
再看乘法散列
private int hash(int hashCode) {int capacity = table.length;double a = 0.6180334; // 萬能的黃金分割return (int) (((hashCode * a) % 1) * capacity);}
用常數(shù)(A) 乘hashCode 取小數(shù) 再乘capacity
Knuth認(rèn)為 黃金分割數(shù) 是比較理想的值((根號5 - 1) / 2 ~ 0.618), 股民朋友們一定認(rèn)識
乘法散列 的優(yōu)點是:
對 capacity 沒有什么特別的要求, 一般選擇它為 2 的整數(shù)冪。
因為這樣可以使用移位代替乘法計算。
然后黃金分割數(shù) A 如果可以表示成 2654435769 / (2 ^32)
那就可以簡化成:
((hashCode * 2654435769)
& ((1 << 32) - 1) ) // 只保留 32 位
>> (32 - p)
重購代碼試試看:
首先,數(shù)組空間大小為 2 ^ p
private int p = 10;private Entry[] table = new Entry[1 << p];
然后:
private int hash(int hashCode) {long k = 2654435769L;return (int)(((k * hashCode) & ((1L << 32) - 1)) >> (32 - p));}
測試還是通過滴。
下面, 讓我們加多一點元素,搞壞它。
@Testpublic void test3() {HashTable ht = new HashTable();for (int i = 0; i < 1000; i++) {Object o = new Object();ht.put("key" + i, o);assertEquals(o, ht.get("key" + i));System.out.println("Ok: " + i);}}
運行測試,失敗, 可以看到控制臺只輸出到 108
RuntimeException, 撞車了怎么辦?
可以采用鏈接法,開放尋址法搞定
先來 鏈接法
首先重構(gòu)Entry, 把自己串起來
public static class Entry {private String key;private Object value;private Entry next;public Entry(String key, Object value) {this(key, value, null);}public Entry(String key, Object value, Entry next) {this.key = key;this.value = value;this.next = next;}public String getKey() {return key;}public Object getValue() {return value;}public void setValue(Object value) {this.value = value;}public Entry getNext() {return next;}}
同時也添加了一個 setValue 方法, 這樣更容易在鏈表中“更新元素”
然后重構(gòu)put
public void put(String key, Object value) {int hash = hash(key.hashCode());Entry entry = table[hash];if (entry == null) { // 位置沒被使用過, 直接用table[hash] = new Entry(key, value);return;}for (Entry o = entry; o != null; o = o.getNext()) {if (o.getKey().equals(key)) { // 看看key節(jié)點是否存在, 如果是,就更新它o.setValue(value);return;}}table[hash] = new Entry(key, value, entry); // 這里我們串起來}
可以看到,測試正常運行:)
但是隨著散列表中的元素越來越多,碰撞機(jī)率也越來越大,最好當(dāng)元素數(shù)量達(dá)到一定量時,自動擴(kuò)充容量,這樣才能保證其優(yōu)異的查找性能。
但是我們先看看,現(xiàn)在的散列表, 運行test3時,碰撞幾率是多少。
為此,我們重構(gòu), 發(fā)生碰撞時, 統(tǒng)計次數(shù)。
private int size = 0; // 統(tǒng)計表中元素個數(shù)private int collideCount = 0; // 統(tǒng)計碰撞次數(shù)public int getSize() {return size;}public float getCollideRate() {return size > 0 ? ((float) collideCount) / size : 0;}
public void put(String key, Object value) {int hash = hash(key.hashCode());Entry entry = table[hash];if (entry == null) {table[hash] = new Entry(key, value);size++; // 這里return;}collideCount++; // 這里for (Entry o = entry; o != null; o = o.getNext()) {if (o.getKey().equals(key)) {o.setValue(value);return;}}table[hash] = new Entry(key, value, entry);size++; // 還有這}
測試:
@Testpublic void test4() {HashTable ht = new HashTable();for (int i = 0; i < 1000; i++) {ht.put("key" + i, new Object());}System.out.println(ht.getCollideRate());}
輸出:0.309
總的容量為 1024, 有1000個元素, 其中309個是發(fā)生碰撞。事故挺嚴(yán)重的。
下面我們重構(gòu)HashTable類, 讓其每次達(dá)到容量的 0.75(裝載因子) 就擴(kuò)充容量:)
private int p = 4;private Entry[] table = new Entry[1 << p];private float loadFactor = 0.75f;
首先, 我們的初始化容量為 16個(1 << 4), 然后 load factor 為0.75
public void put(String key, Object value) {if (table.length * loadFactor < size) {resize();}
然后在put 前檢查一下, 如有必要 resize
private void resize() {Entry[] old = table;p += 1;table = new Entry[1 << p];size = 0;collideCount = 0;for (int i = 0; i < old.length; i++) {Entry entry = old[i];while (entry != null) {put(entry.getKey(), entry.getValue());entry = entry.getNext();}}}
寫個測試:
@Testpublic void test5() {HashTable ht = new HashTable();for (int i = 0; i < 1000; i++) {Object o = new Object();ht.put("key" + i, o);assertEquals(o, ht.get("key" + i));}System.out.println(ht.getSize());assertTrue(ht.getSize() == 1000);System.out.println(ht.getCollideRate());}
這個時候,同樣是添加到1000個, loadFactor 此時為 0.08
我們的散列表初始大小為16, 添加到1000個,要進(jìn)行若干次 resize, resize開銷比較大。
我們可以重構(gòu)代碼, 構(gòu)造函數(shù)中指定容量大小,以避免不必要的resize開銷。
但這里不做了,因為現(xiàn)在只是為了說明算法, 但是使用 java.util.HashMap時,就曉得了。
解決碰撞還有開放尋址法
也是灰常容易滴, 我們添加兩個方法, put2, 和 get2, 實現(xiàn)看看。
使用最簡單的 線性探查
public Object get2(String key) {int hash = hash(key.hashCode());Entry entry = table[hash];while (entry != null) {if (entry.getKey().equals(key)) {return entry.getValue();}hash = (hash + 1) % table.length;entry = table[hash];}return null;}
同樣,寫一個測試:
線性探查比較容易實現(xiàn), 但是容易造成“堆在一起”的問題, 書中稱為:一次群集
可以采用二次探查, 或雙重散列,更好地避免這種現(xiàn)象
//----------
下面看看java.util.HashMap的實現(xiàn),更好地了解散列表。
先看 put:
代碼中 hash 和 indexFor addEntry 是我們關(guān)心的地方。
此外: HashMap 允許使用值為 null 的key
有一個 if 語句:
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
先看看 hash值是否相等, 再判斷equals
這也給出了我們重寫equals和 hash的原則: 如果你重寫了equals, 那么你一定要重寫 hashCode, 如果兩個對象equals,那么hashCode也一定要相等, 否則在HashMap等容器中將不能正確工作。參看《Effective Java》
再來看看 hash 和 indexFor (中文注釋是我加的)
hash 根據(jù) 原h(huán)ashCode產(chǎn)生更好的散列值, 因為table的容量大小剛好為2的整數(shù)冪, 所以必須這樣做,否則hash code的高位將浪費(取模時) --- 見上面 除法散列
indexFor: 等于 h % length,
所以,HashMap 采用 改進(jìn)的除法散列
再看看 addEntry
void addEntry(int hash, K key, V value, int bucketIndex) {Entry<K, V> e = table[bucketIndex];table[bucketIndex] = new Entry<K, V>(hash, key, value, e);if (size++ >= threshold)resize(2 * table.length);}
table 也成倍擴(kuò)展的