哈希表介紹

　　　　哈希表是一種非常重要的數據結構，但是很多學習編程的人一直搞不懂哈希表到底是如何實現的

　　　　　　在這一章中，我們就一點點來實現一個自己的哈希表，通過實現來李杰哈希表背后的原理和它的優勢

　　　　幾乎所有的編程語言都有直接或者間接的應用這種數據結構，

　　　　哈希表通常是基于數組進行實現的，但是相對于數組，它也很多的優勢：

　　　　　　它可以提供非常快速的插入-刪除-查找操作

　　　　　　無論多少數據，插入和刪除值需要接近常量的時間：即O(1)的時間級。實際上，只需要幾個機器指令即可完成

　　　　　　哈希表的速度比樹還要快，基本可以瞬間查找到想要的元素

　　　　　　哈希表相對于樹來說編碼要容易得多

　　　　哈希表相對于數組的一些不足：

　　　　　　哈希表中的數據是沒有順序的，所以不能以一種固定的方式（比如從小到大）來遍歷其中的元素

　　　　　　通常情況下，哈希表中的key是不允許重復的，不能放置相同的key，用于保存不同的元素

　　哈希表到底是什么呢？

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

　　　　　　似乎還是沒有說它到底是什么

　　　　　　這也是哈希表不好理解的地方，不像數組和鏈表，甚至是樹一樣直接畫出你就知道它的結構，甚至是原理了

　　　　　　它的結構就是數組，但是它神奇的地方在于對下標值的一種變換，這種變換我們可以稱之為哈希函數，通過哈希函數，通過哈希

　　　　　　函數可以獲得HashCode。

　　　　　　不著急，我們慢慢來認識它到底是什么

　　　　我們通過三個案例，案例需要你挑選某種數據結構，而你會發現最好的選擇就是哈希表

　　　　　　案例一：公司使用一種數據結構來保存所有員工

　　　　　　案例二：設計一個數據結構，保存聯系人和電話

　　　　　　案例三：使用一種數據結構存儲單詞信息，比如有50000個單詞，找到單詞后每個單詞有自己的翻譯&讀音&應用等等

　　案例一：公司員工存儲

　　案例二：聯系人和電話存儲

 　　案例三：50000個單詞的存儲

　　字母轉數字的案例一

　　　　似乎所有的案例都指向一個目標：將字符串轉成下標值

　　　　但是，怎樣才能將一個字符串轉成數組的下標值呢？

　　　　　　單詞/字符串轉下標值，其實就是字母/文字轉文字

　　　　　　怎么轉？

　　　　現在我們需要設計一種方案，可以將單詞轉成適當的下標

　　　　　　其實計算機中有很多的編碼方法就是用數字代替單詞的字符。就

　　　　　　是字符編碼。（常見的字符編碼？）

　　　　　　比如ASCII編碼：a是98，b是98，依次類推122代表z

　　　　　　我們也可以設計一個自己的編碼系統，比如a是1，b是2，c是3，依

　　　　　　次類推，z是26.

　　　　　　當然我們可以加上空格用0代表，就是27個字符（不考慮大寫問題）

　　　　　　但是，有了編碼系統后，一個單詞如何轉成數字呢？

　　　　方案一：數字相加

　　　　　　一種轉換單詞的簡單方案就是把單詞每個字符的編碼求和

　　　　　　例如單詞cats轉成數組：3+1+20+19=43，

　　　　　　那么43就作為cats單詞的下標存在數據中

　　　　問題：按照這種方案有一個很明顯的問題就是很多單詞最終的下標可能都是43.

　　　　　　比如was/tin/give/tend/moan/tick等等

　　　　　　我們知道數組中一個下標值位置只能存儲一個數據

　　　　　　如果存入后來的數據，必然會造成數據的覆蓋

　　　　　　一個下標存儲這么多單詞顯然是不合理的。

　　字母轉數字的方案二

　　　　方案二：冪的連乘

　　　　　　現在，我們想通過一種算法，讓cats轉成數字后不那么普通

　　　　　　數字相加的方案就有些過于普通了

　　　　　　有一種方案就是使用冪的連乘，什么是冪的連乘呢？

　　　　　　其實我們平時使用的大于10的數字，可以用一種冪的連乘來表示它的

　　　　　　唯一性：比如：7654 = 7 * 10的3次方 + 6 * 10的2次方 + 5 * 10 + 4

　　　　　　我們的單詞是可以使用這種方案來表示：比如cats = 3 * 27的3次方 + 1*27的2次方 + 20*27+17 = 60337

　　　　　　這樣得到的數字可以基本保證它的唯一性，不會和別的單詞重復

　　　　問題：如果一個單詞是zzzzzzzzzz(一般英文單詞不會超過10個字符)，那么得到的數字超過7000000000000，數組可以表示這么大的下標值嗎？

