哈希表是一種保存鍵值對(duì)（key-value）的數(shù)據(jù)結(jié)構(gòu)

哈希表優(yōu)點(diǎn)在于，它能以 O(1) 的復(fù)雜度快速查詢數(shù)據(jù)。

怎么做到的呢？

將 key 通過(guò) Hash 函數(shù)的計(jì)算，就能定位數(shù)據(jù)在表中的位置，因?yàn)楣１韺?shí)際上是數(shù)組，所以可以通過(guò)索引值快速查詢到數(shù)據(jù)。

在哈希表大小固定的情況下，隨著數(shù)據(jù)不斷增多，那么哈希沖突的可能性也會(huì)越高。

Redis 采用了**「鏈?zhǔn)焦！?*來(lái)解決哈希沖突，在不擴(kuò)容哈希表的前提下，將具有相同哈希值的數(shù)據(jù)串起來(lái)，形成鏈接起，以便這些數(shù)據(jù)在表中仍然可以被查詢到

1.哈希沖突

哈希表實(shí)際上是一個(gè)數(shù)組，數(shù)組里的每一個(gè)元素就是一個(gè)哈希桶

當(dāng)一個(gè)鍵值對(duì)的鍵經(jīng)過(guò) Hash 函數(shù)計(jì)算后得到哈希值，再將(哈希值 % 哈希表大小)取模計(jì)算，得到的結(jié)果值就是該 key-value 對(duì)應(yīng)的數(shù)組元素位置，也就是第幾個(gè)哈希桶

當(dāng)有兩個(gè)以上數(shù)量的 kay 被分配到了哈希表中同一個(gè)哈希桶上時(shí)，此時(shí)稱這些 key 發(fā)生了沖突

2.鏈?zhǔn)焦?/h2>

鏈?zhǔn)焦Ｊ窃趺磳?shí)現(xiàn)的？

實(shí)現(xiàn)的方式就是每個(gè)哈希表節(jié)點(diǎn)都有一個(gè) next 指針，用于指向下一個(gè)哈希表節(jié)點(diǎn)，因此多個(gè)哈希表節(jié)點(diǎn)可以用 next指針構(gòu)成一個(gè)單項(xiàng)鏈表，被分配到同一個(gè)哈希桶上的多個(gè)節(jié)點(diǎn)可以用這個(gè)單項(xiàng)鏈表連接起來(lái)，這樣就解決了哈希沖突。

隨著鏈表長(zhǎng)度的增加，在查詢這一位置上的數(shù)據(jù)的耗時(shí)就會(huì)增加，因?yàn)殒湵淼牟樵兊臅r(shí)間復(fù)雜度是 O(n)。

3.rehash

Redis 定義一個(gè) dict 結(jié)構(gòu)體，這個(gè)結(jié)構(gòu)體里定義了兩個(gè)哈希表（ht[2]）

之所以定義了 2 個(gè)哈希表，是因?yàn)檫M(jìn)行 rehash 的時(shí)候，需要用上 2 個(gè)哈希表
在正常服務(wù)請(qǐng)求階段，插入的數(shù)據(jù)，都會(huì)寫(xiě)入到「哈希表 1」，此時(shí)的「哈希表 2 」 并沒(méi)有被分配空間。

隨著數(shù)據(jù)逐步增多，觸發(fā)了 rehash 操作，這個(gè)過(guò)程分為三步：

1.給「哈希表 2」 分配空間，一般會(huì)比「哈希表 1」 大 2 倍；
2.將「哈希表 1 」的數(shù)據(jù)遷移到「哈希表 2」 中；
3.遷移完成后，「哈希表 1 」的空間會(huì)被釋放，并把「哈希表 2」 設(shè)置為「哈希表 1」，然后在「哈希表 2」 新創(chuàng)建一個(gè)空白的哈希表，為下次 rehash 做準(zhǔn)備。

第二步很有問(wèn)題，如果「哈希表 1 」的數(shù)據(jù)量非常大，那么在遷移至「哈希表 2 」的時(shí)候，因?yàn)闀?huì)涉及大量的數(shù)據(jù)拷貝，此時(shí)可能會(huì)對(duì) Redis 造成阻塞，無(wú)法服務(wù)其他請(qǐng)求

4.漸進(jìn)式 rehash

為了避免 rehash 在數(shù)據(jù)遷移過(guò)程中，因拷貝數(shù)據(jù)的耗時(shí)，影響 Redis 性能的情況

漸進(jìn)式 rehash 步驟如下：

1.給「哈希表 2」 分配空間；
2.在 rehash 進(jìn)行期間，每次哈希表元素進(jìn)行新增、刪除、查找或者更新操作時(shí)，Redis 除了會(huì)執(zhí)行對(duì)應(yīng)的操作之外，還會(huì)順序?qū)ⅰ腹１?1 」中索引位置上的所有 key-value 遷移到「哈希表 2」 上；
3.隨著處理客戶端發(fā)起的哈希表操作請(qǐng)求數(shù)量越多，最終在某個(gè)時(shí)間點(diǎn)會(huì)把「哈希表 1 」的所有 key-value 遷移到「哈希表 2」，從而完成 rehash 操作。

把一次性大量數(shù)據(jù)遷移工作的開(kāi)銷(xiāo)，分?jǐn)偟搅硕啻翁幚碚?qǐng)求的過(guò)程中，避免了一次性 rehash 的耗時(shí)操作

1.查找一個(gè) key 的值的話，先會(huì)在「哈希表 1」 里面進(jìn)行查找，如果沒(méi)找到，就會(huì)繼續(xù)到哈希表 2 里面進(jìn)行找到。

2.新增一個(gè) key-value 時(shí)，會(huì)被保存到「哈希表 2 」里面，而「哈希表 1」 則不再進(jìn)行任何添加操作，這樣保證了「哈希表 1 」的 key-value 數(shù)量只會(huì)減少，隨著 rehash 操作的完成，最終「哈希表 1 」就會(huì)變成空表

5.rehash 觸發(fā)條件

觸發(fā)條件跟**負(fù)載因子（load factor）**有關(guān)系。

主要有兩個(gè)：

1.當(dāng)負(fù)載因子大于等于 1 ，并且 Redis 沒(méi)有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒(méi)有執(zhí)行 RDB 快照或沒(méi)有進(jìn)行 AOF 重寫(xiě)的時(shí)候，就會(huì)進(jìn)行 rehash 操作。
2.當(dāng)負(fù)載因子大于等于 5 時(shí)，此時(shí)說(shuō)明哈希沖突非常嚴(yán)重了，不管有沒(méi)有有在執(zhí)行 RDB 快照或 AOF 重寫(xiě)，都會(huì)強(qiáng)制進(jìn)行 rehash 操作

到此這篇關(guān)于Redis之常用數(shù)據(jù)結(jié)構(gòu)哈希表的文章就介紹到這了,更多相關(guān)Redis哈希表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論