哈希表是一種保存鍵值對（key-value）的數據結構

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

怎么做到的呢？

將 key 通過 Hash 函數的計算，就能定位數據在表中的位置，因為哈希表實際上是數組，所以可以通過索引值快速查詢到數據。

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

Redis 采用了**「鏈式哈?！?*來解決哈希沖突，在不擴容哈希表的前提下，將具有相同哈希值的數據串起來，形成鏈接起，以便這些數據在表中仍然可以被查詢到

1.哈希沖突

哈希表實際上是一個數組，數組里的每一個元素就是一個哈希桶

當一個鍵值對的鍵經過 Hash 函數計算后得到哈希值，再將(哈希值 % 哈希表大小)取模計算，得到的結果值就是該 key-value 對應的數組元素位置，也就是第幾個哈希桶

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

2.鏈式哈希

鏈式哈希是怎么實現的？

實現的方式就是每個哈希表節(jié)點都有一個 next 指針，用于指向下一個哈希表節(jié)點，因此多個哈希表節(jié)點可以用 next指針構成一個單項鏈表，被分配到同一個哈希桶上的多個節(jié)點可以用這個單項鏈表連接起來，這樣就解決了哈希沖突。

隨著鏈表長度的增加，在查詢這一位置上的數據的耗時就會增加，因為鏈表的查詢的時間復雜度是 O(n)。

3.rehash

Redis 定義一個 dict 結構體，這個結構體里定義了兩個哈希表（ht[2]）

之所以定義了 2 個哈希表，是因為進行 rehash 的時候，需要用上 2 個哈希表
在正常服務請求階段，插入的數據，都會寫入到「哈希表 1」，此時的「哈希表 2 」 并沒有被分配空間。

隨著數據逐步增多，觸發(fā)了 rehash 操作，這個過程分為三步：

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

第二步很有問題，如果「哈希表 1 」的數據量非常大，那么在遷移至「哈希表 2 」的時候，因為會涉及大量的數據拷貝，此時可能會對 Redis 造成阻塞，無法服務其他請求

4.漸進式 rehash

為了避免 rehash 在數據遷移過程中，因拷貝數據的耗時，影響 Redis 性能的情況

漸進式 rehash 步驟如下：

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

把一次性大量數據遷移工作的開銷，分攤到了多次處理請求的過程中，避免了一次性 rehash 的耗時操作

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

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

5.rehash 觸發(fā)條件

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

主要有兩個：

1.當負載因子大于等于 1 ，并且 Redis 沒有在執(zhí)行 bgsave 命令或者 bgrewiteaof 命令，也就是沒有執(zhí)行 RDB 快照或沒有進行 AOF 重寫的時候，就會進行 rehash 操作。
2.當負載因子大于等于 5 時，此時說明哈希沖突非常嚴重了，不管有沒有有在執(zhí)行 RDB 快照或 AOF 重寫，都會強制進行 rehash 操作

到此這篇關于Redis之常用數據結構哈希表的文章就介紹到這了,更多相關Redis哈希表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論