一、哈希表原理

哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，幾乎所有的編程語(yǔ)言都有直接或者間接的應(yīng)用這種數(shù)據(jù)結(jié)構(gòu)，它通常是基于數(shù)組實(shí)現(xiàn)的，當(dāng)時(shí)相對(duì)于數(shù)組，它有更多的優(yōu)勢(shì)：

• 它可以提供非?？焖俚牟迦?刪除-查找操作。
• 哈希表的速度比數(shù)還要快，基本可以瞬間查找到想要的元素
• 哈希表相對(duì)于數(shù)來(lái)說(shuō)編碼要容易的多。

但是哈希表相對(duì)于數(shù)組也有一些不足：

• 哈希表中的數(shù)組是沒(méi)有順序的，所以不能以一種固定的方式（比如從小到大）來(lái)遍歷其中的元素。
• 通常情況下，哈希表中的key是不允許重復(fù)的，不能放置相同的key，用于保存不同的元素。

那么，哈希表到底是什么呢？

它的結(jié)構(gòu)是數(shù)組，但是神奇的地方在于對(duì)下標(biāo)值的一種變換，這種變換我們可以稱之為哈希函數(shù)，通過(guò)哈希函數(shù)可以獲得到HashCode。

接下來(lái)，我們可以來(lái)看一個(gè)例子：

使用一種數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)單詞信息，比如有50000個(gè)單詞，找到單詞后每個(gè)單詞有自己的具題應(yīng)用等等。我們應(yīng)該怎樣操作呢？

或許我們可以嘗試將字母轉(zhuǎn)化成合適的下標(biāo)。但是怎樣才能將一個(gè)字符轉(zhuǎn)化成數(shù)組的下標(biāo)值呢？有沒(méi)有一種方案，可以將單詞轉(zhuǎn)化成數(shù)組的下標(biāo)值呢？如果單詞轉(zhuǎn)化為數(shù)組的下標(biāo)，以后如果我們要查找某個(gè)單詞的信息，直接按照下標(biāo)值一步即可訪問(wèn)到想要的元素。那么怎樣將字符串轉(zhuǎn)化為下標(biāo)值呢？

其實(shí)計(jì)算機(jī)有很多的編碼方案就是用數(shù)字代替單詞的字符，就是字符編碼，當(dāng)然， 我們可以設(shè)計(jì)自己的編碼系統(tǒng)，比如a是1，b是2，c是3等等。但是有了編碼系統(tǒng)以后，一個(gè)單詞如何轉(zhuǎn)化成數(shù)字呢？

在這里，我們有兩種方案：

方案一：數(shù)字相加

一種轉(zhuǎn)換單詞的簡(jiǎn)便方法就是把單詞每個(gè)字符的編碼求和

例如單詞cats轉(zhuǎn)成數(shù)字：3+1+20+19=43，那么43就作為cats單詞下標(biāo)存在數(shù)組中

但是按照這種方案有一個(gè)很明顯的問(wèn)題就是很多單詞最終的下標(biāo)可能都是43

我們知道數(shù)組中一個(gè)下標(biāo)值位置只能存儲(chǔ)一個(gè)數(shù)據(jù)，如果存入后來(lái)的數(shù)據(jù)，必然會(huì)造成數(shù)據(jù)的覆蓋，故而，一個(gè)下標(biāo)存儲(chǔ)這么多單詞顯然是不合理的。

方案二：冪的連乘

其實(shí)我們平時(shí)用的大于10的數(shù)字，就可以用冪的連乘來(lái)表示其唯一性，比如：6543 = 6 *103+5 *102+4 *10 + 4

我們的單詞也可以使用這種方案來(lái)表示，比如cats = 3 * 273+1 * 272 + 20 * 27+17 = 60337

這樣得到的數(shù)字可以基本保證其唯一性，不會(huì)和別的單詞重復(fù)。

但是存在一個(gè)問(wèn)題，如果一個(gè)單詞是zzzzzzzzzz.那么得到的數(shù)字超過(guò)7000000000000.數(shù)組不一定能夠表示這么大的下標(biāo)值，就算能夠創(chuàng)建這么大的數(shù)組，事實(shí)上有很多的無(wú)效單詞，并沒(méi)有意義。

兩種方案總結(jié)：

第一種方案（把數(shù)字相加求和）產(chǎn)生的數(shù)組下標(biāo)太少，第二種方案（與27的冪相乘求和）產(chǎn)生的數(shù)組下標(biāo)又太多。

