【數(shù)據(jù)結(jié)構(gòu)與算法——TypeScript】

哈希表(HashTable)

哈希表介紹和特性

• 哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，但是很多學(xué)習(xí)編程的人一直搞不懂哈希表到底是如何實(shí)現(xiàn)的。

  • 在這一章節(jié)中，我門就一點(diǎn)點(diǎn)來實(shí)現(xiàn)一個(gè)自己的哈希表。
  • 通過實(shí)現(xiàn)來理解哈希表背后的原理和它的優(yōu)勢。

• 幾乎所有的編程語言都有直接或者間接的應(yīng)用這種數(shù)據(jù)結(jié)構(gòu)。

• 哈希表通常是基于數(shù)組進(jìn)行實(shí)現(xiàn)的，但是相對(duì)于數(shù)組，它也很多的優(yōu)勢：

  • 口 它可以提供非?？焖俚牟迦?甽除-查找操作：
  • 口 無論多少數(shù)據(jù)，插入和刪除值都接近常量的時(shí)間：即O(1)的時(shí)間與雜度。實(shí)際上，只需要幾個(gè)機(jī)器指令即可完成；
  • 口 哈希表的速度比樹還要快，基本可以瞬間查找到想要的元素：
  • 口 哈希表相對(duì)于樹來說編碼要容易很多；

• 哈希表相對(duì)于數(shù)組的一些不足：

  • 口 哈希表中的數(shù)據(jù)是沒有順序的，所以不能以一種固定的方式(出如從小到大)來遍力其中的元素（沒有特妹處理情況下）
  • 口 通常情況下，哈希表中的key是不允許重復(fù)的，不能放置相同的key，用于保存不同的元素。

哈希表到底是什么呢？

• 口 我們只是說了一下它的優(yōu)勢，似乎還是沒有說它到底長什么樣子？
• 口 這也是哈希表不好理解的地方，不像數(shù)組和鏈表，甚至是樹一樣直接畫出你就知道它的結(jié)構(gòu)，甚至是原理了。
• 口 ????? 它的結(jié)構(gòu)就是數(shù)組，但是它神奇的地方在于對(duì)數(shù)組下標(biāo)值的一種變換， 這種變換我們可以使用哈希函數(shù)，通過哈希函數(shù)可以獲取到 HashCode.
• 口 不著急，我們慢慢來認(rèn)識(shí)它到底是什么。
  

?? 我們通過二個(gè)案例，案例需要你挑選某種數(shù)據(jù)結(jié)構(gòu)，而你會(huì)發(fā)現(xiàn)最好的 選擇就是哈希表

• 口 案例一：公司使用一種數(shù)據(jù)結(jié)構(gòu)來保存所有員工；
• 口 案例二：使用一種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)單詞信息，比如有50000個(gè)單詞。找到單詞后每個(gè)單詞有自己的翻譯&讀音&應(yīng)用等等：

?? 案例一：公司員工存儲(chǔ)

• ?? 案例介紹：

  • 口 假如一家公司有1000個(gè)員工，現(xiàn)在我們需要將這些員工的信息使用某種數(shù)據(jù)結(jié)構(gòu)來保存起來
  • 口 你會(huì)采用什么數(shù)據(jù)結(jié)構(gòu)呢？

• ? 方案一：數(shù)組

  • 口 一種方案是按照順序?qū)⑺械膯T工依次存入一個(gè)長度為1000的數(shù)組中。
  • 口 每個(gè)員工的信息都保存在數(shù)組的某個(gè)位置上。
  • 口 但是我們要查看某個(gè)具體員工的信息怎么辦呢？一個(gè)個(gè)找嗎？不太好找。
  • 口 數(shù)組最大的優(yōu)勢是什么？通過下標(biāo)值去獲取信息。
  • 口 所以為了可以通過數(shù)組快速定位到某個(gè)員工，最好給員工信息中添加一個(gè)員工編號(hào)(工號(hào))， 而編號(hào)對(duì)應(yīng)的就是員工的下標(biāo)值。
  • 口 當(dāng)查找某個(gè)員工的信息時(shí)，通過員工編號(hào)可以快速定位到員工的信息位置，

