1、是什么

Redis Hash（散列表）是一種 field-value pairs（鍵值對）集合類型，類似于 Python 中的字典、Java 中的 HashMap。一個 field 對應(yīng)一個 value，你可以通過 field 在 O(1) 時間復(fù)雜度查 field 找關(guān)聯(lián)的 field，也可以通過 field 來更新或者刪除這個鍵值對。

Redis 的散列表 dict 由數(shù)組 + 鏈表構(gòu)成，數(shù)組的每個元素占用的槽位叫做哈希桶，當(dāng)出現(xiàn)散列沖突的時候就會在這個桶下掛一個鏈表，用“拉鏈法”解決散列沖突的問題。

簡單地說就是將一個 key 經(jīng)過散列計算均勻的映射到散列表上。

圖 2-18

2、修煉心法

Hash 數(shù)據(jù)類型底層存儲數(shù)據(jù)結(jié)構(gòu)實際上有兩種。

1. dict 結(jié)構(gòu)。
2. 在 7.0 版本之前使用 ziplist，之后被 listpack 代替。

通常情況下使用 dict 數(shù)據(jù)結(jié)構(gòu)存儲數(shù)據(jù)，每個 field-value pairs 構(gòu)成一個 dictEntry 節(jié)點來保存。

只有同時滿足以下兩個條件的時候，才會使用 listpack（7.0 版本之前使用 ziplist）數(shù)據(jù)結(jié)構(gòu)來代替 dict 存儲， 把 key-value 鍵值對按照 field 在前 value 在后，緊密相連的方式放到一次把每個鍵值對放到列表的表尾。

• 每個鍵值對中的 field 和 value 的字符串字節(jié)大小都小于hash-max-listpack-value 配置的值（默認(rèn) 64）。
• field-value pairs 鍵值對數(shù)量小于 hash-max-listpack-entries配置的值（默認(rèn) 512）。

每次向散列表寫數(shù)據(jù)的時候，都會調(diào)用 t_hash.c 中的hashTypeConvertListpack()函數(shù)來判斷是否需要轉(zhuǎn)換底層數(shù)據(jù)結(jié)構(gòu)。

當(dāng)插入和修改的數(shù)據(jù)不滿足以上兩個條件時，就把散列表底層存儲結(jié)構(gòu)轉(zhuǎn)換成 dict結(jié)構(gòu)。需要注意的是，不能由 dict 退化成 listpack。

雖然使用了 listpack 就無法實現(xiàn) O(1) 時間復(fù)雜度操作數(shù)據(jù)，但是使用 listpack 能大大減少內(nèi)存占用，而且數(shù)據(jù)量比較小，性能并不是有太大差異。

為了對上層屏蔽散列表底層使用了不同數(shù)據(jù)結(jié)構(gòu)存儲，所以抽象了一個 hashTypeIterator 迭代器來實現(xiàn)散列表的查詢。

Hashes 數(shù)據(jù)類型使用 listpack 作為存儲數(shù)據(jù)時的情況，如圖 2-19 所示。

圖 2-19

listpack 數(shù)據(jù)結(jié)構(gòu)在之前的已經(jīng)介紹過， 接下來帶你揭秘 dict 到底長啥樣。

Redis 數(shù)據(jù)庫就是一個全局散列表。正常情況下，我只會使用 ht_table[0]散列表，圖 2-20 是一個沒有進(jìn)行 rehash 狀態(tài)下的字典。

圖 2-20

dict 字典在源代碼 dict.h中使用 dict 結(jié)構(gòu)體表示。

struct dict {
    dictType *type;
  // 真正存儲數(shù)據(jù)的地方，分別存放兩個指針
    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx;

    int16_t pauserehash;
    signed char ht_size_exp[2];
};

• dictType *type，存放函數(shù)的結(jié)構(gòu)體，定義了一些函數(shù)指針，可以通過設(shè)置自定義函數(shù)，實現(xiàn) dict 的 key 和 value 存放任何類型的數(shù)據(jù)。
• 重點看 dictEntry **ht_table[2]，存放了兩個 dictEntry 的二級指針，指針分別指向了一個 dictEntry 指針的數(shù)組。
• ht_used[2]，記錄每個散列表使用了多少槽位（比如數(shù)組長度 32，使用了 12）。
• rehashidx，用于標(biāo)記是否正在執(zhí)行 rehash 操作，-1 表示沒有進(jìn)行 rehash。如果正在執(zhí)行 rehash，那么其值表示當(dāng)前 rehash 操作執(zhí)行的 ht_table[0] 散列表 dictEntry 數(shù)組的索引。
• pauserehash 表示 rehash 的狀態(tài)，大于 0 時表示 rehash 暫停了，小于 0 表示出錯了。

繼續(xù)看 dictEntry，數(shù)組中每個元素都是 dictEntry 類型，就是這玩意存放了鍵值對，表示字典的一個節(jié)點。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

• *key指針指向鍵值對中的鍵，實際上指向一個 SDS 實例。
• v是一個 union 聯(lián)合體，表示鍵值對中的值，同一時刻只有一個字段有值，用聯(lián)合體的目是節(jié)省內(nèi)存。

• *val 如果值是非數(shù)字類型，那就使用這個指針存儲。
• uint64_t u64，值是無符號整數(shù)的時候使用這個字段存儲。
• int64_t s64，值是有符號整數(shù)時，使用該字段存儲。
• double d，值是浮點數(shù)是，使用該字段存儲。

