《算法導論》讀書筆記7 (散列表)

碧海山城 2010-05-05

展開全文

《算法導論》第三部分 數(shù)據(jù)結構 略過棧隊列鏈表，我們到了 散列表

散列表是最常用的數(shù)據(jù)結構之一，特別是 ruby js等動態(tài)語言在語法層次上對它進行了支持。只是在java中，有那么點點繞(每次使用的時候，心里會疙瘩一下，不知道你們有沒有這種感覺)。

本章真是糾結，因為看得懂的以前都看過，不懂的現(xiàn)在還是看不懂。還好看不懂的部分都是加星號的。

散列表是這樣一個東西：它能以key為索引保存東西，然后在需要的時候嗖的一下就能找出來，灰常地快：）

	@Test
public 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) <--- 要這樣的復雜度

先不管這些，但至少HashTable看起來像這樣：

public class HashTable {
public void put(String key, Object value) {
//...
}
public Object get(String key) {
//...
return null;
}
}

上面的代碼當然是通不過測試的(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("撞車啦，怎么辦?");
}
}
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 的作用是把關鍵字等可能地散列到 table 中去

有除法散列，乘法散列，等等。

先試一個除法散列：

	private int hash(int hashCode) {
int capacity = table.length;
return hashCode % capacity;
}

capacity 不應該是 2 的冪，否則的話值為hashCode的低 k 位，高位就會浪費掉，可能會造成很多碰撞

可以選擇2的整數(shù)冪不大接近的質數(shù)。

現(xiàn)在運行測試，是通過滴：）

但是等等，有時候我們需要這樣：

Java代碼

	@Test
public 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"));
}

我們需要重構代碼，把key也給保存起來。

首先添加一個結構，保存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[]

重構put

Java代碼

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("撞車啦，怎么辦?");
}
}

	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("撞車啦，怎么辦?");
}
}

重構get

Object get(String key) {
   int hash = hash(key.hashCode());
   Entry entry = table[hash];
   return entry == null ? null : entry.getValue();
}

可以看到，測試又通過了：）

再看乘法散列

	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認為黃金分割數(shù) 是比較理想的值（(根號5 - 1) / 2 ~ 0.618), 股民朋友們一定認識

乘法散列的優(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));
}

測試還是通過滴。

下面，讓我們加多一點元素，搞壞它。

	@Test
public 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, 撞車了怎么辦？

可以采用鏈接法，開放尋址法搞定

先來 鏈接法

首先重構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 方法，這樣更容易在鏈表中“更新元素”

然后重構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);  // 這里我們串起來
}

可以看到，測試正常運行：）

但是隨著散列表中的元素越來越多，碰撞機率也越來越大，最好當元素數(shù)量達到一定量時，自動擴充容量，這樣才能保證其優(yōu)異的查找性能。

但是我們先看看，現(xiàn)在的散列表，運行test3時，碰撞幾率是多少。

為此，我們重構, 發(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++; // 還有這
}

測試：

	@Test
public 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ā)生碰撞。事故挺嚴重的。

下面我們重構HashTable類，讓其每次達到容量的 0.75(裝載因子) 就擴充容量：）

	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();
}
}
}

寫個測試：

	@Test
public 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個，要進行若干次 resize, resize開銷比較大。

我們可以重構代碼， 構造函數(shù)中指定容量大小，以避免不必要的resize開銷。

但這里不做了，因為現(xiàn)在只是為了說明算法，但是使用 java.util.HashMap時，就曉得了。

解決碰撞還有開放尋址法

也是灰常容易滴，我們添加兩個方法， put2, 和 get2，實現(xiàn)看看。

使用最簡單的 線性探查

	public void put2(String key, Object value) {
if (table.length * loadFactor < size) {
resize();
}
int hash = hash(key.hashCode());
Entry entry = table[hash];
int nextHash = hash;
while (entry != null) {
if (entry.getKey().equals(key)) {
entry.setValue(value);
return;
}
nextHash = (nextHash + 1) % table.length;  // 看看下一個位置
entry = table[nextHash];
}
table[nextHash] = new Entry(key, value);
size++;
if (hash != nextHash) {
collideCount++;
}
}

	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;
}

同樣，寫一個測試：

	@Test
public void test6() {
HashTable ht = new HashTable();
for (int i = 0; i < 1000; i++) {
Object o = new Object();
ht.put2("key" + i, o);
assertEquals(o, ht.get2("key" + i));
}
System.out.println(ht.getSize());
assertTrue(ht.getSize() == 1000);
System.out.println(ht.getCollideRate());
}

線性探查比較容易實現(xiàn)，但是容易造成“堆在一起”的問題，書中稱為：一次群集

可以采用二次探查，或雙重散列，更好地避免這種現(xiàn)象

//----------

下面看看java.util.HashMap的實現(xiàn)，更好地了解散列表。

先看 put:

	public V put(K key, V value) {
if (key == null)  // null 也可以為key
return putForNullKey(value);
int hash = hash(key.hashCode()); // 關心的地方
int i = indexFor(hash, table.length); // 關心的地方
for (Entry<K, V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i); // 關心的地方
return null;
}

代碼中 hash 和 indexFor addEntry 是我們關心的地方。

此外： 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 (中文注釋是我加的)

   /**
* Applies a supplemental hash function to a given hashCode, which
* defends against poor quality hash functions.  This is critical
* because HashMap uses power-of-two length hash tables, that
* otherwise encounter collisions for hashCodes that do not differ
* in lower bits. Note: Null keys always map to hash 0, thus index 0.
*/
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**
* Returns index for hash code h.
*/
static int indexFor(int h, int length) {
return h & (length-1);
}

hash 根據(jù) 原h(huán)ashCode產(chǎn)生更好的散列值，因為table的容量大小剛好為2的整數(shù)冪，所以必須這樣做，否則hash code的高位將浪費(取模時) --- 見上面 除法散列

indexFor：等于 h % length,

所以，HashMap 采用 改進的除法散列

再看看 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 也成倍擴展的