久久久久99精品成人片直播_ 《算法導論》讀書(shū)筆記7 (散列表)

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

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

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

散列表是這樣一個(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í)間內找到需要的東西。O(1) <--- 要這樣的復雜度

先不管這些，但至少HashTable看起來(lái)像這樣：

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

上面的代碼當然是通不過(guò)測試的(PS: 請先忘記java.util.HashTable)

要想get足夠快，那么最好是跟據 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("撞車(chē)啦，怎么辦?");}}public Object get(String key) {int hash = hash(key.hashCode());return table[hash];}private int hash(int hashCode) {return -1; // 這里需要返回一個(gè)數 [0, table.length - 1]}}

運行測試，數組越界，因為我們還未實(shí)現 hash 這個(gè)方法。

hash 的作用是把關(guān)鍵字等可能地散列到 table 中去

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

先試一個(gè)除法散列：

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

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

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

現在運行測試，是通過(guò)滴：）

但是等等，有時(shí)候我們需要這樣：

Java代碼

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

我們需要重構代碼，把key也給保存起來(lái)。

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

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

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

重構get

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

可以看到，測試又通過(guò)了：）

再看乘法散列

	private int hash(int hashCode) {int capacity = table.length;double a = 0.6180334;  // 萬(wàn)能的黃金分割return (int) (((hashCode * a) % 1) * capacity);}

用常數(A) 乘hashCode 取小數再乘capacity

Knuth認為黃金分割數是比較理想的值（(根號5 - 1) / 2 ~ 0.618), 股民朋友們一定認識

乘法散列的優(yōu)點(diǎn)是：

對 capacity 沒(méi)有什么特別的要求，一般選擇它為 2 的整數冪。

因為這樣可以使用移位代替乘法計算。

然后黃金分割數 A 如果可以表示成 2654435769 / (2 ^32)

那就可以簡(jiǎn)化成：

              ((hashCode * 2654435769)
                  & ((1 << 32) - 1) )   // 只保留 32 位
               >> (32 - p)

重購代碼試試看：

首先，數組空間大小為 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));}

測試還是通過(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);}}

運行測試，失敗，可以看到控制臺只輸出到 108

RuntimeException, 撞車(chē)了怎么辦？

可以采用鏈接法，開(kāi)放尋址法搞定

先來(lái) 鏈接法

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

然后重構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節點(diǎn)是否存在， 如果是，就更新它o.setValue(value);return;}}table[hash] = new Entry(key, value, entry);  // 這里我們串起來(lái)}

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

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

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

為此，我們重構, 發(fā)生碰撞時(shí)，統計次數。

	private int size = 0;  // 統計表中元素個(gè)數private int collideCount = 0;  // 統計碰撞次數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個(gè)元素，其中309個(gè)是發(fā)生碰撞。事故挺嚴重的。

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

	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è)測試：

	@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)比較大。

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

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

解決碰撞還有開(kāi)放尋址法

也是灰常容易滴，我們添加兩個(gè)方法， put2, 和 get2，實(shí)現看看。

使用最簡(jiǎn)單的 線(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;  // 看看下一個(gè)位置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;}

同樣，寫(xiě)一個(gè)測試：

	@Testpublic 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)性探查比較容易實(shí)現，但是容易造成“堆在一起”的問(wèn)題，書(shū)中稱(chēng)為：一次群集

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

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

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

先看 put:

	public V put(K key, V value) {if (key == null)  // null 也可以為keyreturn putForNullKey(value);int hash = hash(key.hashCode()); // 關(guān)心的地方int i = indexFor(hash, table.length); // 關(guān)心的地方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); // 關(guān)心的地方return null;}

代碼中 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è)對象equals，那么hashCode也一定要相等, 否則在HashMap等容器中將不能正確工作。參看《Effective Java》

再來(lái)看看 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 根據原h(huán)ashCode產(chǎn)生更好的散列值，因為table的容量大小剛好為2的整數冪，所以必須這樣做，否則hash code的高位將浪費(取模時(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 也成倍擴展的

本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請點(diǎn)擊舉報。

欧美性猛交XXXX免费看蜜桃,成人网18免费韩国,亚洲国产成人精品区综合,欧美日韩一区二区三区高清不卡,亚洲综合一区二区精品久久