摘要：哈希表也是種數(shù)據(jù)結(jié)構(gòu)，它可以提供快速的插入操作和查找操作。一個(gè)更好的散列函數(shù)為了避免碰撞，首先要確保散列表中用來(lái)存儲(chǔ)數(shù)據(jù)的數(shù)組其大小是個(gè)質(zhì)數(shù)，這和計(jì)算散列值時(shí)使用的取余運(yùn)算有關(guān)。散列函數(shù)將學(xué)生里的數(shù)字相加，使用函數(shù)計(jì)算出散列值。

字典是以鍵值對(duì)形式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，就像電話號(hào)碼薄里的名字和電話號(hào)碼那樣的一一對(duì)應(yīng)的關(guān)系。

javascript的Object類就是以這樣的一種字典形式設(shè)計(jì)的。

鍵值對(duì)在字典中以這樣的方式標(biāo)記：d = {key1 : value1, key2 : value2 }。字典中的鍵/值對(duì)是沒(méi)有順序的。如果你想要一個(gè)特定的順序，那么你應(yīng)該在使用前自己對(duì)它們排序。

Dictionary類的基礎(chǔ)是Array類，而不是Object類。我們想對(duì)字典中的鍵排序，而在js中是不能對(duì) 對(duì)象 的屬性進(jìn)行排序的。話雖如此，但在js中一切皆對(duì)象，數(shù)組也是對(duì)象。以下面的代碼開始定義Dictionary類：

先來(lái)定義add()方法。該方法接受兩個(gè)參數(shù)：鍵和值。鍵是值在字典中的索引，代碼如下：

function add(key,value){
        this.datastore[key] = value;
}

接下來(lái)定義find()方法，該方法以 鍵 做為參數(shù)，返回和其關(guān)聯(lián)的值。代碼如下：

function find(key){
         return this.datastore[key];
     }

從字典中刪除鍵-值對(duì) 需要使用js中的delete函數(shù)。該函數(shù)是Object類的一部分，該函數(shù)同時(shí)刪掉鍵和與其關(guān)聯(lián)的值：

function remove(key){
         delete  this.datastore[key];
     }

最后，我們希望可以顯示字典中所有的鍵-值對(duì)，可以使用如下的方法：

function showAll(){
         for(var key in Object.keys(this.datastore)){
             print(key + "->" + this.datastore[key]);
         }
     }

我們可以定義一些在特定情況下有用的輔助方法。比如要知道字典中的元素個(gè)數(shù)可以定義一個(gè)count()方法，代碼如下：

function count(){
         var n=0;
         for(var key in Object.keys(this.datastore)){
             ++n;
         }
         return n;
     }

為什么不使用length屬性？這是因?yàn)楫?dāng)鍵的類型為字符串時(shí)，length屬性就不管用了

還可以定義一個(gè)clear清除方法：

function clear(){
         for each(var key in Object.keys(this.datastore)){
             delete  this.datastore[key];
         }
     }

for each in（IE6，7，8不支持）無(wú)法獲得對(duì)象的屬性名，只能獲取到屬性值。
另外，遍歷對(duì)象也盡量使用for in 而不是for each，而遍歷數(shù)組的話還是使用for循環(huán)吧

for each in無(wú)法獲得對(duì)象的屬性名，只能獲取到屬性值。