所以現(xiàn)在需要一種壓縮方法，把冪的連乘方案系統(tǒng)中得到的巨大整數(shù)范圍壓縮到可接收的數(shù)組范圍中。有一種簡(jiǎn)單的方法就是使用取余操作符，他的作用是得到一個(gè)數(shù)被另一個(gè)數(shù)整除后的余數(shù)。

取余操作的實(shí)現(xiàn)：（0-199之間的數(shù)字）

假設(shè)把從0-199的數(shù)字,(large)，壓縮為0-9的數(shù)字(small)

下標(biāo)的結(jié)果index = large % small

當(dāng)一個(gè)數(shù)被10整除時(shí)，余數(shù)一定在0-9之間

例如16%10 = 6,23%10 = 3

這中間還是會(huì)有重復(fù)，不過(guò)重復(fù)的數(shù)量明顯小了，比如說(shuō)在0-199中間取5個(gè)數(shù)字，放在一個(gè)長(zhǎng)度為10的數(shù)組，也會(huì)重復(fù)，但是重復(fù)的概率非常小。

二、哈希表的概念

了解了哈希化的原理，我們就可以來(lái)看幾個(gè)概念：

哈?；簩⒋髷?shù)字轉(zhuǎn)化為數(shù)組范圍內(nèi)下標(biāo)的過(guò)程，就稱之為哈?；?/p>

哈希函數(shù)：例如將單詞轉(zhuǎn)化為大數(shù)字，大數(shù)字在進(jìn)行哈?；拇a實(shí)現(xiàn)放在一個(gè)函數(shù)中，這個(gè)函數(shù)就是哈希函數(shù)。

哈希表：最終將數(shù)據(jù)插入到這個(gè)數(shù)組，對(duì)整個(gè)結(jié)構(gòu)的封裝，就可以稱之為一個(gè)哈希表。

三、哈?；瘺_突問(wèn)題

前面提到了，通過(guò)哈希化的下標(biāo)值依然可能會(huì)重復(fù)，就會(huì)導(dǎo)致沖突，比如說(shuō)我們將0-199的數(shù)字選取5個(gè)放在長(zhǎng)度為10的單元格里，如果我們隨機(jī)選出來(lái)的是33，45，27，86，92，那么最終他們的位置會(huì)是3-5-7-6-2，沒(méi)有發(fā)生沖突，但是其中如果還有一個(gè)86，一個(gè)66呢？此時(shí)就會(huì)發(fā)生沖突。該如何解決這個(gè)問(wèn)題呢？

常用的解決方案有兩種：

1、鏈地址法

鏈地址法是一種比較常見的解決沖突的方案（也稱拉鏈法）

如下圖所示：

創(chuàng)建了一個(gè)內(nèi)存為10的數(shù)組，現(xiàn)在，需要將一些數(shù)字存到數(shù)組內(nèi)部，這些數(shù)字哈?；罂赡軙?huì)重復(fù)，將下標(biāo)值相同的數(shù)通過(guò)鏈表或者數(shù)組鏈接起來(lái)的方法叫做鏈地址法。當(dāng)我們要查找某值的時(shí)候，就可以先根據(jù)其下標(biāo)找到對(duì)應(yīng)的鏈表或者數(shù)組再在其內(nèi)部尋找。

從圖片中，我們可以看出，鏈地址法解決沖突的辦法是每個(gè)數(shù)組單元中存儲(chǔ)的不再是單個(gè)數(shù)據(jù)而是一個(gè)鏈條，這個(gè)鏈條常用的結(jié)構(gòu)是數(shù)組或者鏈條。那在具體應(yīng)用中應(yīng)該采用哪一種方式呢？其實(shí)這兩種方法都可以，效率上也差不多，當(dāng)然在某些實(shí)現(xiàn)中，會(huì)將新插入的數(shù)據(jù)放在數(shù)組或者鏈表的最前面，這種情況最好用鏈表。因?yàn)閿?shù)組再首位插入數(shù)據(jù)是需要所有其他項(xiàng)后移的的，而鏈表就沒(méi)有這樣的問(wèn)題。

2、開放地址法

開放地址法的主要工作方式是尋找空白的單元格來(lái)添加重復(fù)的數(shù)據(jù)。如下圖所示：

如果有一個(gè)數(shù)字32，現(xiàn)在要將其插入到數(shù)組中，我們的解決方案為：