• ? 方案二：鏈表

  • 口 鏈表對(duì)應(yīng)插入和刪除數(shù)據(jù)有一定的優(yōu)勢。
  • 口 但是對(duì)于獲取員工的信息，每次都必須從頭遍歷到尾，這種方式顯然不是特別適合我們這里。

• ? 最終方案：

  • 口 這樣看最終方案似乎就是數(shù)組了， 但是數(shù)組還是有缺點(diǎn)，什么缺點(diǎn)呢？
  • 口 但是如果我們只知道員工的姓名， 比如why，但是不知道why的員工編號(hào)，你怎么辦呢？
  • 只能線性查找？效率非常的低
  • 能不能有一種辦法，讓why的名字和它的員工編號(hào)產(chǎn)生直接的關(guān)系呢？
    • 也就是通過why這個(gè)名字，我們就能獲取到它的素引值，而再通過索引值我就能獲取到why的信息呢？
    • 口 這樣的方案已經(jīng)存在了，就是使用哈希函數(shù)，讓某個(gè)key的信息和索引值對(duì)應(yīng)起來。

?? 案例二：50000個(gè)單詞的存儲(chǔ)

• ?? 案例介紹：
  • 口 使用一種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)單詞信息，比如有50000個(gè)單詞.
  • 口 找到單詞后每個(gè)單詞有自己的翻譯&讀音&應(yīng)用等等
• ? 方案一：數(shù)組？
  • 口 這個(gè)案例更加明顯能感受到數(shù)組的缺陷
  • 口 拿到一個(gè)單詞 lridescent，我想知道這個(gè)單詞的翻譯/讀音/應(yīng)用。
  • 口 怎么可以從數(shù)組中查到這個(gè)單詞的位置呢？
  • 口 線性查找？50000次比較？
  • 口 如果你使用數(shù)組來實(shí)現(xiàn)這個(gè)功能，效率會(huì)非常非常低，而且你一定沒有學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu)。
• ? 方案二：鏈表？
  • 口 不需要考慮了吧？
• ? 方案三：有沒有一種方案，可以將單詞轉(zhuǎn)成數(shù)組的下標(biāo)值呢
  • 口 如果單詞轉(zhuǎn)成數(shù)組的下標(biāo)，那么以后我們要查找某個(gè)單詞的信息，直接按照下標(biāo)值一步即可訪問到想要的元素

????? 字母轉(zhuǎn)數(shù)字的方案

似乎所有的案例都指向了一目標(biāo)：將字符串轉(zhuǎn)成下標(biāo)值
但是，怎樣才能將一個(gè)字符串轉(zhuǎn)成數(shù)組的下標(biāo)值呢？
口 單詞/字符串轉(zhuǎn)下標(biāo)值，其實(shí)就是字母/文字轉(zhuǎn)數(shù)字
口 怎么轉(zhuǎn)？

• 現(xiàn)在我們需要設(shè)計(jì)一種方案，可以將單詞轉(zhuǎn)成適當(dāng)?shù)南聵?biāo)值：

  • 口 其實(shí)計(jì)算機(jī)中有很多的編碼方案就是用數(shù)字代皆單詞的字符。就是字符編碼。（常見的字符編碼？）
  • 口 比如ASCII編碼：a是97，b是98，依次類推122代表z
  • 口 我們也可以設(shè)計(jì)一個(gè)自己的編碼系統(tǒng)，比如a是1，b是2，c是3，依 次類推，z是26。
  • 口 當(dāng)然我們可以加上空格用0代替，就是27個(gè)字符（不考慮大寫問題）
  • 口 但是，有了編碼系統(tǒng)后，一個(gè)單詞如何轉(zhuǎn)成數(shù)字呢？

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

  • 口 一種轉(zhuǎn)換單詞的簡單方案就是把單詞每個(gè)字符的編碼求和。
  • 口 例如單詞cats轉(zhuǎn)成數(shù)字：3+1+20+19=43.
  • 那么43就作為cats單詞的下標(biāo)存在數(shù)組中。
  • ??【問題】：按照這種方案有一個(gè)很明顯的問題就是很多單詞最終的下標(biāo)可能都是43。
    • 口 比如was/tin/give/tend/moan/tick等等。
    • 口 我們知道數(shù)組中一個(gè)下標(biāo)值位置只能存儲(chǔ)一個(gè)數(shù)據(jù)如果存入后來的數(shù)據(jù)，必然會(huì)造成數(shù)據(jù)的獲蓋。
    • 一個(gè)下標(biāo)存儲(chǔ)這么多單詞顯然是不合理的。
    • 口 雖然后面的方案也會(huì)出現(xiàn)，但是要盡雖避免。

