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