• 新插入的32本來(lái)應(yīng)該插入到52的位置，但是該位置已經(jīng)包含數(shù)據(jù)，
• 可以發(fā)現(xiàn)3、5、9的位置是沒(méi)有任何內(nèi)容的
• 這個(gè)時(shí)候就可以尋找對(duì)應(yīng)的空白位置來(lái)放這個(gè)數(shù)據(jù)

但是探索這個(gè)位置的方式不同，有三種方式：

1、線性探索

即線性的查找空白單元

插入32

• 經(jīng)過(guò)哈?；玫降膇ndex=2，但是在插入的時(shí)候，發(fā)現(xiàn)該位置已經(jīng)有52
• 此時(shí)就從index+1的位置開始一點(diǎn)點(diǎn)查找合適的位置來(lái)放置32
• 探測(cè)到的第一個(gè)空的位置就是該值插入的位置

查詢32

• 首先經(jīng)過(guò)哈希化得到index= 2，比較2的位置結(jié)果和查詢的數(shù)值是否相同，相同則直接返回
• 不相同則線性查找，從index位置+1查找和32一樣的。

需要注意的是：如果32的位置之前沒(méi)有插入，并不需要將整個(gè)哈希表查詢一遍來(lái)確定該值是否存在，而是如果查詢到空位置，就停止。因?yàn)?2之前不可能跳過(guò)空位置去其他的位置。

線性探測(cè)也有一個(gè)問(wèn)題就是：如果之前插入的數(shù)據(jù)是連續(xù)插入的，則新插入的數(shù)據(jù)就需要很長(zhǎng)的探測(cè)距離。

2、二次探索

二次探索就在線性探索的基礎(chǔ)上進(jìn)行了優(yōu)化。

線性探測(cè)，我們可以看做是步長(zhǎng)為1的探測(cè)，比如從下標(biāo)值x開始，從x+1,x+2,x+3依次探測(cè)。

二次探測(cè)對(duì)步長(zhǎng)做了優(yōu)化，比如從下標(biāo)值x開始,x+12,x+22,x+32依次探測(cè)。

但是二次探測(cè)依然存在問(wèn)題：比如我們連續(xù)插入的是32-112-82-42-52，那么他們依次累加的時(shí)候步長(zhǎng)是相同的，也就是這種情況下會(huì)造成步長(zhǎng)不一的一種聚集，還是會(huì)影響效率，怎樣解決這個(gè)問(wèn)題呢？來(lái)看看再哈希法。

3、再哈希法

再哈希法的做法就是：把關(guān)鍵字用另一個(gè)哈希函數(shù)在做一次哈希化，用這次哈?；慕Y(jié)果作為步長(zhǎng)，對(duì)于指定的關(guān)鍵字，步長(zhǎng)在整個(gè)探測(cè)中是不變的，不同的關(guān)鍵字使用不同的步長(zhǎng)。

第二次哈?；枰邆湟韵绿攸c(diǎn)：

和第一個(gè)哈希函數(shù)不同

不能輸出為0（否則，將沒(méi)有步長(zhǎng)，每次嘆詞都是原地踏步，算法進(jìn)入死循環(huán)）

而計(jì)算機(jī)專家已經(jīng)設(shè)計(jì)好了一種工作很好的哈希函數(shù)。

stepSize = constant - (key % constant)

其中constant是質(zhì)數(shù)，且小于數(shù)組的容量，key是第一次哈?；玫降闹怠?/p>

例如：stepSize = 5-(key%5),滿足需求，并且結(jié)果不可能為0。

四、哈希函數(shù)的實(shí)現(xiàn)

哈希表的主要優(yōu)點(diǎn)在于它的速度，提高速度的一個(gè)方法就是讓哈希函數(shù)中有盡量少的乘法和除法，設(shè)計(jì)好的哈希函數(shù)需要具備以下優(yōu)點(diǎn)：

（1）快速的計(jì)算

（2）均勻的分布

來(lái)具體實(shí)現(xiàn)一下：

首先我們所實(shí)現(xiàn)的哈希函數(shù)最主要的操作是：將字符創(chuàng)轉(zhuǎn)化為比較大的數(shù)字和將大的數(shù)字壓縮到數(shù)組范圍之內(nèi)。如下所示：

 function hashFunc(str,size){
            //定義hashCode變量
            var hashCode = 0;
            //根據(jù)霍納算法，計(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;
        }

