0.前言

上個(gè)篇章回顧，我們上個(gè)章節(jié)，講了Redis中的快表（QuickList），它是一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一系列的連續(xù)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以是一個(gè)整數(shù)或一個(gè)字節(jié)數(shù)組?？毂硎荝edis中的底層數(shù)據(jù)結(jié)構(gòu)之一，常用于存儲(chǔ)有序集合（Sorted Set）等數(shù)據(jù)類型的底層實(shí)現(xiàn)。

那么本章講解Redis中的底層數(shù)據(jù)結(jié)構(gòu)中的字典（Dictionary）也稱為哈希表（Hash Table）。字典（Dictionary）是一種高效的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)鍵值對(duì)，常用于實(shí)現(xiàn)哈希表。用于快速存取和查找數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，它的內(nèi)部實(shí)現(xiàn)是一個(gè)數(shù)組加上鏈表或者紅黑樹(shù)。在 Redis 中，字典被廣泛用于實(shí)現(xiàn)哈希表鍵值對(duì)的存儲(chǔ)和查找，例如 Redis 中的 Hash 類型就是基于字典實(shí)現(xiàn)的在本文中，我們將深入了解Redis中的字典/哈希表，包括字典的結(jié)構(gòu)和操作等。

Redis中的字典（Dictionary）是一種高效的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)鍵值對(duì)，常用于實(shí)現(xiàn)哈希表（Hash Table）。在本文中，我們將深入了解Redis中的字典/哈希表，包括字典的結(jié)構(gòu)和操作等。

圖1 哈希表（Hash Table）

1. 字典的結(jié)構(gòu)

示意圖中，RedisDictionary 表示 Redis 字典，它包含了多個(gè) HashSlot 對(duì)象，每個(gè) HashSlot
對(duì)象代表一個(gè)哈希槽，它包含了多個(gè) Entry 對(duì)象，每個(gè) Entry 對(duì)象代表一個(gè)鍵值對(duì)。

Redis中的字典（Dictionary）是由多個(gè)哈希表（Hash Table 如圖1）組成的，每個(gè)哈希表都包含了多個(gè)哈希槽（Hash Bucket）。哈希表的結(jié)構(gòu)如下圖所示：

+---------+---------+---------+-------+
|  bucket |  bucket |  bucket |  ...  |
+---------+---------+---------+-------+
|  ...    |  ...    |  ...    |  ...  |
+---------+---------+---------+-------+

其中，bucket是哈希桶，包含了多個(gè)鍵值對(duì)。每個(gè)鍵值對(duì)包含了一個(gè)鍵和一個(gè)值，鍵和值可以是任意數(shù)據(jù)類型，但鍵必須是唯一的。哈希表的大小是固定的，當(dāng)哈希桶中的鍵值對(duì)數(shù)量超過(guò)一定閾值時(shí)，需要對(duì)哈希表進(jìn)行擴(kuò)容操作，以保持哈希表的高效性。
Redis 6 字典的源碼實(shí)現(xiàn)主要在 dict.h 和 dict.c 文件中。dict.h 文件定義了字典的結(jié)構(gòu)體和函數(shù)接口，而 dict.c 文件則具體實(shí)現(xiàn)了這些函數(shù)接口。

2. 源碼解析

2.1. 字典的結(jié)構(gòu)體

Redis 6 字典的結(jié)構(gòu)體定義與 Redis 5 相同，但是新增了一個(gè) dictEntryKey 結(jié)構(gòu)體，用于存儲(chǔ)鍵的信息。Redis 6 字典的結(jié)構(gòu)體定義如下：

typedef struct dictEntryKey {
    void *key;  // 指向鍵的指針
    uint64_t hash;  // 哈希值
} dictEntryKey;