　　　　　　而且就算能創建這么大的數組，實時上有很多事無效的單詞

　　　　　　創建這么大的數組是沒有意義的 

　　　　兩種方案總結：

　　　　　　第一種方法(把數字相加求和)產生的數組下標太少

　　　　　　第二種方案(與27的冪相乘求和)產生的數組下標又太多

　　認識哈?；?/p>

　　　　現在需要一種壓縮方法，把冪的連乘方案系統中得到的巨大整數范圍壓縮到可接受的數組范圍中

　　　　對于英文詞典，多大的數組才合適呢？

　　　　　　如果直有50000個單詞，可能會定義一個長度為50000的數組

　　　　　　但是實際情況中，往往需要更大的空間來存儲這些單詞，因為

　　　　　　我們不能保證單詞會映射到每一個位置

　　　　　　比如兩倍的大?。?00000

　　　　如何壓縮呢？

　　　　　　現在，就找一種方法，把0到超過7000000000000的范圍，壓縮為從0到100000

　　　　　　有一種簡單的方法就是使用取余操作符，它的作用是得到一個數

　　　　　　被另外一個數整除后的余數

　　　　取余操作的實現：

　　　　　　為了看到這個方法如何工作，我們先來看一個小點的數字范圍壓縮到一個小點的空間中

　　　　　　假設把從0~199的數字，比如使用largeNumber代表，壓縮為從0到9的數字，

　　　　　　比如使用samallRange代表

　　　　　　下標值的結果：index = largeNumber % smallRange

　　　　　　當一個數被10整除時，余數一定在0~9之間

　　　　　　比如13%10=3，157%10=7

　　　　　　當然，這中間還是會有重復，不過重復的數量明顯變小了

　　　　　　因為我們的數組時100000，而只有50000個單詞

　　　　　　就好比，你在0~199中間選取5個數字，放在這個長度為10的數組中，

　　　　　　也會重復，但是重復的概率非常小。（后面我們會講到真的發生重復了應該怎么解決）

　　哈希表的一些概念

　　　　認識情況了上面的內容，相信你應該懂了哈希表的原理了，我們來看看幾個感念：

　　　　　　哈?；簩⒋髷底洲D換成數組范圍內下標的過程，我們稱之為哈?；?/p>

　　　　　　哈希函數：通常我們會將單詞轉成大數字，大數字在進行哈?；拇a實現放在一個函數中，這個函數我們稱為哈希函數

　　　　　　哈希表：最終將數據插入到的這個數組，對整個結構的封裝，我們就稱之為時一個哈希表

　　　　但是，我們還有問題需要解決：

　　　　　　雖然，我們在一個100000的數組中，放50000個單詞已經足夠

　　　　　　但是通過哈?；蟮南聵酥狄廊豢赡軙貜?，如何解決這種重復的問題呢？

　　什么是沖突？

　　　　盡管50000和單詞，我們使用了100000個位置來存儲，并且通過一種相對比較好的

　　　　哈希函數來完成。但是依然有可能會發生沖突

　　　　　　比如melioration這個單詞，通過哈希函數得到數組的下標值后，發現那個位置上

　　　　　　已經存在一個單詞demystify

　　　　　　因為它經過哈?；蠛萴elioration得到的下標實現相同的

　　　　這種情況我們稱為沖突

　　　　雖然我們不希望這種情況發生，當然更希望每個下標對應一個數據項，但是通常這是不可能的

　　　　沖突不可避免，我們只能解決沖突

　　　　就像之前0~199的數字選取5個放在長度為10的單元格中

　　　　　　如果我們隨機選出來的是33，82，11，45，90，那么最終他們的

　　　　　　位置會是3-2-1-5-0，沒有發生沖突

　　　　我們需要針對這種沖突提出一些解決方案

　　　　　　即使沖突的可能性比較小，你依然需要考慮到這種情況

　　　　　　以便發生的時候進行對應的代理代碼

　　　　如何解決這種沖突呢？常見的情況有兩種方案

　　　　　　鏈地址法　　開放地址法

　　鏈地址法

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

　　　　　　其實，如果你理解了為什么產生沖突，看到圖后就可以立馬理解鏈地址是什么含義

　　開放地址法

　　　　開放地址法的主要工作方式是尋找空白的單元格來添加重復的數據

　　　　我們還是通過圖片來了解開放地址的工作方式

 　　　　圖片解析：

　　　　　　從圖片的文字中我們可以了解到

　　　　　　開發地址法其實就是要尋找空白的位置來放置沖突的數據項

　　　　但是探索這個位置的方式不同，有三種方法：

　　　　　　線性探測　　二次探測　　再哈希法

 　　線性探測

　　　　線性探測非常好理解：線性的查找空白的單元

　　　　插入的32：

　　　　　　經過哈?；玫降膇ndex=2，但是在插入的時候，發現該位置已經又了82，怎么辦呢？

