溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關JavaScript如何實現哈希表，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
哈希表是一種非常重要的數據結構，幾乎所有的編程語言都有直接或者間接的應用這種數據結構，它通常是基于數組實現的，當時相對于數組，它有更多的優勢：
它可以提供非常快速的插入-刪除-查找操作。
哈希表的速度比數還要快，基本可以瞬間查找到想要的元素
哈希表相對于數來說編碼要容易的多。
但是哈希表相對于數組也有一些不足：
哈希表中的數組是沒有順序的，所以不能以一種固定的方式（比如從小到大）來遍歷其中的元素。
通常情況下，哈希表中的key是不允許重復的，不能放置相同的key，用于保存不同的元素。
那么，哈希表到底是什么呢？
它的結構是數組，但是神奇的地方在于對下標值的一種變換，這種變換我們可以稱之為哈希函數，通過哈希函數可以獲得到HashCode。
接下來，我們可以來看一個例子：
使用一種數據結構來存儲單詞信息，比如有50000個單詞，找到單詞后每個單詞有自己的具題應用等等。我們應該怎樣操作呢？
或許我們可以嘗試將字母轉化成合適的下標。但是怎樣才能將一個字符轉化成數組的下標值呢？有沒有一種方案，可以將單詞轉化成數組的下標值呢？如果單詞轉化為數組的下標，以后如果我們要查找某個單詞的信息，直接按照下標值一步即可訪問到想要的元素。那么怎樣將字符串轉化為下標值呢？
其實計算機有很多的編碼方案就是用數字代替單詞的字符，就是字符編碼，當然， 我們可以設計自己的編碼系統，比如a是1，b是2，c是3等等。但是有了編碼系統以后，一個單詞如何轉化成數字呢？
在這里，我們有兩種方案：
方案一：數字相加
一種轉換單詞的簡便方法就是把單詞每個字符的編碼求和
例如單詞cats轉成數字：3+1+20+19=43，那么43就作為cats單詞下標存在數組中
但是按照這種方案有一個很明顯的問題就是很多單詞最終的下標可能都是43
我們知道數組中一個下標值位置只能存儲一個數據，如果存入后來的數據，必然會造成數據的覆蓋，故而，一個下標存儲這么多單詞顯然是不合理的。
方案二：冪的連乘
其實我們平時用的大于10的數字，就可以用冪的連乘來表示其唯一性，比如：6543 = 6 *103+5 *102+4 *10 + 4
我們的單詞也可以使用這種方案來表示，比如cats = 3 * 273+1 * 272 + 20 * 27+17 = 60337
這樣得到的數字可以基本保證其唯一性，不會和別的單詞重復。
但是存在一個問題，如果一個單詞是zzzzzzzzzz.那么得到的數字超過7000000000000.數組不一定能夠表示這么大的下標值，就算能夠創建這么大的數組，事實上有很多的無效單詞，并沒有意義。
兩種方案總結：
第一種方案（把數字相加求和）產生的數組下標太少，第二種方案（與27的冪相乘求和）產生的數組下標又太多。
所以現在需要一種壓縮方法，把冪的連乘方案系統中得到的巨大整數范圍壓縮到可接收的數組范圍中。有一種簡單的方法就是使用取余操作符，他的作用是得到一個數被另一個數整除后的余數。
取余操作的實現：（0-199之間的數字）
假設把從0-199的數字,(large)，壓縮為0-9的數字(small)
下標的結果index = large % small
當一個數被10整除時，余數一定在0-9之間
例如16%10 = 6,23%10 = 3
這中間還是會有重復，不過重復的數量明顯小了，比如說在0-199中間取5個數字，放在一個長度為10的數組，也會重復，但是重復的概率非常小。
了解了哈希化的原理，我們就可以來看幾個概念：
哈希化：將大數字轉化為數組范圍內下標的過程，就稱之為哈希化
哈希函數：例如將單詞轉化為大數字，大數字在進行哈希化的代碼實現放在一個函數中，這個函數就是哈希函數。
哈希表：最終將數據插入到這個數組，對整個結構的封裝，就可以稱之為一個哈希表。
前面提到了，通過哈希化的下標值依然可能會重復，就會導致沖突，比如說我們將0-199的數字選取5個放在長度為10的單元格里，如果我們隨機選出來的是33，45，27，86，92，那么最終他們的位置會是3-5-7-6-2，沒有發生沖突，但是其中如果還有一個86，一個66呢？此時就會發生沖突。該如何解決這個問題呢？
常用的解決方案有兩種：
鏈地址法是一種比較常見的解決沖突的方案（也稱拉鏈法）
如下圖所示：
創建了一個內存為10的數組，現在，需要將一些數字存到數組內部，這些數字哈希化后可能會重復，將下標值相同的數通過鏈表或者數組鏈接起來的方法叫做鏈地址法。當我們要查找某值的時候，就可以先根據其下標找到對應的鏈表或者數組再在其內部尋找。
從圖片中，我們可以看出，鏈地址法解決沖突的辦法是每個數組單元中存儲的不再是單個數據而是一個鏈條，這個鏈條常用的結構是數組或者鏈條。那在具體應用中應該采用哪一種方式呢？其實這兩種方法都可以，效率上也差不多，當然在某些實現中，會將新插入的數據放在數組或者鏈表的最前面，這種情況最好用鏈表。因為數組再首位插入數據是需要所有其他項后移的的，而鏈表就沒有這樣的問題。
開放地址法的主要工作方式是尋找空白的單元格來添加重復的數據。如下圖所示：
如果有一個數字32，現在要將其插入到數組中，我們的解決方案為：
新插入的32本來應該插入到52的位置，但是該位置已經包含數據，
可以發現3、5、9的位置是沒有任何內容的
這個時候就可以尋找對應的空白位置來放這個數據
但是探索這個位置的方式不同，有三種方式：
1、線性探索
即線性的查找空白單元
插入32
經過哈希化得到的index=2，但是在插入的時候，發現該位置已經有52
此時就從index+1的位置開始一點點查找合適的位置來放置32
探測到的第一個空的位置就是該值插入的位置
查詢32
首先經過哈希化得到index= 2，比較2的位置結果和查詢的數值是否相同，相同則直接返回
不相同則線性查找，從index位置+1查找和32一樣的。
需要注意的是：如果32的位置之前沒有插入，并不需要將整個哈希表查詢一遍來確定該值是否存在，而是如果查詢到空位置，就停止。因為32之前不可能跳過空位置去其他的位置。
線性探測也有一個問題就是：如果之前插入的數據是連續插入的，則新插入的數據就需要很長的探測距離。
2、二次探索
二次探索就在線性探索的基礎上進行了優化。
線性探測，我們可以看做是步長為1的探測，比如從下標值x開始，從x+1,x+2,x+3依次探測。
二次探測對步長做了優化，比如從下標值x開始,x+12,x+22,x+32依次探測。
但是二次探測依然存在問題：比如我們連續插入的是32-112-82-42-52，那么他們依次累加的時候步長是相同的，也就是這種情況下會造成步長不一的一種聚集，還是會影響效率，怎樣解決這個問題呢？來看看再哈希法。
3、再哈希法
再哈希法的做法就是：把關鍵字用另一個哈希函數在做一次哈希化，用這次哈希化的結果作為步長，對于指定的關鍵字，步長在整個探測中是不變的，不同的關鍵字使用不同的步長。
第二次哈希化需要具備以下特點：
和第一個哈希函數不同
不能輸出為0（否則，將沒有步長，每次嘆詞都是原地踏步，算法進入死循環）
而計算機專家已經設計好了一種工作很好的哈希函數。
stepSize = constant - (key % constant)
其中constant是質數，且小于數組的容量，key是第一次哈希化得到的值。
例如：stepSize = 5-(key%5),滿足需求，并且結果不可能為0。
哈希表的主要優點在于它的速度，提高速度的一個方法就是讓哈希函數中有盡量少的乘法和除法，設計好的哈希函數需要具備以下優點：
（1）快速的計算
（2）均勻的分布
來具體實現一下：
首先我們所實現的哈希函數最主要的操作是：將字符創轉化為比較大的數字和將大的數字壓縮到數組范圍之內。如下所示：
function hashFunc(str,size){
//定義hashCode變量
var hashCode = 0;
//根據霍納算法，計算hashCode的值
//先將字符串轉化為數字編碼
for(var i =0;i<str.length;i++){
hashCode = 37*hashCode + str.charCodeAt(i)
}
//取余操作
var index = hashCode % size;
return index;
}代碼測試：
console.log( hashFunc('abc',7));
console.log( hashFunc('cba',7));
console.log( hashFunc('nba',7));
console.log( hashFunc('rgt',7));測試結果為：
可以發現我們得到的字符串對應的下標值分布還是很均勻的。
這里我將采用鏈地址法來實現哈希表：
其中定義了三個屬性：
storage:作為數組，存放相關元素
count：記錄當前已存放的數據量
-limit:標記數組中一共可以存放多少數據
實現的哈希表（基于storage的數組）每個index對應的是一個數組（bucket），bucket里面存放的是（key和value),最終哈希表的數據格式是：[[[k,v],[k,v],[k,v],[[k,v],[k,v]],[k,v]]
如下圖所示：
代碼如下：
function HashTable(){
// 定義屬性
this.storage = [];
this.count = 0;
this.limit = 8;
}在將我們前面封裝好的哈希函數通過原型添加進去：
function HashTable(){
// 定義屬性
this.storage = [];
this.count = 0;
this.limit = 8;
HashTable.prototype.hashFunc = function(str,size){
//定義hashCode變量
var hashCode = 0;
//先將字符串轉化為數字編碼
for(var i =0;i<str.length;i++){
hashCode = 37*hashCode + str.charCodeAt(i)
}
//取余操作
var index = hashCode % size;
return index;
}
}哈希表的插入和修改操作是同一個函數，因為當使用者傳入一個<key,value>時，如果原來不存在該key，那么就是插入操作，如果已經存在該key,對應的就是修改操作。
具體實現思路為：先根據傳入的key獲取對應的hashCode，即數組的index,接著從哈希表的Index位置中取出另一個數組（bucket）,查看上一步的bucket是否為空，如果為空的話，表示之前在該位置沒有放置過任何的內容，則新建一個數組[]；再查看是否之前已經放置過key對應的value,如果放置過，那么就是依次替換操作，而不是插入新的數據，如果不是修改操作的話，那么插入新的數據，并且讓數據項加1。
實現代碼為：
//插入和修改操作
HashTable.prototype.put = function(key,value){
//根據key獲取對應的index
var index = this.hashFunc(str,this.limit);
//根據index取出對應的bucket
var bucket = this.storage[index];
//如果值為空，給bucket賦值一個數組
if(bucket === null){
bucket = [];
this.storage[index] = bucket;
}
//判斷是否是修改數據
for(let i =0;i<bucket.length;i++){
var tuple = bucket[i];
if(tuple[0] === key){
tuple[1] = value;
return;
}
}
//進行添加操作
bucket.push([key,value]);
this.count += 1;
}測試代碼：
ht.put('a',12)
ht.put('b',67)
ht.put('c',88)
ht.put('d',66)
console.log('ht',ht);打印結果為：
測試成功
首先根據key獲取對應的index,在根據對應的index獲取對應的bucket;判斷bucket是否為空，如果為空，返回null,否則，線性查找bucket中的key和傳入的key是否相等，如果相等，直接返回對應的value值，否則，直接返回null。
實現代碼為：
HashTable.prototype.get = function(key){
//根據key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據index獲取對應的bucket
var bucket = this.storage[index];
//判斷是否為空
if(bucket == null){
return null;
}
//線性查找
for(let i = 0;i<bucket.length;i++){
var tuple = bucket[i];
if(tuple[0] === key){
return tuple[1];
}
}
return null;
}測試代碼：比如回去key為d的元素的值
console.log("ht.get('d'):"+ht.get('d'));
方法和獲取操作的方法相似，首先根據key獲取對應的index,在根據對應的index獲取對應的bucket;判斷bucket是否為空，如果為空，返回null,否則，線性查找bucket中的key和傳入的key是否相等，如果相等，則進行刪除，否則，直接返回null。
HashTable.prototype.remove = function(key){
//根據key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據index獲取對應的bucket
var bucket = this.storage[index];
//判斷是否為空
if(bucket == null){
return null;
}
//線性查找并通過splice()刪除
for(let i =0;i<bucket.length;i++){
var tuple = bucket[i];
if(tuple[0] === key){
bucket.splice(i,1);
this.count -= 1;
return tuole[1];
}
}
return null;
}測試代碼：刪除key為b的元素
console.log("ht.remove('b'):"+ht.remove('b'));
HashTable.prototype.isEmpty = function(){
return this.count === 0;
}代碼測試：
console.log("是否為空:"+ht.isEmpty());結果：
HashTable.prototype.size = function(){
return this.count;
}代碼測試：
console.log("哈希表元素個數:"+ht.size());結果：
上述代碼的封裝中，我們是將所有的數據項放在長度為5的數組中，因為我們使用的是鏈地址法，所以哈希表當前的數據量和總長度的比值可以大于1，這個哈希表可以無限制的插入新數據。但是，隨著數據量的增多，每一個index對應的bucket會越來越長，也會造成效率的降低，所以，在合適的情況下對數組進行擴容是很有必要的。那應該如何進行擴容呢？擴容可以簡單的將容量增大兩倍，但是在這種情況下，所有的數據項一定要同時進行修改（重新調用哈希函數，獲取到不同的位置）什么情況下擴容呢？比較常見的是：當哈希表當前的數據量和總長度的比值可以大于0.75的時候就可以進行擴容。
實現思路：首先，保存舊的數組內容，然后重置所有的屬性，遍歷保存的舊數組的內容，判斷bucket是否為空，為空的話，進行跳過，否則，取出數據，重新插入，實現代碼為：
HashTable.prototype.resize = function(newLimit){
//保存舊數組的內容
var oldStorge = this.storage;
//重置所有屬性
this.storage = [];
this.count = 0;
this.limit = newLimit;
//遍歷舊數組的內容
for(var i =0;i<oldStorge.length;i++){
//取出對應的bucket
var bucket = oldStorge[i];
//判斷backet是否為空
if(bucket == null){
continue;
}
//取出數據重新插入
for(var j =0;j<bucket.length;j++){
var tuple = bucket[j];
this.put(tuple[0],tuple[1]);
}
}
}封裝完成后，每添加一個數據項的時候，就進行是否擴容判斷，需要的話，在進行擴容，代碼為：
if(this.count > this.limit*0.75){
this.resize(this.limit*2);
}那么，有對應的擴大容量，就有對應的縮小容量，當我們刪除數據項的時候，如果剩余的數據項很小，我們就可以進行縮小容量，代碼如下：
if(this.limit > 5 && this.count < this.limit/2){
this.resize(Math.floor(this.limit/2))
} function HashTable(){
// 定義屬性
this.storage = [];
this.count = 0;
this.limit = 5;
HashTable.prototype.hashFunc = function(str,size){
//定義hashCode變量
var hashCode = 0;
//根據霍納算法，計算hashCode的值
//先將字符串轉化為數字編碼
for(var i =0;i<str.length;i++){
hashCode = 37*hashCode + str.charCodeAt(i)
}
//取余操作
var index = hashCode % size;
return index;
}
//插入和修改操作
HashTable.prototype.put = function(key,value){
//根據key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據index取出對應的bucket
var bucket = this.storage[index];
//如果值為空，給bucket賦值一個數組
if(bucket == null){
bucket = [];
this.storage[index] = bucket;
}
//判斷是否是修改數據
for(let i =0;i<bucket.length;i++){
var tuple = bucket[i];
if(tuple[0] === key){
tuple[1] = value;
return;
}
}
//進行添加操作
bucket.push([key,value]);
this.count += 1;
//進行擴容判斷
if(this.count > this.limit*0.75){
this.resize(this.limit*2);
}
}
//獲取操作
HashTable.prototype.get = function(key){
//根據key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據index獲取對應的bucket
var bucket = this.storage[index];
//判斷是否為空
if(bucket == null){
return null;
}
//線性查找
for(let i = 0;i<bucket.length;i++){
var tuple = bucket[i];
if(tuple[0] === key){
return tuple[1];
}
}
return null;
}
//刪除操作
HashTable.prototype.remove = function(key){
//根據key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據index獲取對應的bucket
var bucket = this.storage[index];
//判斷是否為空
if(bucket == null){
return null;
}
//線性查找并通過splice()刪除
for(let i =0;i<bucket.length;i++){
var tuple = bucket[i];
if(tuple[0] === key){
bucket.splice(i,1);
this.count -= 1;
return tuple[1];
//縮小容量
if(this.limit > 5 && this.count < this.limit/2){
this.resize(Math.floor(this.limit/2))
}
}
}
return null;
}
//擴容
HashTable.prototype.resize = function(newLimit){
//保存舊數組的內容
var oldStorge = this.storage;
//重置所有屬性
this.storage = [];
this.count = 0;
this.limit = newLimit;
//遍歷舊數組的內容
for(var i =0;i<oldStorge.length;i++){
//取出對應的bucket
var bucket = oldStorge[i];
//判斷backet是否為空
if(bucket == null){
continue;
}
//取出數據重新插入
for(var j =0;j<bucket.length;j++){
var tuple = bucket[j];
this.put(tuple[0],tuple[1]);
}
}
}
HashTable.prototype.isEmpty = function(){
return this.count === 0;
}
HashTable.prototype.size = function(){
return this.count;
}
}關于“JavaScript如何實現哈希表”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
