js數(shù)據(jù)結(jié)構(gòu)和算法（五）字典和散列（hash）

Hegel_Gu 發(fā)布于2019-08-21 10:23 / 2026人閱讀

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

什么是字典結(jié)構(gòu)？

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

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

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

Dictionary類

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

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

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

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

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

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

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

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

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

Dictionary類的輔助方法

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

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

為什么不使用length屬性？這是因為當(dāng)鍵的類型為字符串時，length屬性就不管用了

還可以定義一個clear清除方法：

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

備注：

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

for each in無法獲得對象的屬性名，只能獲取到屬性值。

散列（hash） 什么是哈希表？

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

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

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

散列表的查找步驟

當(dāng)存儲記錄時，通過散列函數(shù)計算出記錄的散列地址

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

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

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

哈希表算法

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

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

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

上面這張表即哈希表。

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

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

HashTable類

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

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

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

使用一個簡單的散列函數(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ù)通過使用js的charCodeAt()函數(shù)，返回每個字符的ASCII碼值，然后再將它們相加得到散列值。put方法通過調(diào)用simpleHash()函數(shù)得到數(shù)組的索引，然后將數(shù)據(jù)存儲到該索引對應(yīng)的位置上。

一個更好的散列函數(shù)

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

散列化整型鍵

這里我們使用一個展示學(xué)生成績的數(shù)據(jù)集，將隨機產(chǎn)生一個9位數(shù)的鍵，用以識別學(xué)生身份和一門成績，下面是產(chǎn)生學(xué)生數(shù)據(jù)（包含ID和成績）的函數(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ù)的最值。genStuData()函數(shù)生成學(xué)生的數(shù)據(jù)。里層的循環(huán)用來生成學(xué)生的ID，緊跟在循環(huán)后面的代碼生成一個隨機的成績，并把成績弄在ID的后面。主程序會把ID和成績分離。散列函數(shù)將學(xué)生ID里的數(shù)字相加，使用simpleHash()函數(shù)計算出散列值。

對散列表排序

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

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


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

從散列表中取值

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

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