　　　　　　線性探測就是從index位置+1開始一點點查找合適的位置來放置32，什么是合適的位置呢？

　　　　　　空的位置就是合適的位置，在我們上面的例子中就是index=3的位置，這個時候32就會放在該位置。

　　　　查詢32呢？

　　　　　　查詢32和插入32比較相似。

　　　　　　首先經過哈希化得到index=2，比如2的位置結果和查詢的數值是否相同，相同那么就直接返回

　　　　　　不相同呢？線性查找，從index位置+1開始查找和32一樣的。

　　　　　　這里有一個特別需要注意的地方：如果32的位置我們之前沒有插入，是否將整個哈希表查詢一邊來確定32存不存在嗎？

　　　　　　當然不是，查詢過程有一個約定，就是查詢到空位置，就停止

　　　　　　因為查詢到這個有空位置，32之前不可能跳過空位置去其他的位置

 　　　　刪除32呢？

　　　　　　刪除操作和插入查詢比較類似，但是也有一個特別的注意點。

　　　　　　注意：刪除操作一個數據項時，不可以將這個位置下標的內容設置為null，為什么呢？

　　　　　　因為將它設置為null可能會影響我們之后查詢其他操作，所以通常刪除一個位置的數據項時，我們可以將它進行特殊處理（比如設置為-1）

　　　　　　當我們之后看到-1位置的數據項時，就知道查詢時要繼續查詢，但是插入時這個位置可以放置數據。

　　　　線性探測問題：

　　　　　　線性探測有一個比較嚴重的問題，就是聚焦，什么時聚焦呢？

　　　　　　比如我在沒有任何數據的時候，插入的是22-23-24-25-26，那么意味著下標值：2-3-4-5-6的位置都有元素

　　　　　　這叫一連串填充單元就叫做聚焦。

　　　　　　聚焦會影響哈希表的性能，無論是插入/查詢/刪除都會影響。

　　　　　　比如我們插入一個32，會發現連續的單元都不允許我們放置數據，并且在這個過程中我們需要探索多次

　　　　　　二次探測可以解決一部分這個問題，我們一起來看一看

 　　二次探測

　　　　我們剛才談到，線性探測存在的問題：

　　　　　　如果之前的數據是連續插入的，那么新插入的一個數據可能需要探測很長的距離

　　　　二次探測在線性探測的基礎上進行了優化：

　　　　　　二次探測主要優化的是探測時的步長，什么意思呢？

　　　　　　線性探測，我們可以看成時步長為1的探測，比如從下標值x開始，那么線性測試就是x+1，x+2，x+3依次探測

　　　　　　二次探測，對步長做了優化，比如從下標值x開始，x+1的2次方，x+2的2次方，x+3的3次方

　　　　　　這樣就可以一次性探測比較長的距離，比避免那些聚焦帶來的影響

　　　　二次探測的問題：

　　　　　　但是二次探測依然存在問題，比如我們連續插入的時32-1112-82-2-192，那么它們依次累加的時候步長的1相同的

　　　　　　也就是這種情況下造成步長不一的一種聚焦，還是會影響效率。（當然這種可能性相對于連續的數字會小一些）

　　　　　　怎么根本解決這個問題呢？讓每個人的步長不一樣，一起來看看再哈希法吧

　　再哈希法

　　　　為了消除線性探測和二次探測無論步長+1還是步長+平法中存在的問題，還有一種最常用的解決方案：再哈希法

　　　　再哈希法：

　　　　　　二次探測的算法產生的探測序列步長是固定的：1，4，9，16，依次類推

　　　　　　現在需要一種方法：產生一種依賴關鍵字的探測序列，而不是每個關鍵字都一樣

　　　　　　那么，不同的關鍵字即使映射到相同的數組下標，也可以使用不同的探測序列

　　　　　　再哈希法的做法就是：把關鍵字用另外一個哈希函數，再做一次哈?；?，用這次哈?；慕Y果作為步長。

　　　　　　對于指定的關鍵字，步長再整個探測中是不變的，不過不同的關鍵字使用不同的步長

　　　　第二次哈希化需要具備如下特點：

　　　　　　和第一個哈希函數不同（不要再使用上一次的哈希函數了，不然結果還是原來的位置）

　　　　　　不能輸出為0（否則，將沒有步長，每次探測都是原地踏步，算法就進入了死循環）

　　　　其實，我們不用費腦細胞來設計了，計算機專家已經設計出一種工作很好的哈希函數

　　　　　　stepSize = constant -  （Key % constant）

　　　　　　其中constant是質數，且小于數組的容量

　　　　　　例如：stepSize = 5 - （key % 5），滿足需求，并且結果不可能為0.

　　哈?；男?/p>

　　　　哈希表中執行插入和搜索操作效率是非常高的