• ? 方案二：冪的連乘

  • 口 現(xiàn)在，我們想通過一種算法，讓cats轉(zhuǎn)成數(shù)字后不那么普通。
  • 口 數(shù)字相加的方案就有些過于普通了。
  • 口 有一種方案就是使用冪的連乘，什么是冪的連乘呢？
    • 其實(shí)我們平時(shí)使用的大于10的數(shù)字，可以用一種系的連乘來表示它的唯一性：

      比如：7654 = 7 *10³ + 6 * 10² + 5 * 10 + 4

• 口 我們的單詞也可以使用這種方案來表示：

  • 比如 cats= 327³+127²+20*27+17= 60337

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

• ??【問題】：如果一個(gè)單詞是 zzzzzzzzzz(一般英文單詞不會(huì)超過10個(gè)宇符)。那么得到的數(shù)字超過7000000000000。

  • 口 數(shù)組可以表示這么大的下標(biāo)值嗎？
  • 口 而且就算能創(chuàng)建這么大的數(shù)組，事實(shí)上有很多是無效的單詞。
  • 口 創(chuàng)建這么大的數(shù)組是沒有意義的

• ?? 兩種方案總結(jié):

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

數(shù)據(jù)的哈?；^程

下標(biāo)的壓縮算法

• 現(xiàn)在需要一種壓縮方法，把冪的連乘方案系統(tǒng)中得到的巨大整數(shù)范圍壓縮到可接受的數(shù)組范圍中。

• ? 對(duì)于英文詞典，多大的數(shù)組才合適呢？

  • 如果只有50000個(gè)單詞，可能會(huì)定義一個(gè)長度為50000的數(shù)組。
  • 但是實(shí)際情況中，往往需要更大的空間來存儲(chǔ)這些單詞。
  • ?? 因?yàn)槲覀儾荒鼙ＷC單詞會(huì)映射到每一個(gè)位置。
    • 比如兩倍的大?。?00000。

• ?? 如何壓縮呢？

  • 現(xiàn)在，就找一種方法，把0到超過7000000000000的范圍，壓縮為從0到100000。
  • 有一種簡單的方法就是使用取余操作符，它的作用是得到一個(gè)數(shù)被另外一個(gè)數(shù)整除后的余數(shù)。

• ? 取余操作的實(shí)現(xiàn)：

  • 為了看到這個(gè)方法如何工作，我們先來看一個(gè)小點(diǎn)的數(shù)字范圍壓縮到一個(gè)小點(diǎn)的空間中。
  • ?? 假設(shè)把從0~199的數(shù)字，比如使用largeNumber代表，壓縮為從0到9的數(shù)字，比如使用smallRange代表。
  • ?? 下標(biāo)值的結(jié)果：index = largeNumber % smallRange
  • 當(dāng)一個(gè)數(shù)被10整除時(shí)，余數(shù)一定在0~9之間;
  • 比如13%10=3，157%10=7。
  • 當(dāng)然，這中間還是會(huì)有重復(fù)，不過重復(fù)的數(shù)量明顯變小了。
  • 因?yàn)槲覀兊臄?shù)組是100000，而只有50000個(gè)單詞。
  • 就好比，你在0~199中間選取5個(gè)數(shù)字，放在這個(gè)長度為10的數(shù)組中，也會(huì)重復(fù)，但是重復(fù)的概率非常小。(后面我們會(huì)講到真的發(fā)生重復(fù)了應(yīng)該怎么解決)

哈希表的一些概念

