Redis 的字典底層使用哈希表實現，說到哈希表大家應該能聯想到 HashMap 或者是 Hashtable，也應該能聯想到 key、value 的存儲形式，以及哈希表擴容，哈希算法等知識點。那么 Redis 字典是否也是通過這種形式實現的呢？帶著這些疑問下面我們就來了解一下 Redis 中的哈希表。

一、 哈希表結構

• table：用于存儲鍵值對
• size：表示哈希表的數組大小
• used：表示哈希表中已經存儲的鍵值對的個數
• sizemask：大小永遠為 size - 1，該屬性用于計算哈希值

二、 字典結構

上面我們說過字典是基于哈希表實現的，通過上圖我們可以看出字典包含了 2 個哈希表，還有一些其他屬性，比如 rehashindex，type 等。

為什么字典使用 2 個哈希表作為底層實現呢？原因是與 rehash 相關，與 rehash 相關的還有 rehashindex 屬性，下面我們會具體看到字典 rehash 的過程。

三、哈希算法

當我們把一個新的鍵值對添加到字典里時，會先根據鍵的哈希值計算其對應的索引值，然后根據索引值，將新的鍵值對放到哈希表數組指定的索引上面。

如果當 2 個或 2 個以上的鍵值對被分配同一個索引上面時，就發生了哈希沖突。我們聯想下 HashMap 中時如何解決哈希沖突的呢？HassMap 會通過鏈地址法將新的鍵值對通過鏈表的形式追加在上一個鍵值對后面。Redis 中的字典也是通過鏈地址法解決哈希沖突的，不過有一點不同的是 Redis 會將新添加的鍵值對放在鏈表的頭節點位置上。

四、rehash

4.1 負載因子

我們再來想一下 HashMap 中的 rehash，HashMap 中有一個 threshold 字段，這個字段在作為擴容閾值時默認情況下為 0.75 * capacity，意思是當哈希表中鍵值對的數量達到哈希表容量的 0.75 倍時就需要對哈希表進行擴容。

Redis 哈希表的負載因子通過下面的公式計算：

# 負載因子 = 哈希表已保存節點數量 / 哈希表大小load_factor = ht[0].used / ht[0].size

4.2 rehash 條件

Redis 哈希表不僅提供了擴容還提供了收縮機制，擴容與收縮都是通過 rehash 完成的。與 HashMap 一樣，Redis 中的哈希表想要執行 rehash 擴容操作也是需要一定條件的，主要為以下 2 個：

• 服務器目前沒有執行 BGREWRITEAOF 或者 BGSAVE 命令，切哈希表的負載因子大于等于 1
• 服務器目前正在執行 BGSAVE 或者 BGREWRITEAOF 命令， 并且哈希表的負載因子大于等于 5

下面是收縮 rehash 的條件：

• 哈希表的負載因子小于 0.1 時， 程序自動開始對哈希表執行收縮操作

上面擴容時根據 BGREWRITEAOF 或者 BGSAVE 命令是否執行分了兩種情況，為什么要這么做呢？原因如下：

在執行 BGREWRITEAOF 或者 BGSAVE 命令 時，Redis 會為當前服務器進程創建一個子進程，所以在子進程存在期間，會提高執行擴容的負載因子，因為這樣可以避免在子進程存在期間進行哈希表的擴容操作，從而避免不必要的內存寫入操作，最大限度的節約內存，提高效率。

4.3 rehash 擴容過程

Redis 字典 rehash 過程比較有意思的是它通過 2 個哈希表實現，當沒有在 rehash 時：rehashidx 的值為 -1，且使用哈希表 0 存儲鍵值對，哈希表 1 什么也不存儲。

rehash 過程：

• 為字典的 ht[1] 哈希表分配空間，分配的大小如下
  • 擴容：ht[1] 的大小為第一個大于等于 ht[0].used * 2 的 2^n
  • 收縮：ht[1] 的大小為第一個大于等于 ht[0].used 的 2^n
• 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上，這個過程會重新計算鍵的哈希值和索引值， 然后將鍵值對放置到 ht[1] 哈希表的指定位置上
• 當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后 （ht[0] 變為空表）， 釋放 ht[0] ， 將 ht[1] 設置為 ht[0] ， 并在 ht[1] 新創建一個空白哈希表， 為下一次 rehash 做準備

下面是 rehash 前后的一個對比

上面只給出了最終的結果對比，其實在 rehash 的過程中，每當一個鍵值對被 rehash 到 ht[1]
上時，對應的 rehashidx 屬性就會加 1。

4.4 漸進式 rehash

上面我們提到 Redis 字典的 rehash 過程，其實 rehash 并不是一次性，集中式的完成的，而是分多次，漸進式完成的。原因是 Redis 的字典字典有可能存儲上百萬個鍵值對，如果一次性完成的話，那么 Redis 可能會在一段時間內停止服務，為了保證 Redis 的高性能，這么做肯定是不允許的。

4.5 擴展問題分析

上面我們已經知道 rehash 的過程，現在我們來思考一個問題，在 rehash 的過程中，如果我們對字典進行了增刪改查，那么會操作哪個哈希表呢？是舊的還是新的，下面我們就來分析下：

其實不管執行任何操作，都不會允許有鍵值有丟失或者不一致的情況，有了這個前提后再進行分析就比較簡單了。在新增鍵值對的時候肯定會添加到新的哈希表中去，因為添加到舊的哈希表的話，最終還是被 rehash 到新的哈希表，就沒有必要進行一次浪費的 rehash 了。

刪改查操作在保證一致性的前提下，一定會先操作舊的哈希表，如果在舊的哈希表中沒有操作成功，會繼續操作新的哈希表。我們想一下，如果刪改查先操作新的哈希表再操作舊的哈希表的話，那么在操作的過程中可能有一部分數據被 rehash 到新的哈希表中去，這些數據有可能因為重新哈希的原因而被忽略。

五、參考資料

《Redis 設計與實現》 黃健宏著

總結

以上是生活随笔為你收集整理的Redis 数据结构之哈希表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。