　　　　　　如果沒有產生沖突，那么效率就會更高

　　　　　　如果發生沖突，存取時間就依賴后來的探測長度

　　　　　　平均探測長度以及平均存取時間，取決于填裝因子，隨著填裝因子變大，探測長度也越來越長

　　　　　　隨著填裝因此變大，效率下降的情況，在不同開放地址方案中比鏈地址法更嚴重，所以我們來對比一下他們的

　　　　　　效率，再決定我們選取的方案

　　　　在分析效率之前，我們先了解一個概念：裝填因子

　　　　　　裝填因子表示當前哈希表中已經包含的數據項和整個哈希表長度的比值

　　　　　　裝填因子 = 總數據項 / 哈希表長度

　　　　　　開放地址法的裝填因子最大是多少呢？1，因為它必須尋找到空白的單元才能將元素放入

　　　　　　鏈地址法的裝填因子呢？可以大于1，因為拉鏈法可以無限的延伸下去，只要你愿意。（當然后面效率就變低了）

　　線性探測效率

　　　　下面的等式顯示了線性探測時，探測序列(P)和填裝因子(L)的關系

　　　　　　對成功的查找：P=(1+1/(1-L)^2)/2

　　　　　　對不成功的查找：P=(1+1/(1-L))/2

　　　　公式來自于Knuth（算法分析領域的專家，現代計算機的先驅人物），這些公式的推導自己去看了一下，確實有些繁瑣，

　　　　這里不再給出推導過程，僅僅說明它的效率

　　　　　　圖片解析：

　　　　　　　　當填充因子是1/2時，成功的搜索需要1.5次比較，不成功的搜索需要2.5次

　　　　　　　　當填充因子為2/3時，分別需要2.0次和5.0次比較

　　　　　　　　如果填充因子更大，比較次數會非常大

　　　　　　　　應該使填充因子保持在2/3以下，最好在1/2一下，另外一面，填裝因子越低，對于給定

　　　　　　　　數量的數據項，就需要越多的空間

　　　　　　　　實際情況中，最好的填裝因子取決于存儲效率和速度之間的平衡，隨著填裝因子變小

　　　　　　　　存儲效率下降，而速度上升

　　二次探測和再哈?；?/p>

　　　　二次探測和再哈?；男阅芟啾?。它們的性能比線性探測略好

　　　　　　對成功的搜索，公式是：-log2（1-loadFactor）/loadFactor

　　　　　　對于不成功的搜索，公式是：1/（1-loadFactor）

　　　　　　　　圖片解析：

　　　　　　　　　　當填裝因子是0.5時，成功和不成功的查找平均需要2次比較

　　　　　　　　　　當填裝因子為2/3時，分別需要2.37和3.0次比較

　　　　　　　　　　當填裝因子為0.8時，分別需要2.9和5.0次

　　　　　　　　　　因此對于較高的填裝因子，對比線性探測，二次探測和再哈希法還是可以忍受的。

　　鏈地址法

　　　　鏈地址法的效率分析有些不同，一般來說比開放地址法簡單，我們來分析一下這個公式應該時怎么樣的

　　　　　　加入哈希表包含arraySize個數據項，每個數據項有一個鏈表，在表中一共包含N個數據項

　　　　　　那么，平均起來每個鏈表有多少個數據項呢？非常簡單，N / arraySize

　　　　　　有沒有發現這個公式有點眼熟？其實就是裝填因子

　　　　OK，那么我們就可以求出查找查找成功和不成功的次數了

　　　　　　成功可能只需要查找鏈表的一半即可：1 + loadFactor / 2

　　　　　　不成功呢？可能需要將整個鏈表查詢玩才知道不成功：1 + loadFactor

　　　　經過上面的比較我們可以發現，鏈地址法相對來說效率是好于開放地址法的

　　　　所以再真是開發中，使用鏈地址法的情況較多

　　　　　　因為他不會因為添加了某元素后性能急劇下降

　　　　　　比如再Java的HashMap中使用的就是鏈地址法　　　　

　　優秀的哈希函數

　　　　講了很久的哈希表理論知識，你有沒有發現再整個過程中，一個非常簡單的東西：哈希函數？

　　　　好的哈希函數應該盡可能讓計算的過程變得簡單，提高計算的效率

　　　　　　哈希表的主要優點是它的速度，所以在速度上不能足夠，那么就達不到設計的目的了

　　　　　　提高速度的一個方法就是讓哈希函數中盡量少的有乘法和除法，因為它們的性能是比較低的

　　　　設計好的哈希函數應該具備那些優點？

　　　　　　快速的計算

　　　　　　　　哈希表的優勢就在于效率，所以快速獲取到對應的hashCode非常重要

　　　　　　　　我們需要通過快速的計算來獲取到元素對應的hashCode

　　　　　　均勻的分布