• *next指向下一個節(jié)點指針，當(dāng)散列表數(shù)據(jù)增加，可能會出現(xiàn)不同的 key 得到的哈希值相等，也就是說多個 key 對應(yīng)在一個哈希桶里面，這就是哈希沖突。Redis 使用拉鏈法，也就是用鏈表將數(shù)據(jù)串起來。

MySQL：“為啥 ht_table[2] 存放了兩個指向散列表的指針？用一個散列表不就夠了么?！?/p>

默認(rèn)使用 ht_table [0] 進(jìn)行讀寫數(shù)據(jù)，當(dāng)散列表的數(shù)據(jù)越來越多的時候，哈希沖突嚴(yán)重會出現(xiàn)哈希桶的鏈表比較長，導(dǎo)致查詢性能下降。

我為了唯快不破想了一個法子，當(dāng)散列表保存的鍵值對太多或者太少的時候，需要通過 rehash（重新散列）對散列表進(jìn)行擴容或者縮容。

擴容和縮容

1. 為了高性能，減少哈希沖突，我會創(chuàng)建一個大小等于 ht_used[0] * 2的散列表 ht_table[1]，也就是每次擴容時根據(jù)散列表 ht_table [0]已使用空間擴大一倍創(chuàng)建一個新散列表ht_table [1]。反之，如果是縮容操作，就根據(jù)ht_table [0]已使用空間縮小一倍創(chuàng)建一個新的散列表。
2. 重新計算鍵值對的哈希值，得到這個鍵值對在新散列表 ht_table [1]的桶位置，將鍵值對遷移到新的散列表上。
3. 所有鍵值對遷移完成后，修改指針，釋放空間。具體是把 ht_table[0]指針指向擴容后的散列表，回收原來小的散列表內(nèi)存空間，ht_table[1]指針指向NULL，為下次擴容或者縮容做準(zhǔn)備。

MySQL：“什么時候會觸發(fā)擴容？”

1. 當(dāng)前沒有執(zhí)行 BGSAVE或者 BGREWRITEAOF命令，同時負(fù)載因子大于等于 1。也就是當(dāng)前沒有 RDB 子進(jìn)程和 AOF 重寫子進(jìn)程在工作，畢竟這倆操作還是比較容易對性能造成影響的，就不擴容火上澆油了。
2. 正在執(zhí)行 BGSAVE或者 BGREWRITEAOF命令，負(fù)載因子大于等于 5。（這時候哈希沖突太嚴(yán)重了，再不觸發(fā)擴容，查詢效率太慢了）。

負(fù)載因子 = 散列表存儲 dictEntry 節(jié)點數(shù)量 / 散列表桶個數(shù)。完美情況下，每個哈希桶存儲一個 dictEntry 節(jié)點，這時候負(fù)載因子 = 1。

MySQL：“需要遷移數(shù)據(jù)量很大，rehash 操作豈不是會長時間阻塞主線程？”

為了防止阻塞主線程造成性能問題，我并不是一次性把全部的 key 遷移，而是分多次，將遷移操作分散到每次請求中，避免集中式 rehash 造成長時間阻塞，這個方式叫漸進(jìn)式 rehash。

在執(zhí)行漸進(jìn)式 rehash 期間，dict 會同時使用 ht_table[0] 和 ht_table[1]兩個散列表，rehash 具體步驟如下。

1. 將 rehashidx設(shè)置成 0，表示 rehash 開始執(zhí)行。
2. 在 rehash 期間，服務(wù)端每次處理客戶端對 dict 散列表執(zhí)行添加、查找、刪除或者更新操作時，除了執(zhí)行指定操作以外，還會檢查當(dāng)前 dict 是否處于 rehash 狀態(tài)，是的話就把散列表ht_table[0]上索引位置為 rehashidx 的桶的鏈表的所有鍵值對 rehash 到散列表 ht_table[1]上，這個哈希桶的數(shù)據(jù)遷移完成，就把 rehashidx 的值加 1，表示下一次要遷移的桶所在位置。
3. 當(dāng)所有的鍵值對遷移完成后，將 rehashidx設(shè)置成 -1，表示 rehash 操作已完成。

MySQL：“rehash 過程中，字典的刪除、查找、更新和添加操作，要從兩個 ht_table 都搞一遍么？”

刪除、修改和查找可能會在兩個散列表進(jìn)行，第一個散列表沒找到就到第二個散列表進(jìn)行查找。但是增加操作只會在新的散列表上進(jìn)行。

MySQL：“如果請求比較少，豈不是會很長時間都要使用兩個散列表?！?/p>

好問題，在 Redis Server 初始化時，會注冊一個時間事件，定時執(zhí)行 serverCron 函數(shù)，其中包含 rehash 操作用于輔助遷移，避免這個問題。

serverCron 函數(shù)除了做 rehash 以外，主要處理如下工作。

• 過期 key 刪除。
• 監(jiān)控服務(wù)運行狀態(tài)。
• 更新統(tǒng)計數(shù)據(jù)。
• 漸進(jìn)式 rehash。
• 觸發(fā) BGSAVE / AOF rewrite 以及停止子進(jìn)程。
• 處理客戶端超時。
• ......

是不是很貼心，既能保證性能，又能避免內(nèi)存浪費。好了，今天散列表底層數(shù)據(jù)結(jié)構(gòu)實現(xiàn)原理就到這里。后面我將給大家分享如何使用 Hash 實現(xiàn)購物車功能。