Redis常用數(shù)據(jù)結構哈希表是什么

這篇文章主要介紹“Redis常用數(shù)據(jù)結構哈希表是什么”，在日常操作中，相信很多人在Redis常用數(shù)據(jù)結構哈希表是什么問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Redis常用數(shù)據(jù)結構哈希表是什么”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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

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

怎么做到的呢？

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

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

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

1.哈希沖突

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

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

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

2.鏈式哈希

鏈式哈希是怎么實現(xiàn)的？

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

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

3.rehash

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

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

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

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

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

4.漸進式 rehash

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

漸進式 rehash 步驟如下：

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

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

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

2.新增一個 key-value 時，會被保存到「哈希表 2 」里面，而「哈希表 1」 則不再進行任何添加操作，這樣保證了「哈希表 1 」的 key-value 數(shù)量只會減少，隨著 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常用數(shù)據(jù)結構哈希表是什么”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關知識，請繼續(xù)關注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>