• 認(rèn)識(shí)了上面的內(nèi)容，相信你應(yīng)該懂了哈希表的原理了，我們來看看幾個(gè)概念：

  • ?? 哈?；?/strong>：將大數(shù)字轉(zhuǎn)化成數(shù)組范圍內(nèi)下標(biāo)的過程，我們就稱之為哈?；?/strong>。
  • ?? 哈希函數(shù)：通常我們會(huì)將單詞轉(zhuǎn)成大數(shù)字，大數(shù)字在進(jìn)行哈希化的代碼實(shí)現(xiàn)放在一個(gè)函數(shù)中，這個(gè)函數(shù)我們稱為哈希函數(shù)。
  • ?? 哈希表：最終將數(shù)據(jù)插入到的這個(gè)數(shù)組，對(duì)整個(gè)結(jié)構(gòu)的封裝，我們就稱之為是一個(gè)哈希表。

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

  • 雖然，我們?cè)谝粋€(gè)100000的數(shù)組中，放50000個(gè)單詞已經(jīng)足夠。
  • 但是通過哈希化后的下標(biāo)值依然可能會(huì)重復(fù)，如何解決這種重復(fù)的問題呢？

• ?? 好的哈希函數(shù)應(yīng)該盡可能讓計(jì)算的過程變得簡單，提高計(jì)算的效率。
  • 哈希表的主要優(yōu)點(diǎn)是它的速度，所以在速度上不能滿足，那么就達(dá)不到設(shè)計(jì)的目的了。
  • 提高速度的一個(gè)辦法就是讓哈希函數(shù)中盡量少的有乘法和除法。因?yàn)樗鼈兊?strong>性能是比較低的。
• ?? 設(shè)計(jì)好的哈希函數(shù)應(yīng)該具備哪些優(yōu)點(diǎn)呢？
  • ? 快速的計(jì)算
    • ? 哈希表的優(yōu)勢就在于效率，所以快速獲取到對(duì)應(yīng)的hashCode非常重要。
    • ? 我們需要通過快速的計(jì)算來獲取到元素對(duì)應(yīng)的hashCode
  • ? 均勻的分布
    • ? 哈希表中，無論是鏈地址法還是開放地址法，當(dāng)多個(gè)元素映射到同一個(gè)位置的時(shí)候，都會(huì)影響效率。
    • ? 所以，優(yōu)秀的哈希函數(shù)應(yīng)該盡可能將元素映射到不同的位置，讓元素在哈希表中均勻的分布。

快速計(jì)算 - 霍納法則

• ? 在前面，我們計(jì)算哈希值的時(shí)候使用的方式: ?? cats = 3273+1272+20*27+17= 60337
• ? 這種方式是直觀的計(jì)算結(jié)果，那么這種計(jì)算方式會(huì)進(jìn)行幾次乘法幾次加法呢？
  • ? 當(dāng)然，我們可能不止4項(xiàng)，可能有更多項(xiàng)
  • ? 我們抽象一下，這個(gè)表達(dá)式其實(shí)是一個(gè)多項(xiàng)式： a_(n)xⁿ+a_(n-1)x^(n-1)+…+a₍₁₎x+a₍₀₎
• ? 現(xiàn)在問題就變成了多項(xiàng)式有多少次乘法和加法：
  • ? 乘法次數(shù)：n＋(n－1)＋…＋1＝n(n+1)/2
  • ? 加法次數(shù)：n次
  • ? O(N2)

?????

• ? 多項(xiàng)式的優(yōu)化：????? 霍納法則

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

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

  Pn(x)=a_nxⁿ+a_(n－1)x^^(n-1)+…+a₁x+a₀=((…(((a_nx+a_n－1)x+a_n－2)x+a_n－3)…)x+a₁)x+a₀

  • 這種求值的方式我們稱為霍納法則。

  • ?? 當(dāng)x=4時(shí),2x⁴ - 3x³ + 5x² + x - 7 的值?

    • 先將其轉(zhuǎn)換為的形式 x(x(x(2x - 3 ) + 5 ) +1 ) -7

    系數(shù)	2	-3	5	1	-7
    x=4	2	2x2-3 =5	4x5+5=25	4x25+1 = 101	4x101-7=397

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

  • ? 乘法次數(shù)：N次
  • ? 加法次數(shù)：N次。