　　　　　　　　哈希表中，無論是鏈地址法還是開放地址法，當多個元素映射到同一個位置的時候，都會影響效率

　　　　　　　　所以，優秀的哈希函數應該盡可能將元素映射到不同的位置，讓元素在哈希表中均勻的分布

　　快速計算：霍納法則

　　　　在前面，我們計算哈希值的時候使用的方式

　　　　　　cats = 3*27的3次方+1*27的2次方+20*27+17=60337

　　　　這種方式是直觀的計算結果，那么這種計算方式會

　　　　進行幾次乘法幾次加法呢？

　　　　　　當然，我們可能不止4項，可能有更多項

　　　　　　我們抽象一下，這個表達式其實是一個多項式：

　　　　　　a(n)x^n+a(n-1)x^(n-1)+...+a(1)x+a(0)

　　　　現在問題就變成了多項式有多少次乘法和加法：

　　　　　　乘法次數：n+(n-1)+...+1=n(n+1)/2

　　　　　　加法次數：n次

　　　　多項式的優化：霍納法則

　　　　　　解決這類求值問題的高效算法-霍納法則。在中國，霍納法則也被稱為為秦九韶算法

　　　　通過如下變換我們可以得到一種快得多的算法，即

　　　　　　Pn(x)=anx^n+a(n - 1)x^(n - 1)+...+a1x+a0=

　　　　　　((...(((anx + an -1)x + an - 2)x + an - 3)...)x+a1)x+a0

　　　　　　這種求值的安排我們稱為霍納法則

　　　　變換后，我們需要多少次乘法，多少次加法呢？

　　　　　　乘法次數：N次

　　　　　　加法次數：N次

　　　　如果使用大Q表示時間復雜度的話，我們直接從O(N方)降到了O(N)

　　均勻分布

　　　　均勻的分布

　　　　　　在設計哈希表時，我們已經有辦法處理映射到相同下標值的情況：鏈地址發或者開放地址法

　　　　　　但是無論那種方案，為了提供效率，最好的情況還是讓數據在哈希表中均勻分布

　　　　　　因此，我們需要在使用常量的地方，盡量使用質數

　　　　　　那些地方我們會使用到常量呢？

　　　　質數的使用：

　　　　　　哈希表的長度

　　　　　　N次冪的底數（我們之前使用的是27）

　　　　為什么他們使用質數，會讓哈希表分布更加均勻呢？

　　　　　　我們這里簡單來討論一下

　　哈希表的長度

　　　　哈希表的長度最好使用質數

　　　　再哈希法中質數的重要性：

　　　　　　假設表的容量不是質數，例如：表長為15（下標值0~14）

　　　　　　有一個特定關鍵字映射0，步長為5.探測序列是多少呢？

　　　　　　0 - 5 - 10 - 0 - 5 - 10，依次類推，循環下去

　　　　　　算法只嘗試著三個單元，如果這三個單元已經有了數據，那么會一直循環下去，直到程序崩潰

　　　　　　如果容量是一個質數，比如13，探測序列是多少呢？

　　　　　　0 - 5 -10 - 2 - 7 - 12 - 4 - 9 - 1 - 6 - 11 - 3，一直這樣下去

　　　　　　不僅不會產生循環，而且可以讓數據在哈希表中更加均勻的分布

　　　　鏈地址法中質數沒有那么重要，甚至在Java中故意是2的N次冪

　　Java中的HashMap

　　　　Java中的哈希表采用的是鏈地址法

　　　　HashMap的初始長度是16，每次自動擴展（我們還沒有聊到擴展的話題），長度必須是2的次冪

　　　　這是為了服務于從Key映射到index的算法

　　　　HashMap中為了提高效率，采用了位運算的方式

　　　　　　HashMap中index的計算公式：index = HashCode (Key) & (Length - 1)

　　　　　　比如計算book的hashcode，結果為十進制的3029737，二進制的101110001110101110 1001

　　　　　　假定HashMap長度是默認的16，計算Length-1的結果為十進制15，二進制的1111

　　　　　　把以上兩個結果做與運算，1011100011101011110 1001 & 1111 = 1001，十進制是0，所以index = 9

　　　　　　這樣的方式相對于取模來說性能是高的，因為計算機更運算計算二進制的數據

　　　　但是，我個人發現JavaScript中進行較大數據的位運算時會出問題，所以我的代碼實現中還是使用了取模

　　　　　　另外，我這里為了方便代碼之后向開放地址法中遷移，容量還是選擇使用質數

　　設置哈希函數