代碼測(cè)試：

 console.log( hashFunc('abc',7));
       console.log( hashFunc('cba',7));
       console.log( hashFunc('nba',7));
       console.log( hashFunc('rgt',7));

測(cè)試結(jié)果為：

可以發(fā)現(xiàn)我們得到的字符串對(duì)應(yīng)的下標(biāo)值分布還是很均勻的。

五、封裝哈希表

這里我將采用鏈地址法來(lái)實(shí)現(xiàn)哈希表：

其中定義了三個(gè)屬性：

• storage:作為數(shù)組，存放相關(guān)元素
• count：記錄當(dāng)前已存放的數(shù)據(jù)量
• -limit:標(biāo)記數(shù)組中一共可以存放多少數(shù)據(jù)

實(shí)現(xiàn)的哈希表（基于storage的數(shù)組）每個(gè)index對(duì)應(yīng)的是一個(gè)數(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ù)通過(guò)原型添加進(jìn)去：

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、插入&修改操作

哈希表的插入和修改操作是同一個(gè)函數(shù)，因?yàn)楫?dāng)使用者傳入一個(gè)<key,value>時(shí)，如果原來(lái)不存在該key，那么就是插入操作，如果已經(jīng)存在該key,對(duì)應(yīng)的就是修改操作。

具體實(shí)現(xiàn)思路為：先根據(jù)傳入的key獲取對(duì)應(yīng)的hashCode，即數(shù)組的index,接著從哈希表的Index位置中取出另一個(gè)數(shù)組（bucket）,查看上一步的bucket是否為空，如果為空的話，表示之前在該位置沒(méi)有放置過(guò)任何的內(nèi)容，則新建一個(gè)數(shù)組[]；再查看是否之前已經(jīng)放置過(guò)key對(duì)應(yīng)的value,如果放置過(guò)，那么就是依次替換操作，而不是插入新的數(shù)據(jù)，如果不是修改操作的話，那么插入新的數(shù)據(jù)，并且讓數(shù)據(jù)項(xiàng)加1。

實(shí)現(xiàn)代碼為：

 //插入和修改操作
        HashTable.prototype.put = function(key,value){
            //根據(jù)key獲取對(duì)應(yīng)的index
            var index = this.hashFunc(str,this.limit);
            //根據(jù)index取出對(duì)應(yīng)的bucket
            var bucket = this.storage[index];
            //如果值為空，給bucket賦值一個(gè)數(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;
                }
            }
            //進(jìn)行添加操作
            bucket.push([key,value]);
            this.count += 1;
        }

測(cè)試代碼：

 ht.put('a',12)
 ht.put('b',67)
 ht.put('c',88)
 ht.put('d',66)
 console.log('ht',ht);

打印結(jié)果為：

測(cè)試成功

2、獲取操作

首先根據(jù)key獲取對(duì)應(yīng)的index,在根據(jù)對(duì)應(yīng)的index獲取對(duì)應(yīng)的bucket;判斷bucket是否為空，如果為空，返回null,否則，線性查找bucket中的key和傳入的key是否相等，如果相等，直接返回對(duì)應(yīng)的value值，否則，直接返回null。

實(shí)現(xiàn)代碼為：

HashTable.prototype.get = function(key){
    //根據(jù)key獲取對(duì)應(yīng)的index
    var index = this.hashFunc(key,this.limit);
    //根據(jù)index獲取對(duì)應(yīng)的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;
}

測(cè)試代碼：比如回去key為d的元素的值

 console.log("ht.get('d'):"+ht.get('d'));

3、刪除操作

方法和獲取操作的方法相似，首先根據(jù)key獲取對(duì)應(yīng)的index,在根據(jù)對(duì)應(yīng)的index獲取對(duì)應(yīng)的bucket;判斷bucket是否為空，如果為空，返回null,否則，線性查找bucket中的key和傳入的key是否相等，如果相等，則進(jìn)行刪除，否則，直接返回null。

 HashTable.prototype.remove = function(key){
             //根據(jù)key獲取對(duì)應(yīng)的index
            var index = this.hashFunc(key,this.limit);
             //根據(jù)index獲取對(duì)應(yīng)的bucket
            var bucket = this.storage[index];
            //判斷是否為空
            if(bucket == null){
                return null;
            }
            //線性查找并通過(guò)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;
        }

測(cè)試代碼：刪除key為b的元素

 console.log("ht.remove('b'):"+ht.remove('b'));