哈希表(Hash table，也叫散列表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。

　　哈希表的做法其實(shí)很簡(jiǎn)單，就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里。

　　而當(dāng)使用哈希表進(jìn)行查詢的時(shí)候，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對(duì)應(yīng)的數(shù)組下標(biāo)，并定位到該空間獲取value，如此一來(lái)，就可以充分利用到數(shù)組的定位性能進(jìn)行數(shù)據(jù)定位

當(dāng)存儲(chǔ)記錄時(shí)，通過(guò)散列函數(shù)計(jì)算出記錄的散列地址

當(dāng)查找記錄時(shí)，我們通過(guò)同樣的是散列函數(shù)計(jì)算記錄的散列地址，并按此散列地址訪問(wèn)該記錄

在js中，散列函數(shù)會(huì)將每個(gè)鍵值映射為一個(gè)唯一的數(shù)組索引。然而，鍵的數(shù)量是無(wú)限的，數(shù)組的長(zhǎng)度是有限的，所以，應(yīng)該讓散列函數(shù)盡量將鍵均勻地映射到數(shù)組中。

哈希表也是種數(shù)據(jù)結(jié)構(gòu)，它可以提供快速的插入操作和查找操作。哈希表運(yùn)算速度極快，哈希表的速度明顯比樹快，樹的操作通常需要O(N)的時(shí)間級(jí)。哈希表不僅速度快，編程實(shí)現(xiàn)也相對(duì)容易。

哈希表最常見(jiàn)的例子是以學(xué)生學(xué)號(hào)為關(guān)鍵字的成績(jī)表，１號(hào)學(xué)生的記錄位置在第一條，１０號(hào)學(xué)生的記錄位置在第１０條...

如果我們以學(xué)生姓名為關(guān)鍵字，如何建立查找表，使得根據(jù)姓名可以直接找到相應(yīng)記錄呢？

用上述得到的數(shù)值作為對(duì)應(yīng)記錄在表中的位置，得到下表：

上面這張表即哈希表。

如果將來(lái)要查李秋梅的成績(jī)，可以用上述方法求出該記錄所在位置：

李秋梅:lqm 12+17+13=42 取表中第42條記錄即可。

我們使用一個(gè)類來(lái)表示散列表，該類包含計(jì)算散列值的方法、向散列中插入數(shù)據(jù)的方法、從散列表中讀取數(shù)據(jù)的方法、顯示散列表中數(shù)據(jù)分布的方法等。
HashTable類的構(gòu)造函數(shù)定義如下：

function HashTable(){
         this.table = new Array(137);//設(shè)定數(shù)組長(zhǎng)度為137，質(zhì)數(shù)
         this.simpleHash = simpleHash;
         this.showDistro = showDistro;
         this.put = put;
     }

散列函數(shù)的選擇依賴于鍵值的數(shù)據(jù)類型。如果鍵是整形，最簡(jiǎn)單的散列函數(shù)就是以數(shù)組的長(zhǎng)度對(duì)鍵取余。

使用一個(gè)簡(jiǎn)單的散列函數(shù)做散列:

   load("HashTable.js");
    var someNames = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];
    var hTable = new HashTable();
    for(var i = 0;i < someNames.length;i++){
        hTable.put(someNames[i]);
    }
    hTable.showDistro();

輸出如下：

35:Cynthia
45:Clayton
57:Donnie
77:David
95:Danny
116:Mike
132:Jennifer
134:Jonathan

simpleHash()函數(shù)通過(guò)使用js的charCodeAt()函數(shù)，返回每個(gè)字符的ASCII碼值，然后再將它們相加得到散列值。put方法通過(guò)調(diào)用simpleHash()函數(shù)得到數(shù)組的索引，然后將數(shù)據(jù)存儲(chǔ)到該索引對(duì)應(yīng)的位置上。

為了避免碰撞，首先要確保散列表中用來(lái)存儲(chǔ)數(shù)據(jù)的數(shù)組其大小是個(gè)質(zhì)數(shù)，這和計(jì)算散列值時(shí)使用的取余運(yùn)算有關(guān)。數(shù)組的長(zhǎng)度應(yīng)該在100以上，這是為了讓數(shù)據(jù)在散列表中分布得更均勻

這里我們使用一個(gè)展示學(xué)生成績(jī)的數(shù)據(jù)集，將隨機(jī)產(chǎn)生一個(gè)9位數(shù)的鍵，用以識(shí)別學(xué)生身份和一門成績(jī)，下面是產(chǎn)生學(xué)生數(shù)據(jù)（包含ID和成績(jī)）的函數(shù)：

function getRandomInt(min,max){
    return Math.floor(Math.random()*(max-min+1))+min;
}
function genStuData(arr){
    for(var i = 0;i

使用getRandomInt()函數(shù)時(shí)，可以指定隨機(jī)數(shù)的最值。genStuData()函數(shù)生成學(xué)生的數(shù)據(jù)。里層的循環(huán)用來(lái)生成學(xué)生的ID，緊跟在循環(huán)后面的代碼生成一個(gè)隨機(jī)的成績(jī)，并把成績(jī)弄在ID的后面。主程序會(huì)把ID和成績(jī)分離。散列函數(shù)將學(xué)生ID里的數(shù)字相加，使用simpleHash()函數(shù)計(jì)算出散列值。

對(duì)散列表排序

put方法同時(shí)接受鍵和數(shù)據(jù)作為參數(shù)，對(duì)鍵值散列后，將數(shù)據(jù)存儲(chǔ)到散列表中：

function put(key,data){
    var pos = this.betterHash(key);
    this.table[pos] = data;
}


put方法將鍵值散列化后，將數(shù)據(jù)存儲(chǔ)到散列化后的鍵值對(duì)應(yīng)在數(shù)組中的位置上。

從散列表中取值

定義get()方法，用以讀取存儲(chǔ)在散列表中的數(shù)據(jù)。該方法同樣需要對(duì)鍵值進(jìn)行散列化，然后才能知道數(shù)據(jù)存儲(chǔ)在數(shù)組的什么位置，代碼如下：

function get(key){
    return this.table[this.betterHash(key)];
}