<script>
        // 設計哈希函數
        // 將字符串轉成比較大的數字：hashCode
        // 將大的數字hashCode壓縮到數組范圍（大小）之內
        function hashFunc(str, size) {
            // 定義hashCode變量
            var hashCode = 0
                // 霍納算法，來計算hashCode的值
                // cats -> Unicode編碼
            for (let 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('def', 7))
        console.log(hashFunc('ghi', 7))
        console.log(hashFunc('jkl', 7))
    </script>

　　創建哈希表

　　　　經過前面那么多內容的學習，我們現在可以真正實現自己的哈希表了

　　　　　　可能你學到這里的時候，已經感覺到數據結構的一些復雜性

　　　　　　但是如果你仔細品味，你也會發現它在設計時候的巧妙和優美

　　　　　　當你愛上它的那一刻，你也真正愛上了編程

　　　　我們這里采用鏈地址法來實現哈希表

　　　　　　實現的哈希表（基于storage的數組）每個index對應的是一個數組（bucket）（當然基于鏈表也可以）

　　　　　　bucket中存放什么呢？我們最好將key和value都放進去，我們繼續使用一個數組（其實其他語言使用元組更好）

　　　　　　最終我們的哈希表的數據格式是這樣：[ [ [ k, v],[ k, v ], [ k, v ] ], [ [ k, v],[ k, v ], [ k, v ] ] ]

　　　　封裝哈希表

    <script>
        // 封裝哈希類
        function HashTable() {
            // 屬性
            this.storage = []
            this.count = 0
            this.limit = 0

            // 方法
        }
    </script>

　　　　代碼解析：

　　　　　　我們定義了三個屬性

　　　　　　storage作為我們的數組，數組中存放相關的元素

　　　　　　count表示當前已經存在了多少數據

　　　　　　limit用于標記數組中一共可以存放多少個元素

 　　插入&修改數據

　　　　哈希表的插入和修改操作是同一個函數：

　　　　　　因為，當使用者傳入一個<Key，Value>時

　　　　　　如果原來不存該key，那么就是插入操作

　　　　　　如果已經存在該key，那么就是修改操作

                // 插入&修改操作
            HashTable.prototype.put = function(key, value) {
                // 根據key獲取對應的index
                let index = this.hashFunc(key, this.limit)
                    // 根據index取出對應的bucket
                let bucket = this.storage[index]
                    // 判斷該bucket是否為null
                if (bucket == null) {
                    bucket = []
                    this.storage[index] = bucket
                }
                // 判斷是否是修改數據
                for (let i = 0; i < bucket.length; i++) {
                    let tuple = bucket[i]
                    if (tuple[0] == key) {
                        tuple[1] = value
                        return
                    }
                }
                // 進行添加操作
                bucket.push([key, value])
                this.count += 1
            }

　　　　代碼解析：

　　　　步驟1：根據傳入的key獲取對應的hashCode，也就是數組的index

　　　　步驟2：從哈希表的index位置中取出桶（另外一個數組）

　　　　步驟3：查看上一步的bucket是否為null

　　　　　　為null，表示之前在該位置沒有放置過任何內容，那么就新建一個數組[]

　　　　步驟4：查看是否之前已經放置過key對應的value

　　　　　　如果放置過，那么就是依次代替操作，而不是插入新的數據

　　　　　　我們使用一個變量override來記錄是否是修改操作

　　　　步驟5：如果不是修改操作，那么插入新的數據

　　　　　　在bucket中push新的[key，value]即可

　　　　　　注意：這里需要將count + 1，因為數據增加了一項

　　獲取方法

 //獲取操作
            HashTable.prototype.get = function(key) {
                // 根據key獲取對應的index
                let index = this.hashFunc(key, this.limit)
                    // 根據index獲取對應的bucket
                let bucket = this.storage[index]
                    // 判斷bucket是否為null
                if (bucket == null) {
                    return null
                }
                // 有bucket，那么就進行線性查找
                for (let i = 0; i < bucket.length; i++) {
                    let tuple = bucket[i]
                    if (tuple[0] == key) {
                        return tuple[1]
                    }
                }
                // 依然沒有找到，那么返回null
                return null
            }

　　　　思路：

　　　　　　根據key獲取對應的index

　　　　　　根據index獲取對應的bucket

　　　　　　判斷bucket是否為null

　　　　　　如果為null，直接返回null

　　　　　　線性查找bucket中每一個key是否等于傳入的key

　　　　　　如果等于，那么直接返回對應的value

　　　　　　遍歷完后，依然沒有找到對應的key

　　　　　　直接return null 即可

　　刪除方法

                // 刪除方法
            HashTable.prototype.remove = function(key) {
                    // 根據key獲取對應的index
                    let index = this.hashFunc(ket, this, limit)
                        // 根據index獲取對應的bucket
                    let bucket = this.storage[index]
                        // 判斷bucket是否為null
                    if (bucket == null) return null
                        // 有bucket，那么就進行線性查找，并且刪除
                    for (let i = 0; i < bucket.length; i++) {
                        let tuple = bucket[i]
                        if (tuple[0] == key) {
                            bucket.splice(i, 1)
                            this.count--
                                return tuple[1]
                        }
                    }
                    // 依然沒有找到，那么返回null
                    return null
                }

　　　　思路：

　　　　　　根據key獲取對應的index

　　　　　　根據index獲取bucket

　　　　　　判斷bucket是否存在，如果不存在，那么直接返回null

　　　　　　線性查找bucket，尋找對應的數據，并且刪除

　　　　　　依然沒有找到，那么返回null

　　其他方法

                // 其他方法
                // 判斷哈希表是否為空
            HashTable.prototype.isEmpty = function() {
                    return this.count == 0
                }
                // 獲取哈希表中元素的個數
            HashTable.prototype.size = function() {
                return this.count
            }

　　哈希表擴容的思想

 　　　　為什么需要擴容？

　　　　　　目前，我們是將所有的數據項放在長度為7的數組中的

　　　　　　因為我們使用的是鏈地址發，loadFactor可以大于1，所以這個哈希表可以無限制的插入新數據

　　　　　　但是，隨個數據量的增多，每一個index對應的bucket會越來越長，也就造成效率的降低

　　　　　　所以，在合適的情況對數組進行擴充。比如擴容兩倍

　　　　如何進行擴充？

　　　　　　擴充可以簡單的將容量增大兩倍（不是質數嗎？質數的問題后面再討論）

　　　　　　但是這種情況下，所有的數據項一定要同時進行修改（重新調用哈希函數，來獲取到不同的位置）

　　　　　　比如hashCode=12的數據項，在length=8的時候，index=5，在長度為16的時候呢？index=12

　　　　　　這是一個耗時的過程，但是如果數組需要擴容，那么這個過程是必要的

　　　　什么情況下擴充呢？

　　　　　　比較常見的情況是loadFactor>0.75的時候進行擴容

　　　　　　比如Java的哈希表就是在裝填因子大于0.75的時候，對哈希表進行擴容

　　擴容縮容代碼

                // 哈希表擴容/縮容
            HashTable.prototype.resize = function(newLimit) {
                // 保存舊的數組內容
                let oldStorage = this.storage
                    // 重置所有屬性
                this.storage = []
                this.count = 0
                this.limit = newLimit
                    // 遍歷oldStorage中所有的bucket
                for (let i = 0; i < oldStorage.length; i++) {
                    // 取出對應的bucket
                    let bucket = oldStorage[i]
                        // 判斷bucket是否為null
                    if (bucket == null) {
                        continue
                    }
                    // bucket 中有數據，那么取出數據，重新插入
                    for (let j = 0; j < bucket.length; j++) {
                        let tuple = bucket[j]
                        this.put(tuple[0], tuple[1])
                    }
                }
            }
                    // 判斷是否需要擴容操作
                    if (this.count > this.limit * 0.75) {
                        this.resize(this.limit * 2)
                    }
                                    // 縮小容量
                            if (this.limit > 7 && this.count < this.limit * 0.25) {
                                this.resize(Math.floor(this.limit / 2))
                            }

　　容量質數

　　　　我們前面提到過，容量最好是質數

　　　　　　雖然在鏈地址法中將容量設置為質數，沒有在開放地址法中重要

　　　　　　但是其實鏈地址中質數作為容量也更利于數據的均勻分布，所以，我們還是完成一下這個步驟

　　　　我們這里先討論一個常見的面試題，判斷一個數的質數

　　　　質數的特點：

　　　　　　質數也稱為素數  

　　　　　　質數表達大于1的自然數中，只能被1和自己整除的數

　　　　OK，了解了這個特點，應該不難寫出它的算法

　　判斷是否是質數

    <script>
        // 封函數：判斷傳入的數字是否是質數
        // 特點：只能被1和自己整除，不能被2到之間的num-1數字整除
        function isPrime(num) {
            for (let i = 2; i < num; i++) {
                if (num % i == 0) {
                    return false
                }
            }
            return true
        }
        // 驗證函數
        console.log(isPrime(3))
        console.log(isPrime(9))
        console.log(isPrime(37))
        console.log(isPrime(20))
    </script>

　　更高效的質數判斷

　　　　但是，這種做法的效率并不高，為什么呢？

　　　　　　對于每個數n，其實并不需要從2判斷到n-1

　　　　　　一個數若可以進行因數分解，那么分解時得到的兩個數一定是一個小于等于sqrt(n)，一個大于等于sqrt(n)。

　　　　　　比如16可以被分分別，那么是2*8，2小于sqrt(16)，也就是4，8大于4，而4*4都是等于sqrt(n)

　　　　　　所以其實我們遍歷到等于sqrt(n)即可

　　判斷是否是質數

   <script>
        // 封裝函數判斷質數
        function isPrime(num) {
            // 獲取num的平方根
            let temp = parseInt(Math.sqrt(num))
                // 循環判斷
            for (let i = 2; i <= temp; i++) {
                if (num % i == 0) {
                    return false
                }
            }
            return true
        }
        // 驗證函數
        console.log(isPrime(3))
        console.log(isPrime(9))
        console.log(isPrime(37))
        console.log(isPrime(20))
    </script>

　　哈希表完整代碼

   <script>
        // 封裝哈希類
        function HashTable() {
            // 屬性
            this.storage = []
            this.count = 0
            this.limit = 7

            // 方法
            // 哈希函數
            HashTable.prototype.hashFunc = function(str, size) {
                    // 定義hashCode變量
                    let hashCode = 0
                        // 霍納算法，來計算hashCode的值
                        // cats -> Unicode編碼
                    for (let i = 0; i < str.length; i++) {
                        hashCode = 37 * hashCode + str.charCodeAt(i)
                    }
                    // 取余操作
                    let index = hashCode % size
                    return index
                }
                // 插入&修改操作
            HashTable.prototype.put = function(key, value) {
                    // 根據key獲取對應的index
                    let index = this.hashFunc(key, this.limit)
                        // 根據index取出對應的bucket
                    let bucket = this.storage[index]
                        // 判斷該bucket是否為null
                    if (bucket == null) {
                        bucket = []
                        this.storage[index] = bucket
                    }
                    // 判斷是否是修改數據
                    for (let i = 0; i < bucket.length; i++) {
                        let 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) {
                        let newSize = this.limit * 2
                        let newPrime = this.getPrime(newSize)
                        this.resize(newPrime)
                    }
                }
                //獲取操作
            HashTable.prototype.get = function(key) {
                    // 根據key獲取對應的index
                    let index = this.hashFunc(key, this.limit)
                        // 根據index獲取對應的bucket
                    let bucket = this.storage[index]
                        // 判斷bucket是否為null
                    if (bucket == null) {
                        return null
                    }
                    // 有bucket，那么就進行線性查找
                    for (let i = 0; i < bucket.length; i++) {
                        let tuple = bucket[i]
                        if (tuple[0] == key) {
                            return tuple[1]
                        }
                    }
                    // 依然沒有找到，那么返回null
                    return null
                }
                // 刪除方法
            HashTable.prototype.remove = function(key) {
                    // 根據key獲取對應的index
                    let index = this.hashFunc(key, this.limit)
                        // 根據index獲取對應的bucket
                    let bucket = this.storage[index]
                        // 判斷bucket是否為null
                    if (bucket == null) return null
                        // 有bucket，那么就進行線性查找，并且刪除
                    for (let i = 0; i < bucket.length; i++) {
                        let tuple = bucket[i]
                        if (tuple[0] == key) {
                            bucket.splice(i, 1)
                            this.count--
                                return tuple[1]
                                    // 縮小容量
                            if (this.limit > 7 && this.count < this.limit * 0.25) {
                                let newSize = Math.floor(this.limit / 2)
                                let newPrime = this.getPrime(newSize)
                                this.resize(newSize)
                            }
                        }
                    }
                    // 依然沒有找到，那么返回null
                    return null
                }
                // 哈希表擴容/縮容
            HashTable.prototype.resize = function(newLimit) {
                    // 保存舊的數組內容
                    let oldStorage = this.storage
                        // 重置所有屬性
                    this.storage = []
                    this.count = 0
                    this.limit = newLimit
                        // 遍歷oldStorage中所有的bucket
                    for (let i = 0; i < oldStorage.length; i++) {
                        // 取出對應的bucket
                        let bucket = oldStorage[i]
                            // 判斷bucket是否為null
                        if (bucket == null) {
                            continue
                        }
                        // bucket 中有數據，那么取出數據，重新插入
                        for (let j = 0; j < bucket.length; j++) {
                            let tuple = bucket[j]
                            this.put(tuple[0], tuple[1])
                        }
                    }
                }
                // 判斷某個數字是否是質數
            HashTable.prototype.isPrime = function(num) {
                    // 判斷num的平方根
                    let temp = parseInt(Math.sqrt(num))
                        // 循環判斷
                    for (let i = 2; i <= temp; i++) {
                        if (num % i == 0) {
                            return false
                        }
                    }
                    return true
                }
                // 獲取質數的方法
            HashTable.prototype.getPrime = function(num) {
                while (!this.isPrime(num)) {
                    num++
                }
                return num
            }
        }
        // 測試哈希表
        // 創建哈希表
        let ht = new HashTable()
            // 插入數據
        ht.put('abc', '123')
        ht.put('cba', '321')
        ht.put('nba', '521')
        ht.put('mba', '520')
            // 獲取數據
        console.log(ht.get('abc'))
            // 修改方法
        ht.put('abc', '111')
        console.log(ht.get('abc'))
            // 刪除方法
        ht.remove('abc')
        console.log(ht.get('abc'))
    </script>