4、判斷哈希表是否為空

HashTable.prototype.isEmpty = function(){
            return this.count === 0;
        }

代碼測(cè)試：

 console.log("是否為空:"+ht.isEmpty());

結(jié)果：

5、獲取哈希表的元素個(gè)數(shù)

HashTable.prototype.size = function(){
            return this.count;
        }

代碼測(cè)試：

console.log("哈希表元素個(gè)數(shù):"+ht.size());

結(jié)果：

七、哈希表擴(kuò)容

1、哈希表擴(kuò)容思想

上述代碼的封裝中，我們是將所有的數(shù)據(jù)項(xiàng)放在長(zhǎng)度為5的數(shù)組中，因?yàn)槲覀兪褂玫氖擎湹刂贩?，所以哈希表?dāng)前的數(shù)據(jù)量和總長(zhǎng)度的比值可以大于1，這個(gè)哈希表可以無(wú)限制的插入新數(shù)據(jù)。但是，隨著數(shù)據(jù)量的增多，每一個(gè)index對(duì)應(yīng)的bucket會(huì)越來(lái)越長(zhǎng)，也會(huì)造成效率的降低，所以，在合適的情況下對(duì)數(shù)組進(jìn)行擴(kuò)容是很有必要的。那應(yīng)該如何進(jìn)行擴(kuò)容呢？擴(kuò)容可以簡(jiǎn)單的將容量增大兩倍，但是在這種情況下，所有的數(shù)據(jù)項(xiàng)一定要同時(shí)進(jìn)行修改（重新調(diào)用哈希函數(shù)，獲取到不同的位置）什么情況下擴(kuò)容呢？比較常見的是：當(dāng)哈希表當(dāng)前的數(shù)據(jù)量和總長(zhǎng)度的比值可以大于0.75的時(shí)候就可以進(jìn)行擴(kuò)容。

2、哈希表擴(kuò)容實(shí)現(xiàn)

實(shí)現(xiàn)思路：首先，保存舊的數(shù)組內(nèi)容，然后重置所有的屬性，遍歷保存的舊數(shù)組的內(nèi)容，判斷bucket是否為空，為空的話，進(jìn)行跳過(guò)，否則，取出數(shù)據(jù)，重新插入，實(shí)現(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++){
                //取出對(duì)應(yīng)的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]);
                }
            }
        }

封裝完成后，每添加一個(gè)數(shù)據(jù)項(xiàng)的時(shí)候，就進(jìn)行是否擴(kuò)容判斷，需要的話，在進(jìn)行擴(kuò)容，代碼為：

if(this.count > this.limit*0.75){
   this.resize(this.limit*2);
     }

那么，有對(duì)應(yīng)的擴(kuò)大容量，就有對(duì)應(yīng)的縮小容量，當(dāng)我們刪除數(shù)據(jù)項(xiàng)的時(shí)候，如果剩余的數(shù)據(jù)項(xiàng)很小，我們就可以進(jìn)行縮小容量，代碼如下：

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ù)霍納算法，計(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獲取對(duì)應(yīng)的index
       var index = this.hashFunc(key,this.limit);
       //根據(jù)index取出對(duì)應(yīng)的bucket
       var bucket = this.storage[index];
       //如果值為空，給bucket賦值一個(gè)數(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;
           }
       }
       //進(jìn)行添加操作
       bucket.push([key,value]);
       this.count += 1;
       //進(jìn)行擴(kuò)容判斷
       if(this.count > this.limit*0.75){
           this.resize(this.limit*2);
       }
   }

   //獲取操作
   HashTable.prototype.get = function(key){
       //根據(jù)key獲取對(duì)應(yīng)的index
       var index = this.hashFunc(key,this.limit);
       //根據(jù)index獲取對(duì)應(yīng)的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獲取對(duì)應(yīng)的index
       var index = this.hashFunc(key,this.limit);
        //根據(jù)index獲取對(duì)應(yīng)的bucket
       var bucket = this.storage[index];
       //判斷是否為空
       if(bucket == null){
           return null;
       }
       //線性查找并通過(guò)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;
   }
   //擴(kuò)容
   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++){
           //取出對(duì)應(yīng)的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;
   }
}
 

到此這篇關(guān)于詳解JavaScript實(shí)現(xiàn)哈希表的文章就介紹到這了,更多相關(guān)JavaScript哈希表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！