js數據結構和算法（五）字典和散列（hash）

Hegel_Gu 發布于2019-08-21 10:23 / 2017人閱讀

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

什么是字典結構？

字典是以鍵值對形式存儲數據的數據結構，就像電話號碼薄里的名字和電話號碼那樣的一一對應的關系。

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

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

Dictionary類

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

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

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

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

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

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

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

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

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

Dictionary類的輔助方法

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

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

為什么不使用length屬性？這是因為當鍵的類型為字符串時，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，而遍歷數組的話還是使用for循環吧

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

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

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

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

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

散列表的查找步驟

當存儲記錄時，通過散列函數計算出記錄的散列地址

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

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

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

哈希表算法

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

如果我們以學生姓名為關鍵字，如何建立查找表，使得根據姓名可以直接找到相應記錄呢？

用上述得到的數值作為對應記錄在表中的位置，得到下表：

上面這張表即哈希表。

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

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

HashTable類

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

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

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

使用一個簡單的散列函數做散列:

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

一個更好的散列函數

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

散列化整型鍵

這里我們使用一個展示學生成績的數據集，將隨機產生一個9位數的鍵，用以識別學生身份和一門成績，下面是產生學生數據（包含ID和成績）的函數：

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

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

對散列表排序

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

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


put方法將鍵值散列化后，將數據存儲到散列化后的鍵值對應在數組中的位置上。

從散列表中取值

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

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

GPU云服務器云服務器 js算法和數據結構 js hash 刪除數據字符串hash算法最快的hash表算法

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/85444.html

學習數據結構與算法之字典和散列表

摘要：小結實現了字典和哈希表感覺沒有想象中那么困難，當然這還是開始。本系列所有文章：第一篇文章：學習數據結構與算法之棧與隊列第二篇文章：學習數據結構與算法之鏈表第三篇文章：學習數據結構與算法之集合第四篇文章：學習數據結構與算法之字典和散列表第五篇文章：學習數據結構與算法之二叉搜索樹字典不是新華字典哦，這里的字典也稱作_映射_，是一種數據結構，跟set集合很相似的一種數據結構，都可以用來...

Heier 2019-08-21 11:52 評論0 收藏0
《JavaScript數據結構與算法》筆記——第7章字典和散列表

摘要：在字典中，存儲的是鍵，值，集合可以看作值，值的形式存儲元素，字典也稱為映射方法描述備注向字典中添加新元素通過某個鍵值從字典中移除對應的數據值判斷某個鍵值是存在于這個字典中通過鍵值獲取對應的數據值返回字典所有元素的數量刪除字典中所有元素將字典在字典中，存儲的是[鍵，值]，集合可以看作[值，值]的形式存儲元素，字典也稱為映射方法描述備注 set(key,...

zorro 2019-08-26 13:28 評論0 收藏0
《Javascript數據結構和算法》筆記-「字典和散列表」

摘要：我經常在業務代碼中把數據處理成這種字典的數據結構獲取的方法哈希表在學習了類之后，我們會學習散列表，也就是哈希表。《Javascript數據結構和算法》筆記-「字典和散列表」集合、字典、散列表存儲的都是「不重復」的數據結構集合：我們更關注每一個元素的值，并把其作為主要元素字典：我們用[鍵,值]的形式來存儲數據散列表：跟字典類似，也會是用[鍵,值]的形式來存儲數據但是「字...

wenyiweb 2019-08-26 13:23 評論0 收藏0
每周一練之 數據結構與算法（Dictionary 和 HashTable）

摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。根據鍵值從散列表中移除值。請實現散列表將和存在一個對象中即可定義一個包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 Hash...

eternalshallow 2019-08-26 13:51 評論0 收藏0
每周一練之 數據結構與算法（Dictionary 和 HashTable）

摘要：什么是散列表和散列函數哈希表，也叫散列表，是根據關鍵碼值而直接進行訪問的數據結構。將字典的所有鍵名以數組的形式返回。根據鍵值從散列表中移除值。這是第五周的練習題，上周忘記發啦，這周是復習 Dictionary 和 HashTable。下面是之前分享的鏈接： 1.每周一練之數據結構與算法（Stack） 2.每周一練之數據結構與算法（LinkedList） 3.每周一練之數據結構...

ingood 2019-05-22 14:21 評論0 收藏0