• ? 如果使用大O表示時(shí)間復(fù)雜度的話，我們直接從O(N2)降到了O(N)。

均勻分布

• ? 均勻的分布
  • ? 在設(shè)計(jì)哈希表時(shí)，我們已經(jīng)有辦法處理映射到相同下標(biāo)值的情況：鏈地址法或者開放地址法。
  • ? 但是無論哪種方案，為了提供效率，最好的情況還是讓數(shù)據(jù)在哈希表中均勻分布。
  • ? 因此，我們需要在使用常量的地方，盡量使用質(zhì)數(shù)。
  • ? 哪些地方我們會(huì)使用到常量呢？
• ? ??質(zhì)數(shù)的使用：
  • ? 哈希表的長度。
  • ? N次冪的底數(shù)(我們之前使用的是27)
• ? 為什么他們使用質(zhì)數(shù)，會(huì)讓哈希表分布更加均勻呢？
  • ? 質(zhì)數(shù)和其他數(shù)相乘的結(jié)果相比于其他數(shù)字更容易產(chǎn)生唯一性的結(jié)果，減少哈希沖突。
  • ? Java中的N次冪的底數(shù)選擇的是31，是經(jīng)過長期觀察分布結(jié)果得出的；

N次冪的底數(shù)

• ? 這里采用質(zhì)數(shù)的原因是為了產(chǎn)生的數(shù)據(jù)不按照某種規(guī)律遞增。
  • ? 比如我們這里有一組數(shù)據(jù)是按照4進(jìn)行遞增的：0 4 8 12 16，將其映射到長度為8的哈希表中。
  • ? 它們的位置是多少呢？0 - 4 - 0 - 4，依次類推。
  • ? 如果我們哈希表本身不是質(zhì)數(shù)，而我們遞增的數(shù)量可以使用質(zhì)數(shù)，比如5，那么 0 5 10 15 20
  • ? 它們的位置是多少呢？0 - 5 - 2 - 7 - 4，依次類推。也可以盡量讓數(shù)據(jù)均勻的分布。
  • ? 我們之前使用的是27，這次可以使用一個(gè)接近的數(shù)，比如31/37/41等等。一個(gè)比較常用的數(shù)是31或37。
• ? 總之，質(zhì)數(shù)是一個(gè)非常神奇的數(shù)字。
• ? 這里建議兩處都使用質(zhì)數(shù)：
  • ? 哈希表中數(shù)組的長度。
  • ? N次冪的底數(shù)。

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

    /**
     * 哈希函數(shù),將key映射成index
     * @param key 轉(zhuǎn)換的key
     * @param max 數(shù)組的長度(最大的數(shù)值)
     * @returns 索引值
     */
    function hashFunc(key: string, max: number): number {
    // 1.計(jì)算 hashCode: cats => 60337 (27為底)
    let hascode = 0;
    const length = key.length;
    for (let i = 0; i < length; i++) {
        //   霍納法則
        hascode = 31 * hascode + key.charCodeAt(i);
    }
    // 2.計(jì)算索引
    const index = hascode % max;
    return index;
    }

    console.log(hashFunc('abc', 7));
    console.log(hashFunc('nba', 7));
    console.log(hashFunc('cbd', 7));
    console.log(hashFunc('mba', 7));
    console.log(hashFunc('dfc', 7));
    console.log(hashFunc('rft', 7));

哈希表創(chuàng)建和操作

?? 創(chuàng)建哈希表

• ?? 我們這里采用鏈地址法來實(shí)現(xiàn)哈希表：

  • ?? 實(shí)現(xiàn)的哈希表(基于storage的數(shù)組)每個(gè)index對(duì)應(yīng)的是一個(gè)數(shù)組(bucket)。(當(dāng)然基于鏈表也可以。)
  • ?? bucket中存放什么呢？我們最好將key和value都放進(jìn)去，我們繼續(xù)使用一個(gè)數(shù)組。(其實(shí)其他語言使用元組更好)
  • ?? 最終我們的哈希表的數(shù)據(jù)格式是這樣：[[ [k，v]，[k，v]，[k，v] ] ，[ [k，v]，[k，v] ]，[ [k，v] ] ]

