詳解JavaScript實現(xiàn)哈希表
一、哈希表原理
哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，幾乎所有的編程語言都有直接或者間接的應用這種數(shù)據(jù)結(jié)構(gòu)，它通常是基于數(shù)組實現(xiàn)的，當時相對于數(shù)組，它有更多的優(yōu)勢：
- 它可以提供非?？焖俚牟迦?刪除-查找操作。
- 哈希表的速度比數(shù)還要快，基本可以瞬間查找到想要的元素
- 哈希表相對于數(shù)來說編碼要容易的多。
但是哈希表相對于數(shù)組也有一些不足：
- 哈希表中的數(shù)組是沒有順序的，所以不能以一種固定的方式（比如從小到大）來遍歷其中的元素。
- 通常情況下，哈希表中的key是不允許重復的，不能放置相同的key，用于保存不同的元素。
那么，哈希表到底是什么呢？
它的結(jié)構(gòu)是數(shù)組，但是神奇的地方在于對下標值的一種變換，這種變換我們可以稱之為哈希函數(shù)，通過哈希函數(shù)可以獲得到HashCode。
接下來，我們可以來看一個例子：
使用一種數(shù)據(jù)結(jié)構(gòu)來存儲單詞信息，比如有50000個單詞，找到單詞后每個單詞有自己的具題應用等等。我們應該怎樣操作呢？
或許我們可以嘗試將字母轉(zhuǎn)化成合適的下標。但是怎樣才能將一個字符轉(zhuǎn)化成數(shù)組的下標值呢？有沒有一種方案，可以將單詞轉(zhuǎn)化成數(shù)組的下標值呢？如果單詞轉(zhuǎn)化為數(shù)組的下標，以后如果我們要查找某個單詞的信息，直接按照下標值一步即可訪問到想要的元素。那么怎樣將字符串轉(zhuǎn)化為下標值呢？
其實計算機有很多的編碼方案就是用數(shù)字代替單詞的字符，就是字符編碼，當然， 我們可以設計自己的編碼系統(tǒng)，比如a是1，b是2，c是3等等。但是有了編碼系統(tǒng)以后，一個單詞如何轉(zhuǎn)化成數(shù)字呢？
在這里，我們有兩種方案：
方案一：數(shù)字相加
一種轉(zhuǎn)換單詞的簡便方法就是把單詞每個字符的編碼求和
例如單詞cats轉(zhuǎn)成數(shù)字：3+1+20+19=43，那么43就作為cats單詞下標存在數(shù)組中
但是按照這種方案有一個很明顯的問題就是很多單詞最終的下標可能都是43
我們知道數(shù)組中一個下標值位置只能存儲一個數(shù)據(jù)，如果存入后來的數(shù)據(jù)，必然會造成數(shù)據(jù)的覆蓋，故而，一個下標存儲這么多單詞顯然是不合理的。
方案二：冪的連乘
其實我們平時用的大于10的數(shù)字，就可以用冪的連乘來表示其唯一性，比如：6543 = 6 *103+5 *102+4 *10 + 4
我們的單詞也可以使用這種方案來表示，比如cats = 3 * 273+1 * 272 + 20 * 27+17 = 60337
這樣得到的數(shù)字可以基本保證其唯一性，不會和別的單詞重復。
但是存在一個問題，如果一個單詞是zzzzzzzzzz.那么得到的數(shù)字超過7000000000000.數(shù)組不一定能夠表示這么大的下標值，就算能夠創(chuàng)建這么大的數(shù)組，事實上有很多的無效單詞，并沒有意義。
兩種方案總結(jié)：
第一種方案（把數(shù)字相加求和）產(chǎn)生的數(shù)組下標太少，第二種方案（與27的冪相乘求和）產(chǎn)生的數(shù)組下標又太多。
所以現(xiàn)在需要一種壓縮方法，把冪的連乘方案系統(tǒng)中得到的巨大整數(shù)范圍壓縮到可接收的數(shù)組范圍中。有一種簡單的方法就是使用取余操作符，他的作用是得到一個數(shù)被另一個數(shù)整除后的余數(shù)。
取余操作的實現(xiàn)：（0-199之間的數(shù)字）
假設把從0-199的數(shù)字,(large)，壓縮為0-9的數(shù)字(small)
下標的結(jié)果index = large % small
當一個數(shù)被10整除時，余數(shù)一定在0-9之間
例如16%10 = 6,23%10 = 3
這中間還是會有重復，不過重復的數(shù)量明顯小了，比如說在0-199中間取5個數(shù)字，放在一個長度為10的數(shù)組，也會重復，但是重復的概率非常小。
二、哈希表的概念
了解了哈?；脑?，我們就可以來看幾個概念：
哈?；簩⒋髷?shù)字轉(zhuǎn)化為數(shù)組范圍內(nèi)下標的過程，就稱之為哈?；?/p>
哈希函數(shù)：例如將單詞轉(zhuǎn)化為大數(shù)字，大數(shù)字在進行哈?；拇a實現(xiàn)放在一個函數(shù)中，這個函數(shù)就是哈希函數(shù)。
哈希表：最終將數(shù)據(jù)插入到這個數(shù)組，對整個結(jié)構(gòu)的封裝，就可以稱之為一個哈希表。
三、哈?；瘺_突問題
前面提到了，通過哈?；南聵酥狄廊豢赡軙貜?，就會導致沖突，比如說我們將0-199的數(shù)字選取5個放在長度為10的單元格里，如果我們隨機選出來的是33，45，27，86，92，那么最終他們的位置會是3-5-7-6-2，沒有發(fā)生沖突，但是其中如果還有一個86，一個66呢？此時就會發(fā)生沖突。該如何解決這個問題呢？
常用的解決方案有兩種：
1、鏈地址法
鏈地址法是一種比較常見的解決沖突的方案（也稱拉鏈法）
如下圖所示：
創(chuàng)建了一個內(nèi)存為10的數(shù)組，現(xiàn)在，需要將一些數(shù)字存到數(shù)組內(nèi)部，這些數(shù)字哈?；罂赡軙貜停瑢⑾聵酥迪嗤臄?shù)通過鏈表或者數(shù)組鏈接起來的方法叫做鏈地址法。當我們要查找某值的時候，就可以先根據(jù)其下標找到對應的鏈表或者數(shù)組再在其內(nèi)部尋找。
從圖片中，我們可以看出，鏈地址法解決沖突的辦法是每個數(shù)組單元中存儲的不再是單個數(shù)據(jù)而是一個鏈條，這個鏈條常用的結(jié)構(gòu)是數(shù)組或者鏈條。那在具體應用中應該采用哪一種方式呢？其實這兩種方法都可以，效率上也差不多，當然在某些實現(xiàn)中，會將新插入的數(shù)據(jù)放在數(shù)組或者鏈表的最前面，這種情況最好用鏈表。因為數(shù)組再首位插入數(shù)據(jù)是需要所有其他項后移的的，而鏈表就沒有這樣的問題。
2、開放地址法
開放地址法的主要工作方式是尋找空白的單元格來添加重復的數(shù)據(jù)。如下圖所示：
如果有一個數(shù)字32，現(xiàn)在要將其插入到數(shù)組中，我們的解決方案為：
- 新插入的32本來應該插入到52的位置，但是該位置已經(jīng)包含數(shù)據(jù)，
- 可以發(fā)現(xiàn)3、5、9的位置是沒有任何內(nèi)容的
- 這個時候就可以尋找對應的空白位置來放這個數(shù)據(jù)
但是探索這個位置的方式不同，有三種方式：
1、線性探索
即線性的查找空白單元
插入32
- 經(jīng)過哈?；玫降膇ndex=2，但是在插入的時候，發(fā)現(xiàn)該位置已經(jīng)有52
- 此時就從index+1的位置開始一點點查找合適的位置來放置32
- 探測到的第一個空的位置就是該值插入的位置
查詢32
- 首先經(jīng)過哈?；玫絠ndex= 2，比較2的位置結(jié)果和查詢的數(shù)值是否相同，相同則直接返回
- 不相同則線性查找，從index位置+1查找和32一樣的。
需要注意的是：如果32的位置之前沒有插入，并不需要將整個哈希表查詢一遍來確定該值是否存在，而是如果查詢到空位置，就停止。因為32之前不可能跳過空位置去其他的位置。
線性探測也有一個問題就是：如果之前插入的數(shù)據(jù)是連續(xù)插入的，則新插入的數(shù)據(jù)就需要很長的探測距離。
2、二次探索
二次探索就在線性探索的基礎上進行了優(yōu)化。
線性探測，我們可以看做是步長為1的探測，比如從下標值x開始，從x+1,x+2,x+3依次探測。
二次探測對步長做了優(yōu)化，比如從下標值x開始,x+12,x+22,x+32依次探測。
但是二次探測依然存在問題：比如我們連續(xù)插入的是32-112-82-42-52，那么他們依次累加的時候步長是相同的，也就是這種情況下會造成步長不一的一種聚集，還是會影響效率，怎樣解決這個問題呢？來看看再哈希法。
3、再哈希法
再哈希法的做法就是：把關鍵字用另一個哈希函數(shù)在做一次哈希化，用這次哈希化的結(jié)果作為步長，對于指定的關鍵字，步長在整個探測中是不變的，不同的關鍵字使用不同的步長。
第二次哈?；枰邆湟韵绿攸c：
和第一個哈希函數(shù)不同
不能輸出為0（否則，將沒有步長，每次嘆詞都是原地踏步，算法進入死循環(huán)）
而計算機專家已經(jīng)設計好了一種工作很好的哈希函數(shù)。
stepSize = constant - (key % constant)
其中constant是質(zhì)數(shù)，且小于數(shù)組的容量，key是第一次哈?；玫降闹?。
例如：stepSize = 5-(key%5),滿足需求，并且結(jié)果不可能為0。
四、哈希函數(shù)的實現(xiàn)
哈希表的主要優(yōu)點在于它的速度，提高速度的一個方法就是讓哈希函數(shù)中有盡量少的乘法和除法，設計好的哈希函數(shù)需要具備以下優(yōu)點：
（1）快速的計算
（2）均勻的分布
來具體實現(xiàn)一下：
首先我們所實現(xiàn)的哈希函數(shù)最主要的操作是：將字符創(chuàng)轉(zhuǎn)化為比較大的數(shù)字和將大的數(shù)字壓縮到數(shù)組范圍之內(nèi)。如下所示：
function hashFunc(str,size){
//定義hashCode變量
var hashCode = 0;
//根據(jù)霍納算法，計算hashCode的值
//先將字符串轉(zhuǎn)化為數(shù)字編碼
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));
測試結(jié)果為：
可以發(fā)現(xiàn)我們得到的字符串對應的下標值分布還是很均勻的。
五、封裝哈希表
這里我將采用鏈地址法來實現(xiàn)哈希表：
其中定義了三個屬性：
- storage:作為數(shù)組，存放相關元素
- count：記錄當前已存放的數(shù)據(jù)量
- -limit:標記數(shù)組中一共可以存放多少數(shù)據(jù)
實現(xiàn)的哈希表（基于storage的數(shù)組）每個index對應的是一個數(shù)組（bucket），bucket里面存放的是（key和value),最終哈希表的數(shù)據(jù)格式是：[[[k,v],[k,v],[k,v],[[k,v],[k,v]],[k,v]]
如下圖所示：
代碼如下：
function HashTable(){
// 定義屬性
this.storage = [];
this.count = 0;
this.limit = 8;
}
在將我們前面封裝好的哈希函數(shù)通過原型添加進去：
function HashTable(){
// 定義屬性
this.storage = [];
this.count = 0;
this.limit = 8;
HashTable.prototype.hashFunc = function(str,size){
//定義hashCode變量
var hashCode = 0;
//先將字符串轉(zhuǎn)化為數(shù)字編碼
for(var i =0;i<str.length;i++){
hashCode = 37*hashCode + str.charCodeAt(i)
}
//取余操作
var index = hashCode % size;
return index;
}
}
六、哈希表操作
1、插入&修改操作
哈希表的插入和修改操作是同一個函數(shù)，因為當使用者傳入一個<key,value>時，如果原來不存在該key，那么就是插入操作，如果已經(jīng)存在該key,對應的就是修改操作。
具體實現(xiàn)思路為：先根據(jù)傳入的key獲取對應的hashCode，即數(shù)組的index,接著從哈希表的Index位置中取出另一個數(shù)組（bucket）,查看上一步的bucket是否為空，如果為空的話，表示之前在該位置沒有放置過任何的內(nèi)容，則新建一個數(shù)組[]；再查看是否之前已經(jīng)放置過key對應的value,如果放置過，那么就是依次替換操作，而不是插入新的數(shù)據(jù)，如果不是修改操作的話，那么插入新的數(shù)據(jù)，并且讓數(shù)據(jù)項加1。
實現(xiàn)代碼為：
//插入和修改操作
HashTable.prototype.put = function(key,value){
//根據(jù)key獲取對應的index
var index = this.hashFunc(str,this.limit);
//根據(jù)index取出對應的bucket
var bucket = this.storage[index];
//如果值為空，給bucket賦值一個數(shù)組
if(bucket === null){
bucket = [];
this.storage[index] = bucket;
}
//判斷是否是修改數(shù)據(jù)
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);
打印結(jié)果為：
測試成功
2、獲取操作
首先根據(jù)key獲取對應的index,在根據(jù)對應的index獲取對應的bucket;判斷bucket是否為空，如果為空，返回null,否則，線性查找bucket中的key和傳入的key是否相等，如果相等，直接返回對應的value值，否則，直接返回null。
實現(xiàn)代碼為：
HashTable.prototype.get = function(key){
//根據(jù)key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據(jù)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'));
3、刪除操作
方法和獲取操作的方法相似，首先根據(jù)key獲取對應的index,在根據(jù)對應的index獲取對應的bucket;判斷bucket是否為空，如果為空，返回null,否則，線性查找bucket中的key和傳入的key是否相等，如果相等，則進行刪除，否則，直接返回null。
HashTable.prototype.remove = function(key){
//根據(jù)key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據(jù)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'));
4、判斷哈希表是否為空
HashTable.prototype.isEmpty = function(){
return this.count === 0;
}
代碼測試：
console.log("是否為空:"+ht.isEmpty());
結(jié)果：
5、獲取哈希表的元素個數(shù)
HashTable.prototype.size = function(){
return this.count;
}
代碼測試：
console.log("哈希表元素個數(shù):"+ht.size());
結(jié)果：
七、哈希表擴容
1、哈希表擴容思想
上述代碼的封裝中，我們是將所有的數(shù)據(jù)項放在長度為5的數(shù)組中，因為我們使用的是鏈地址法，所以哈希表當前的數(shù)據(jù)量和總長度的比值可以大于1，這個哈希表可以無限制的插入新數(shù)據(jù)。但是，隨著數(shù)據(jù)量的增多，每一個index對應的bucket會越來越長，也會造成效率的降低，所以，在合適的情況下對數(shù)組進行擴容是很有必要的。那應該如何進行擴容呢？擴容可以簡單的將容量增大兩倍，但是在這種情況下，所有的數(shù)據(jù)項一定要同時進行修改（重新調(diào)用哈希函數(shù)，獲取到不同的位置）什么情況下擴容呢？比較常見的是：當哈希表當前的數(shù)據(jù)量和總長度的比值可以大于0.75的時候就可以進行擴容。
2、哈希表擴容實現(xiàn)
實現(xiàn)思路：首先，保存舊的數(shù)組內(nèi)容，然后重置所有的屬性，遍歷保存的舊數(shù)組的內(nèi)容，判斷bucket是否為空，為空的話，進行跳過，否則，取出數(shù)據(jù)，重新插入，實現(xiàn)代碼為：
HashTable.prototype.resize = function(newLimit){
//保存舊數(shù)組的內(nèi)容
var oldStorge = this.storage;
//重置所有屬性
this.storage = [];
this.count = 0;
this.limit = newLimit;
//遍歷舊數(shù)組的內(nèi)容
for(var i =0;i<oldStorge.length;i++){
//取出對應的bucket
var bucket = oldStorge[i];
//判斷backet是否為空
if(bucket == null){
continue;
}
//取出數(shù)據(jù)重新插入
for(var j =0;j<bucket.length;j++){
var tuple = bucket[j];
this.put(tuple[0],tuple[1]);
}
}
}
封裝完成后，每添加一個數(shù)據(jù)項的時候，就進行是否擴容判斷，需要的話，在進行擴容，代碼為：
if(this.count > this.limit*0.75){
this.resize(this.limit*2);
}
那么，有對應的擴大容量，就有對應的縮小容量，當我們刪除數(shù)據(jù)項的時候，如果剩余的數(shù)據(jù)項很小，我們就可以進行縮小容量，代碼如下：
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;
//根據(jù)霍納算法，計算hashCode的值
//先將字符串轉(zhuǎn)化為數(shù)字編碼
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){
//根據(jù)key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據(jù)index取出對應的bucket
var bucket = this.storage[index];
//如果值為空，給bucket賦值一個數(shù)組
if(bucket == null){
bucket = [];
this.storage[index] = bucket;
}
//判斷是否是修改數(shù)據(jù)
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){
//根據(jù)key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據(jù)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){
//根據(jù)key獲取對應的index
var index = this.hashFunc(key,this.limit);
//根據(jù)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){
//保存舊數(shù)組的內(nèi)容
var oldStorge = this.storage;
//重置所有屬性
this.storage = [];
this.count = 0;
this.limit = newLimit;
//遍歷舊數(shù)組的內(nèi)容
for(var i =0;i<oldStorge.length;i++){
//取出對應的bucket
var bucket = oldStorge[i];
//判斷backet是否為空
if(bucket == null){
continue;
}
//取出數(shù)據(jù)重新插入
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實現(xiàn)哈希表的文章就介紹到這了,更多相關JavaScript哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了原生JS實現(xiàn)點擊數(shù)字小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-04-04
JavaScript出于安全方面的考慮，不允許跨域調(diào)用其他頁面的對象。但在安全限制的同時也給注入iframe或是ajax應用上帶來了不少麻煩。這里把涉及到跨域的一些問題簡單地整理一下2015-04-04
這篇文章主要介紹了Javascript中的方法和匿名方法,以實例形式較為詳細的分析了javascript中方法及匿名方法的定義與使用技巧,需要的朋友可以參考下2015-06-06
JavaScript數(shù)據(jù)類型轉(zhuǎn)換實例(其他類型轉(zhuǎn)字符串、數(shù)值型、布爾類型)
這篇文章主要給大家介紹了關于JavaScript數(shù)據(jù)類型轉(zhuǎn)換的相關資料,本文分別介紹了其他類型轉(zhuǎn)為字符串、其他類型轉(zhuǎn)為數(shù)值型以及其他類型轉(zhuǎn)為布爾類型的方法,需要的朋友可以參考下2021-07-07
JavaScript遍歷table表格中的某行某列并打印其值
這篇文章主要介紹了JavaScript遍歷table表格中的某行某列并打印其值,需要的朋友可以參考下2014-07-07
Generator 函數(shù)是 ES6 提供的一種異步編程解決方案，語法行為與傳統(tǒng)函數(shù)完全不同。這篇文章給大家介紹Es6 Generator函數(shù)的相關知識，感興趣的朋友一起看看吧2018-02-02
這篇文章主要介紹了BootStrap表單控件之文本域textarea,需要的朋友可以參考下2017-05-05
這篇文章主要介紹js實現(xiàn)頁面跳轉(zhuǎn)重定向的幾種方式,需要的朋友可以參考下2014-05-05
javascript定時變換圖片實例代碼，需要的朋友可以參考一下2013-03-03
List Information About the Binary Files Used by an Applicati
List Information About the Binary Files Used by an Application...2007-06-06