typedef struct dictEntry {
    dictEntryKey key;  // 鍵的信息
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

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

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

1. dictEntryKey 結(jié)構(gòu)體

   ``dictEntryKey 結(jié)構(gòu)體用于存儲(chǔ)鍵的信息，包括指向鍵的指針和鍵的哈希值。其中，key 成員變量是指向鍵的指針，hash` 成員變量是鍵的哈希值。

2. dictEntry 結(jié)構(gòu)體

   ``dictEntry 結(jié)構(gòu)體用于表示字典中的一個(gè)節(jié)點(diǎn)，包含鍵值對(duì)的信息和指向下一個(gè)節(jié)點(diǎn)的指針。其中，key成員變量是dictEntryKey 結(jié)構(gòu)體類型，表示鍵的信息；v成員變量是一個(gè)union，可以存儲(chǔ)不同類型的值，包括指向值的指針、64 位整數(shù)、64 位有符號(hào)整數(shù)和雙精度浮點(diǎn)數(shù)等；next` 成員變量是指向下一個(gè)節(jié)點(diǎn)的指針。

3. dictType 結(jié)構(gòu)體

   ``dictType` 結(jié)構(gòu)體用于定義字典的類型，包括哈希函數(shù)、鍵復(fù)制函數(shù)、值復(fù)制函數(shù)、鍵比較函數(shù)、鍵銷毀函數(shù)和值銷毀函數(shù)。

   • hashFunction 成員變量是哈希函數(shù)，用于計(jì)算鍵的哈希值；
   • keyDup 成員變量是鍵復(fù)制函數(shù)，用于復(fù)制鍵的值；
   • valDup 成員變量是值復(fù)制函數(shù)，用于復(fù)制值的值；
   • keyCompare 成員變量是鍵比較函數(shù)，用于比較兩個(gè)鍵是否相等；
   • keyDestructor 成員變量是鍵銷毀函數(shù)，用于銷毀鍵的值；
   • valDestructor 成員變量是值銷毀函數(shù)，用于銷毀值的值。

4. dictht 結(jié)構(gòu)體

   ``dictht 結(jié)構(gòu)體用于表示哈希表，包括哈希表的數(shù)組、大小、掩碼和已使用的節(jié)點(diǎn)數(shù)。其中，table 成員變量是指向哈希表數(shù)組的指針，size 成員變量是哈希表數(shù)組的大小，sizemask成員變量是掩碼（等于size - 1），用于計(jì)算哈希值對(duì)應(yīng)的數(shù)組下標(biāo)，used` 成員變量是哈希表已使用的節(jié)點(diǎn)數(shù)。

5. dict 結(jié)構(gòu)體

   ``dict 結(jié)構(gòu)體用于表示字典，包括字典的類型、私有數(shù)據(jù)、哈希表、重哈希索引和正在運(yùn)行的迭代器數(shù)量。其中，type 成員變量是指向字典類型的指針，privdata 成員變量是指向私有數(shù)據(jù)的指針，ht成員變量是一個(gè)長(zhǎng)度為 2 的dictht 數(shù)組，用于實(shí)現(xiàn)哈希表的漸進(jìn)式重哈希操作；rehashidx成員變量表示正在進(jìn)行重哈希的哈希表索引，如果rehashidx 等于 -1，表示沒(méi)有進(jìn)行重哈希操作；iterators` 成員變量表示正在運(yùn)行的迭代器數(shù)量，用于控制在迭代器運(yùn)行期間進(jìn)行重哈希操作。

2.2. 字典的函數(shù)接口

Redis 6 字典提供了與 Redis 5 相同的函數(shù)接口，但是在實(shí)現(xiàn)細(xì)節(jié)上有一些變化。

dictAdd

Redis 6 相對(duì)于 Redis 5 做了一些優(yōu)化，其中 dictAdd 函數(shù)的實(shí)現(xiàn)發(fā)生了變化。在 Redis 6 中，當(dāng)向字典中添加一個(gè)新的鍵值對(duì)時(shí)，會(huì)先嘗試將該鍵的哈希值計(jì)算出來(lái)，并查找哈希表中是否已經(jīng)存在該哈希值。如果該哈希值還沒(méi)有節(jié)點(diǎn)使用，那么就可以直接將新的鍵值對(duì)插入到哈希表中。如果該哈希值已經(jīng)存在節(jié)點(diǎn)，那么就需要使用鍵比較函數(shù)來(lái)比較新鍵和舊鍵是否相等。如果新鍵和舊鍵相等，那么就需要用新值替換舊值；否則就需要將新鍵值對(duì)插入到哈希槽的鏈表末尾。

在實(shí)現(xiàn)過(guò)程中，Redis 6 使用了一個(gè) dictEntryKey 結(jié)構(gòu)體來(lái)存儲(chǔ)鍵的信息，包括指向鍵的指針和鍵的哈希值。這樣可以避免重復(fù)計(jì)算鍵的哈希值，提高了添加操作的效率。

dictFind

在 Redis 6 中，dictFind 函數(shù)的實(shí)現(xiàn)與 Redis 5 相同，但是在查找過(guò)程中，Redis 6 使用了 dictEntryKey 結(jié)構(gòu)體中的哈希值來(lái)進(jìn)行比較，以提高查找效率。

dictResize

Redis 6 中的 dictResize 函數(shù)與 Redis 5 相同，但是在實(shí)現(xiàn)過(guò)程中，Redis 6 增加了一些控制邏輯，以避免在短時(shí)間內(nèi)多次調(diào)整哈希表的大小，從而提高了性能。

Redis 6 字典相對(duì)于 Redis 5 在實(shí)現(xiàn)細(xì)節(jié)上進(jìn)行了一些優(yōu)化，主要是在添加和查找操作上進(jìn)行了改進(jìn)，提高了字典的性能和效率。其中，添加操作使用了一個(gè) dictEntryKey 結(jié)構(gòu)體來(lái)存儲(chǔ)鍵的信息，以避免重復(fù)計(jì)算鍵的哈希值；查找操作使用了dictEntryKey 結(jié)構(gòu)體中的哈希值來(lái)進(jìn)行比較，以提高查找效率。此外，Redis 6 還增加了一些控制邏輯，以避免在短時(shí)間內(nèi)多次調(diào)整哈希表的大小，從而提高了性能。

如果有想繼續(xù)鏈接Redis6源碼的同學(xué)，可以參考github地址 https://github.com/redis/redis/tree/6.0，可以從這個(gè) Github 倉(cāng)庫(kù)中獲取整個(gè) Redis 6 的代碼。在該倉(cāng)庫(kù)中，可以找到所有與 Redis 相關(guān)的代碼，包括服務(wù)器端、客戶端、測(cè)試代碼等等。如果需要了解 Redis 6 的源碼實(shí)現(xiàn)，可以通過(guò)該倉(cāng)庫(kù)中的代碼來(lái)深入了解 Redis 6 的實(shí)現(xiàn)細(xì)節(jié)。同時(shí)，Redis 官方也提供了詳細(xì)的文檔和說(shuō)明，可以幫助開(kāi)發(fā)者更好地理解 Redis 6 的設(shè)計(jì)思路和代碼實(shí)現(xiàn)。

3. 字典/哈希表的優(yōu)缺點(diǎn)

3.1 優(yōu)點(diǎn)

3.1.1. 快速的查找時(shí)間

提供了常數(shù)時(shí)間復(fù)雜度O(1)的鍵值對(duì)查找，這意味著查找與字典大小無(wú)關(guān)，即使對(duì)于非常大的字典，查找時(shí)間也非常快。

3.1.2. 動(dòng)態(tài)調(diào)整大小

字典/哈希表支持動(dòng)態(tài)調(diào)整大小以適應(yīng)數(shù)據(jù)的增長(zhǎng)或減少。當(dāng)某個(gè)哈希桶中的鍵值對(duì)數(shù)量超過(guò)一定閾值時(shí)，Redis會(huì)自動(dòng)調(diào)整哈希桶的大小，以確保字典的高效性。這意味著Redis可以處理大量的數(shù)據(jù)而不會(huì)導(dǎo)致顯著的性能損失。

3.1.3. 靈活的數(shù)據(jù)類型

可以存儲(chǔ)任意數(shù)據(jù)類型的鍵和值，這使它非常靈活。這意味著它可以用于各種應(yīng)用場(chǎng)景，從簡(jiǎn)單的鍵值存儲(chǔ)到更復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。

3.2 缺點(diǎn)

• 哈希表的空間利用率可能較低，當(dāng)哈希桶中的鍵值對(duì)數(shù)量較少時(shí)，會(huì)浪費(fèi)一定的空間。
• 哈希表的擴(kuò)容和縮容可能會(huì)造成性能損失，因?yàn)樾枰匦掠?jì)算哈希值、重新分配內(nèi)存等操作。
• 哈希表中的鍵的順序是無(wú)序的，不適合存儲(chǔ)需要按照鍵的順序進(jìn)行訪問(wèn)的數(shù)據(jù)。

4.總結(jié)

字典/哈希表適合存儲(chǔ)大量的鍵值對(duì)，并需要快速地查找鍵對(duì)應(yīng)的值的場(chǎng)景。在實(shí)際應(yīng)用中，需要根據(jù)具體的業(yè)務(wù)場(chǎng)景選擇合適的底層數(shù)據(jù)結(jié)構(gòu)。例如，如果需要按照鍵的順序進(jìn)行訪問(wèn)，可以使用有序集合（Sorted Set）等其他數(shù)據(jù)結(jié)構(gòu)。

5. Redis從入門到精通系列文章

《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)快表QuickList詳解》
《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單動(dòng)態(tài)字符串(SDS)詳解》
《Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)壓縮列表(ZipList)詳解》
《Redis從入門到精通【進(jìn)階篇】之?dāng)?shù)據(jù)類型Stream詳解和使用示例》
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-494039.html

到了這里，關(guān)于Redis從入門到精通【高階篇】之底層數(shù)據(jù)結(jié)構(gòu)字典(Dictionary)詳解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！