• ??????? 代碼解析：

  • 我們定義了三個(gè)屬性：
    • ?? storage作為我們的數(shù)組，數(shù)組中存放相關(guān)的元素。
    • ?? count表示當(dāng)前已經(jīng)存在了多少數(shù)據(jù)。
    • ?? limit用于標(biāo)記數(shù)組中一共可以存放多少個(gè)元素。

    class HashTable<T = any> {
      // 創(chuàng)建一個(gè)數(shù)組,用來存儲(chǔ)鏈地址法中的鏈(數(shù)組)
      private storage: [string, T][][] = [];
      // 數(shù)組長度
      private length: number = 7;
      // 記錄已經(jīng)存放元素的個(gè)數(shù)
      private count: number = 0;
    }
  

?? 插入/修改數(shù)據(jù)put

• ?? 哈希表的插入和修改操作是同一個(gè)函數(shù)：

  • ? 因?yàn)?，?dāng)使用者傳入一個(gè)<Key，Value>時(shí)
  • ? 如果原來不存該key，那么就是插入操作。
  • ? 如果已經(jīng)存在該key，那么就是修改操作。

• ??????? 代碼解析：

  • ?? 步驟1：根據(jù)傳入的key獲取對(duì)應(yīng)的hashCode，也就是數(shù)組的index

  • ?? 步驟2：從哈希表的index位置中取出桶(另外一個(gè)數(shù)組)

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

    • 為null，表示之前在該位置沒有放置過任何的內(nèi)容，那么就新建一個(gè)數(shù)組[]

  • ?? 步驟4：查看是否之前已經(jīng)放置過key對(duì)應(yīng)的value

    • ? 如果放置過，那么就是依次替換操作，而不是插入新的數(shù)據(jù)。
    • ? 我們使用一個(gè)變量override來記錄是否是修改操作

  • ?? 步驟5：如果不是修改操作，那么插入新的數(shù)據(jù)。

    • ? 在bucket中push新的[key，value]即可。
    • ? 注意：這里需要將count+1，因?yàn)閿?shù)據(jù)增加了一項(xiàng)。
      

• put的流程圖
  

?? 獲取數(shù)據(jù) get

• ?? 獲取數(shù)據(jù)：

  • 根據(jù)key獲取對(duì)應(yīng)的value

  • ??????? 代碼解析：

    • ?? 步驟1：根據(jù)key獲取hashCode(也就是index)
    • ?? 步驟2：根據(jù)index取出bucket。
    • ?? 步驟3：因?yàn)槿绻鸼ucket都是null，那么說明這個(gè)位置之前并沒有插入過數(shù)據(jù)。
    • ?? 步驟4：有了bucket，就遍歷，并且如果找到，就將對(duì)應(yīng)的value返回即可。
    • ?? 步驟5：沒有找到，返回null

      // 獲取數(shù)據(jù) 根據(jù)key獲取對(duì)應(yīng)的value
      get(key: string): T | undefined {
        // 1. 根據(jù)key獲取索引值
        const index = this.hashFunc(key, this.length);
        // 2. 獲取bucket
        const bucket = this.storage[index];
        if (!bucket) return undefined;
        // 3. 對(duì)比bucket 遍歷
        for (let i = 0; i < bucket.length; i++) {
          const tuple = bucket[i];
          const tupleKey = tuple[0];
          const tupleVal = tuple[1];
          if (key === tupleKey) {
            return tupleVal;
          }
        }
        return undefined;
      }
    

刪除數(shù)據(jù)

• ?? 刪除數(shù)據(jù)：

  • ? 我們根據(jù)對(duì)應(yīng)的key，刪除對(duì)應(yīng)的key/value

• ? 代碼解析：

  • ? 思路和獲取數(shù)據(jù)相似

    delete(key: string): T | undefined {
      // 1. 根據(jù)key獲取索引值
      const index = this.hashFunc(key, this.length);
      // 2. 獲取bucket
      const bucket = this.storage[index];
      if (!bucket) return undefined;
      // 3. 對(duì)比bucket 遍歷
      for (let i = 0; i < bucket.length; i++) {
        const tuple = bucket[i];
        const tupleKey = tuple[0];
        const tupleVal = tuple[1];
        if (key === tupleKey) {
          bucket.splice(i, 1);
          this.count--;
          return tupleVal;
        }
      }
      return undefined;
    }
  

