Dict 優(yōu)點在于，它能以 O(1) 的復雜度快速查詢數(shù)據。怎么做到的呢？將 key 通過 Hash 函數(shù)的計算，就能定位數(shù)據在表中的位置，因為哈希表實際上是數(shù)組，所以可以通過索引值快速查詢到數(shù)據。

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

解決哈希沖突的方式，有很多種。

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

接下來，詳細說說 Dict 的結構設計

Dict 的結構

Dict 由三部分組成，分別是：dict、dictht、dicEntry

dictht

dictht 的結構如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

• dictEntry **table，哈希表數(shù)組
• unsigned long size，哈希表大?。ㄈ≈禐?2n2^n2n）
• unsigned long sizemask，哈希表大小掩碼，用于計算索引值，總是等于 size−1size - 1size−1
• unsigned long used，該哈希表已有的節(jié)點數(shù)量

dicEntry

dicEntry 結構如下

void *key;/*鍵*/
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; /*值*/
    struct dictEntry *next;/*下一個 entry 的指針*/
} dictEntry;

• dicEntry 和 dictht 之間的組織方式如下圖所示

• 當我們向 Dict 添加鍵值對時，Redis 首先根據 key 計算出 hash值（h），然后利用 h & sizemask 來計算元素應該存儲到數(shù)組中的哪個索引位置。我們存儲 k1=v1，假設 k1 的哈希值 h =1，則 1&3 = 1，因此 k1=v1 要存儲到數(shù)組角標 1 位置。
• 如果計算出來的數(shù)組角標值相同，也就是說，出現(xiàn)了 *哈希沖突，redis 采用 ”鏈式哈希“ 的方式，將具有相同哈希值的數(shù)據串起來，形成鏈結構，這也就是為什么會有 struct dictEntry next 這個成員變量存在

?? 為什么是 h & sizemask ？ 在根據 hash 值（h）來計算應該把 entry 放在哪個數(shù)組下標位置時，你可能會好奇，為什么不是使用 h%size ，而是使用 h&sizemask，而他們?yōu)槭裁纯梢缘贸鲆粯拥慕Y果。
實際上，當散列表的大小為 2n2^n2n 時，h%sizemask 的結果與 h%size 是相同的（這里不做證明）。讓我們以 size 為 8 的散列表為例：

• size = 8，對應的 sizemask = 7 (111的二進制表示)
• h = 18 (10010的二進制表示)
• h%size = 18%8 = 2
• h&sizemask = 18&7 = 2

dict

在實際使用哈希表時，Redis 沒有使用 dictht ，而是定義一個 dict 結構體，如下

typedef struct dict {
    dictType *type; /* dict類型，內置不同的hash函數(shù) */
    void *privdata; /* 私有數(shù)據，在做特殊hash運算時用 */
    dictht ht[2] ;/* 個Dict包含兩個哈希表，其中一個是當前數(shù)據，另一個一般是空，rehash時使用 */
    long rehashidx; /* rehash的進度，-1表示未進行 */
    int16_t pauserehash; /* rehash是否暫停，1則暫停，0則繼續(xù) */
} dict;

• 在上面這個結構體中，我們發(fā)現(xiàn)，type 、privdata 是跟哈希運算有關系的，但是其他三個成員變量，又是用來做什么的呢？為什么又要定義兩個 dictht 呢？這跟我們下面要說的 rehash 操作有關系

Dict 的 rehash

前面我們提到，redis 使用鏈式哈希來解決 hash 沖突問題。但是，鏈式哈希也存在局限性，那就是隨著鏈表長度的增加，Hash 表在一個位置上查詢哈希項的耗時就會增加，從而增加了 Hash 表的整體查詢時間，這樣也會導致 Hash 表的性能下降。這時，redis 使用 rehash 來解決這個問題。

Redis 如何實現(xiàn) rehash

Redis 實現(xiàn) rehash 的基本思路是這樣的：

• 首先，Redis 準備了兩個哈希表，用于 rehash 時交替保存數(shù)據。

  • 前面我們提到，redis 在實際使用時，定義了一個 dict 結構體。這個結構體中有一個數(shù)組（*ht[2] *），包含了兩個 Hash 表（dictht ） *ht[0] *和 *ht[1] *。

• 其次，在正常服務請求階段，所有的鍵值對寫入哈希表 ht[0]。

• 接著，當進行 rehash 時，鍵值對被遷移到哈希表 ht[1]中。

• 最后，當遷移完成后，ht[0]的空間會被釋放，并把 ht[1] 的地址賦值給 ht[0]，ht[1] 的表大小設置為 0。這樣一來，又回到了正常服務請求的階段，ht[0] 接收和服務請求，ht[1] 作為下一次 rehash 時的遷移表。

什么時候進行 rehash

• 當我們往 Redis 中寫入新的鍵值對或是修改鍵值對時，Redis 都會判斷下是否需要進行 rehash。而 rehash 的觸發(fā)條件則是

  • 條件 1 ：ht[0] 承載的元素個數(shù)已經超過了 ht[0] 的大小，也即d->ht[0].used >= d->ht[0].size，同時 Hash 表可以進行擴容。
  • 條件 2 ：ht[0] 承載的元素個數(shù)，是 ht[0] 的大小的 dict_force_resize_ratio 倍，也即 d->ht[0].used/d->ht[0].size > dict_force_resize_ratio 其中，dict_force_resize_ratio 的默認值是 5。

rehash 的新 size 是多大?

如果是擴容，則新 size 為第一個大于等于 dict.ht[0].used+1 的2n2^n2n 如果是收縮，則新 size 為第一個大于等于 dict.ht[0].used 的 2n2^n2n（不得小于4）

漸進式 rehash

• Hash 表在執(zhí)行 rehash 時，由于 Hash 表空間擴大，原本映射到某一位置的鍵可能會被映射到一個新的位置上，因此，很多鍵就需要從原來的位置拷貝到新的位置。而在鍵拷貝時，由于 Redis 主線程無法執(zhí)行其他請求，所以鍵拷貝會阻塞主線程，這樣就會產生 rehash 開銷。為了降低 rehash 開銷，Redis 就提出了漸進式 rehash 的方法。

rehash 的步驟

• 給 ht[1] 分配空間；
• 在 rehash 進行期間，在rehash過程中，新增操作，則直接寫入 ht[1]，查詢、修改和刪除則會在dict.ht[0] 和 dict.ht[1] 依次查找并執(zhí)行。這樣可以確保 ht[0] 的數(shù)據只減不增。
• 隨著處理客戶端發(fā)起的哈希表操作請求數(shù)量越多，最終在某個時間點會把 ht[0] 的所有 key-value 遷移到 ht[1]，從而完成 rehash 操作。

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

以上就是淺析Redis底層數(shù)據結構Dict的詳細內容，更多關于Redis數(shù)據結構Dict的資料請關注腳本之家其它相關文章！