哈希表的自動(dòng)擴(kuò)容

哈希表擴(kuò)容的思想

• ?為什么需要擴(kuò)容？
  • ? 目前，我們是將所有的數(shù)據(jù)項(xiàng)放在長度為7的數(shù)組中的。
  • ? 因?yàn)槲覀兪褂玫氖?strong>鏈地址法，loadFactor可以大于1，所以這個(gè)哈希表可以無限制的插入新數(shù)據(jù)。
  • ? 但是，隨著數(shù)據(jù)量的增多，每一個(gè)index對(duì)應(yīng)的****bucket會(huì)越來越長，也就造成效率的降低。
  • ? 所以，在合適的情況對(duì)數(shù)組進(jìn)行擴(kuò)容，比如擴(kuò)容兩倍。
• ??如何進(jìn)行擴(kuò)容？
  • ? 擴(kuò)容可以簡單的將容量增大兩倍(不是質(zhì)數(shù)嗎？質(zhì)數(shù)的問題后面再討論)
  • ? 但是這種情況下，所有的數(shù)據(jù)項(xiàng)一定要同時(shí)進(jìn)行修改(重新調(diào)用哈希函數(shù)，來獲取到不同的位置)
  • ? 比如hashCode=12的數(shù)據(jù)項(xiàng)，在length=8的時(shí)候，index=4。在長度為16的時(shí)候呢？index=12。
  • ? 這是一個(gè)耗時(shí)的過程，但是如果數(shù)組需要擴(kuò)容，那么這個(gè)過程是必要的。
    -?? 什么情況下擴(kuò)容呢？
  • ? 比較常見的情況是loadFactor>0.75的時(shí)候進(jìn)行擴(kuò)容。
  • ? 比如Java的哈希表就是在裝填因子大于0.75的時(shí)候，對(duì)哈希表進(jìn)行擴(kuò)容。

擴(kuò)容函數(shù)

• ??????? 代碼解析：
  • ?? 步驟1：先將之前數(shù)組保存起來，因?yàn)槲覀兇龝?huì)兒會(huì)將storeage = []
  • ?? 步驟2：之前的屬性值需要重置。
  • ?? 步驟3：遍歷所有的數(shù)據(jù)項(xiàng)，重新插入到哈希表中。
• ?在什么時(shí)候調(diào)用擴(kuò)容方法呢？
  • ?? 在每次添加完新的數(shù)據(jù)時(shí)，都進(jìn)行判斷。(也就是put方法中)
• ?? 修改容量

  // 修改容量
  private resize(newLimit: number) {
    // 設(shè)置新的長度
    this.length = newLimit;
    // 獲取原來所有數(shù)據(jù),并且重新放入新的容量數(shù)組中
    // 對(duì)數(shù)據(jù)進(jìn)行初始化
    const oldStorage = this.storage;
    this.storage = [];
    this.count = 0;
    // 獲取原來的數(shù)據(jù),放入新的數(shù)組中
    oldStorage.forEach((bucket) => {
      if (!bucket) return;
      for (let i = 0; i < bucket.length; i++) {
        const tuple = bucket[i];
        this.put(tuple[0], tuple[1]);
      }
    });
  }

• ?? 擴(kuò)容

    // 擴(kuò)容:發(fā)現(xiàn)loadFactor>0.75
      const loadFactor = this.count / this.length;
      if (loadFactor > 0.75) {
        this.resize(this.length * 2);
      }
  

• ?? 縮容文章來源地址http://www.zghlxwxcb.cn/news/detail-641326.html

  // 縮容:發(fā)現(xiàn)loadFactor < 0.25
  const loadFactor = this.count / this.length;
  if (loadFactor < 0.25 && this.length > 7) {
    this.resize(Math.floor(this.length / 2));
  }        

容量質(zhì)數(shù)

• ? 我們前面提到過，容量最好是質(zhì)數(shù)。
  • ? 雖然在鏈地址法中將容量設(shè)置為質(zhì)數(shù)，沒有在開放地址法中重要，
  • ? 但是其實(shí)鏈地址法中質(zhì)數(shù)作為容量也更利于數(shù)據(jù)的均勻分布。所以，我們還是完成一下這個(gè)步驟。
• ? 我們這里先討論一個(gè)常見的面試題，判斷一個(gè)數(shù)是質(zhì)數(shù)。
• ? 質(zhì)數(shù)的特點(diǎn)：
  • ? 質(zhì)數(shù)也稱為素?cái)?shù)。
  • ? 質(zhì)數(shù)表示大于1的自然數(shù)中，只能被1和自己整除的數(shù)。
• ? OK，了解了這個(gè)特點(diǎn)，應(yīng)該不難寫出它的算法：
• ?? 更高效的質(zhì)數(shù)判斷
  • ? 對(duì)于每個(gè)數(shù)n，其實(shí)并不需要從2判斷到n-1
  • ? 一個(gè)數(shù)若可以進(jìn)行因數(shù)分解，那么分解時(shí)得到的兩個(gè)數(shù)一定是一個(gè)小于等于sqrt(n)，一個(gè)大于等于sqrt(n)。
    • ? 注意： sqrt是square root的縮寫，表示平方根；
  • ? 比如16可以被分別。那么是2*8，2小于sqrt(16)，也就是4，8大于4。而4*4都是等于sqrt(n)
  • ? 所以其實(shí)我們遍歷到等于sqrt(n)即可

  /**
   * 根據(jù)傳入的數(shù)字,判斷是否是一個(gè)質(zhì)數(shù)
   * @param num 傳入要判斷的數(shù)字
   * @returns 是否是質(zhì)數(shù)
   */
  export function isPrime(num: number): boolean {
    const sqrt = Math.sqrt(num);
    for (let i = 2; i <= sqrt; i++) {
      if (num % i === 0) return false;
    }
    return true;
  }

擴(kuò)容的質(zhì)數(shù)

• 首先，將初始的limit為8，改成7
  • ? 前面，我們有對(duì)容量進(jìn)行擴(kuò)展，方式是：原來的容量 x 2
• ? 比如之前的容量是7，那么擴(kuò)容后就是14。14還是一個(gè)質(zhì)數(shù)嗎？
• ? 顯然不是，所以我們還需要一個(gè)方法，來實(shí)現(xiàn)一個(gè)新的容量為質(zhì)數(shù)的算法。
• ? 那么我們可以封裝獲取新的容量的代碼(質(zhì)數(shù))

  isPrime(num: number): boolean {
    const sqrt = Math.sqrt(num);
    for (let i = 2; i <= sqrt; i++) {
      if (num % i === 0) return false;
    }
    return true;
  }
  private getNextPrime(num: number) {
    // 判斷容量是否為質(zhì)數(shù)
    let newPrime = num;
    while (!this.isPrime(newPrime)) {
      newPrime++;
    }
    return newPrime;
  }
  // 修改容量
  private resize(newLimit: number) {
    // 設(shè)置新的長度
    let newPrime = this.getNextPrime(newLimit);
    if (newPrime < 7) newPrime = 7;
    this.length = newPrime;

    // 獲取原來所有數(shù)據(jù),并且重新放入新的容量數(shù)組中
    // 對(duì)數(shù)據(jù)進(jìn)行初始化
    const oldStorage = this.storage;
    this.storage = [];
    this.count = 0;
    // 獲取原來的數(shù)據(jù),放入新的數(shù)組中
    oldStorage.forEach((bucket) => {
      if (!bucket) return;
      for (let i = 0; i < bucket.length; i++) {
        const tuple = bucket[i];
        this.put(tuple[0], tuple[1]);
      }
    });
  }

1 、【數(shù)據(jù)結(jié)構(gòu)與算法——TypeScript】數(shù)組、棧、隊(duì)列、鏈表

2 、【數(shù)據(jù)結(jié)構(gòu)與算法——TypeScript】算法的復(fù)雜度分析、 數(shù)組和鏈表的對(duì)比

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法——TypeScript】哈希表的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！