dict.c/dict.h

一比规、 dict的定義

??字典，是一種用于實(shí)現(xiàn)鍵值對(duì)（key-value pair）保存的抽象數(shù)據(jù)結(jié)構(gòu)拦英，通過(guò)字典蜒什，可以在單個(gè)鍵（key）與單個(gè)值（value）之間進(jìn)行關(guān)聯(lián)（或者說(shuō)是將鍵映射成值），而這些關(guān)聯(lián)的鍵與值即為鍵值對(duì)疤估。

??在字典中灾常，每一個(gè)鍵都是獨(dú)一無(wú)二的霎冯，所以程序可以在字典中通過(guò)鍵來(lái)對(duì)值，甚至是鍵值對(duì)進(jìn)行操作钞瀑。

??在一些高級(jí)編程語(yǔ)言中沈撞，字典經(jīng)常作為一種內(nèi)置的數(shù)據(jù)結(jié)構(gòu)出現(xiàn)，但是可惜的是雕什，C語(yǔ)言并不在此列缠俺，所以 Redis 自己實(shí)現(xiàn)了字典這種數(shù)據(jù)結(jié)構(gòu)。

??在 Redis 中贷岸，字典使用哈希表作為底層實(shí)現(xiàn)壹士，而一個(gè)哈希表可以有多個(gè)哈希結(jié)點(diǎn)，每一個(gè)哈希節(jié)點(diǎn)保存了一組鍵值對(duì)偿警。下圖是一個(gè)典型的字典：

字典示意圖

??下面依次是哈希節(jié)點(diǎn)躏救、哈希表、字典螟蒸、迭代器的實(shí)現(xiàn)盒使。

哈希節(jié)點(diǎn)（dictEntry ）

哈希節(jié)點(diǎn)，在 dict.h/dictEntry 中進(jìn)行了定義：

// 哈希表節(jié)點(diǎn)
typedef struct dictEntry {
    
    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下一個(gè)哈希節(jié)點(diǎn)七嫌，構(gòu)成單向鏈表忠怖，用以解決鍵沖突（鏈地址法）
    struct dictEntry *next;

} dictEntry;

• key 屬性用來(lái)保存鍵值對(duì)中的鍵，聯(lián)合體（union）v 屬性用來(lái)保存鍵值對(duì)中的值抄瑟。由于 v 屬性使用 union 關(guān)鍵字進(jìn)行定義凡泣，所以鍵值對(duì)中的值可以是一個(gè)指針，一個(gè) uint64_t 類型的整數(shù)皮假，或者是一個(gè) int64_t 類型的整數(shù)鞋拟。

• * next 屬性是指向下一個(gè)哈希節(jié)點(diǎn)的指針，用來(lái)將多個(gè)哈希值相同的鍵值對(duì)連接起來(lái)惹资，構(gòu)成一個(gè)單向鏈表贺纲，用以解決鍵沖突（collision）即通過(guò)鏈地址法解決鍵沖突。

哈希表（dictht ）

哈希表褪测，在 dict.h/dictht 中進(jìn)行了定義：

//哈希表
typedef struct dictht {
    
    // 哈希字節(jié)數(shù)組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩碼猴誊，總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節(jié)點(diǎn)的數(shù)量
    unsigned long used;

} dictht;

• table 屬性是一個(gè)數(shù)組，數(shù)組中的每一個(gè)元素都是一個(gè)指向 dict.h/dictEntry 結(jié)構(gòu)的指針侮措。

• size 屬性記錄了哈希表的大小懈叹，也即是 table 數(shù)組的大小。

• used 屬性記錄了哈希表已有結(jié)點(diǎn)分扎，即鍵值對(duì)的數(shù)量澄成。

• sizemask 屬性的值總是等于 size-1 ，是用來(lái)和哈希值一起決定一個(gè)鍵應(yīng)該被放在 table 數(shù)組的哪一個(gè)索引上面的。

字典（dict）

字典墨状，在 dict.h/dict 中進(jìn)行了定義：

//字典
typedef struct dict {

    // 類型特定函數(shù)
    dictType *type;

    // 私有數(shù)據(jù)
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當(dāng) rehash 不在進(jìn)行時(shí)卫漫，值為 -1
    int rehashidx;

    // 目前正在運(yùn)行的迭代器的數(shù)量
    int iterators;
    
} dict;

• ht屬性：每一個(gè)字典（dict）都有兩個(gè)哈希表（dictht），用來(lái)實(shí)現(xiàn) 漸進(jìn)式 rehash 肾砂，保存在 ht 數(shù)組當(dāng)中列赎。并且，在字典當(dāng)中镐确，一般只會(huì)使用 ht[0] 哈希表粥谬，只有在對(duì) ht[0] 哈希表進(jìn)行 rehash 時(shí)才會(huì)用到 ht[1]。

• rehashidx 屬性用來(lái)記錄 rehash 進(jìn)度辫塌，當(dāng) rehash 沒(méi)有在進(jìn)行的時(shí)候漏策，rehashidx = -1 。

• iterators 屬性用來(lái)記錄目前正在運(yùn)行的迭代器的數(shù)量臼氨。

• type 屬性和 privdata 屬性是用來(lái)針對(duì)不同類型的鍵值對(duì)掺喻，創(chuàng)建多態(tài)字典的。

  • type 屬性是一個(gè)指向 dictType 結(jié)構(gòu)的指針储矩，每個(gè) dictType 結(jié)構(gòu)保存了一組用于操縱特定類型鍵值對(duì)的函數(shù)感耙，而 Redis 會(huì)為不同用途的字典設(shè)置不同的類型特定函數(shù)。
  • privdata 屬性保存了要傳給那些類型特定函數(shù)的可選參數(shù)持隧。

其中即硼，字典類型特定函數(shù)在 dict.h/dictType 中進(jìn)行了定義：

// 字典類型特定函數(shù)
typedef struct dictType {

    // 計(jì)算哈希值的函數(shù)
    unsigned int (*hashFunction)(const void *key);

    // 復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *privdata, const void *key);

    // 復(fù)制值的函數(shù)
    void *(*valDup)(void *privdata, const void *obj);

    // 對(duì)比鍵的函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 銷毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);
    
    // 銷毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);

} dictType;


/* 外部變量 Hash table types */
extern dictType dictTypeHeapStringCopyKey;
extern dictType dictTypeHeapStrings;
extern dictType dictTypeHeapStringCopyKeyValue;

字典迭代器（dictIterator ）

字典迭代器，在 dict.h/dictIterator 中進(jìn)行了定義：

// 字典迭代器
typedef struct dictIterator {
        
    // 被迭代的字典
    dict *d;

    // table ：正在被迭代的哈希表屡拨，值可以是 0 或 1只酥。
    // index ：迭代器當(dāng)前所指向的哈希表的索引位置
    // safe ：標(biāo)識(shí)這個(gè)迭代器是否安全
    int table, index, safe;

    // entry ：當(dāng)前迭代到的哈希節(jié)點(diǎn)
    // nextEntry ：當(dāng)前迭代到的哈希節(jié)點(diǎn)的下一個(gè)哈希節(jié)點(diǎn)
    dictEntry *entry, *nextEntry;

    long long fingerprint; /* unsafe iterator fingerprint for misuse detection */
    
} dictIterator;

• d 屬性是一個(gè)指向 dict 結(jié)構(gòu)的指針，保存了當(dāng)前迭代器正在處理的字典呀狼。

• table 屬性用來(lái)標(biāo)識(shí)當(dāng)前正在被迭代的哈希表裂允，即 dict 結(jié)構(gòu)中的 dictht 數(shù)組 ht 的下標(biāo)，值可以為 0 或 1 哥艇。

• index 屬性用來(lái)標(biāo)識(shí)迭代器當(dāng)前所指向的哈希表的索引位置绝编。

• safe 屬性用來(lái)標(biāo)識(shí)這個(gè)迭代器是否是安全的迭代器，這對(duì)該迭代器后續(xù)能調(diào)用的 API 有影響貌踏。其中十饥，safe = 1 表示該迭代器可以在迭代時(shí)進(jìn)行增刪改等操作，對(duì)字典進(jìn)行修改祖乳，即調(diào)用 dictDelete逗堵、dictFind 等函數(shù)，如若不然凡资，則只能使用 dictNext 遍歷函數(shù)砸捏，而不能對(duì)字典進(jìn)行修改。

• entry 屬性是一個(gè)指向 dictEntry 結(jié)構(gòu)的指針隙赁，指向當(dāng)前迭代到的哈希節(jié)點(diǎn)垦藏。

• nextEntry 屬性是一個(gè)指向 dictEntry 結(jié)構(gòu)的指針，指向當(dāng)前迭代到的哈希節(jié)點(diǎn)的下一個(gè)哈希節(jié)點(diǎn)伞访。這個(gè)屬性存在的原因是掂骏，在安全迭代器運(yùn)行時(shí)，entry 指針?biāo)赶虻墓?jié)點(diǎn)可能會(huì)被修改厚掷，所以需要一個(gè)指針來(lái)保存下一節(jié)點(diǎn)的位置弟灼，來(lái)防止指針丟失。

• fingerprint 屬性是字典的指紋冒黑，用于誤用檢測(cè)田绑，即在不安全的迭代器對(duì)字典進(jìn)行操作后，與操作前的指紋值進(jìn)行對(duì)比抡爹，若不同掩驱，則說(shuō)明在迭代過(guò)程中有對(duì)字典進(jìn)行增刪操作，而這些操作在不安全的迭代器中是不被允許的冬竟。

宏定義常量

在 dict.h 中欧穴，對(duì)一些對(duì)常量的定義：

/*
 * 字典的操作狀態(tài)
 */
// 操作成功
#define DICT_OK 0
// 操作失敗（或出錯(cuò)）
#define DICT_ERR 1


/*
 * 哈希表的初始大小
 */
#define DICT_HT_INITIAL_SIZE     4

即：

• DICT_OK：字典操作狀態(tài)泵殴，表示操作成功

• DICT_ERR：字典操作狀態(tài)涮帘，表示操作失敗或出錯(cuò)

• DICT_HT_INITIAL_SIZE：哈希表的初始大小，值為 4

二笑诅、 dict 的 API

dict 的函數(shù)實(shí)現(xiàn)分為兩種调缨，一種是通過(guò)宏定義的函數(shù)，一種是在 dict.c 內(nèi)實(shí)現(xiàn)的函數(shù)吆你。

1. 宏定義函數(shù)

2. dict.c 中實(shí)現(xiàn)的函數(shù)

在 dict.c 中定義了幾個(gè)靜態(tài)變量：

// 表示字典是否啟用 rehash 
static int dict_can_resize = 1;

// 強(qiáng)制 rehash 的比率
static unsigned int dict_force_resize_ratio = 5;

// 哈希種子，用于 dictGenCaseHashFunction() 函數(shù)中
static uint32_t dict_hash_function_seed = 5381;

• dict_can_resize
  ??表示字典是否啟用 rehash 砌梆，程序可以通過(guò)后續(xù)在API 實(shí)現(xiàn)提及的dictEnableResize() 和 dictDisableResize() 函數(shù)默责，來(lái)手動(dòng)地允許或阻止哈希表進(jìn)行 rehash。但是咸包，即使該值為零桃序，也不是所有的 rehash 都會(huì)被阻止，這種情況與下列的 dict_force_resize_ratio 變量有關(guān)烂瘫。

• dict_force_resize_ratio
  ??字典強(qiáng)制 rehash 比率媒熊。當(dāng)某個(gè)哈希表的已有哈希節(jié)點(diǎn)的數(shù)量和字典大小之間的比率大于字典強(qiáng)制 rehash 比率奇适，即 size / used > dict_force_resize_ratio 時(shí)，即使 dict_can_resize = 0 也會(huì)強(qiáng)制執(zhí)行 rehash芦鳍。

• dict_hash_function_seed
  ??哈希種子嚷往，用于哈希函數(shù)之一的 dictGenCaseHashFunction() 函數(shù)中。

而在 dict.c 中實(shí)現(xiàn)的函數(shù)柠衅，有以下幾種類型：

（1）私有函數(shù)

（2）哈希函數(shù)

具體實(shí)現(xiàn)與分析日后單開(kāi)一篇進(jìn)行學(xué)習(xí)與分析。

（3）其余 API 實(shí)現(xiàn)

三沉眶、 dict 的特性

1. 每個(gè)字典帶有兩個(gè)哈希表 ht[0] 與 ht[1]
   ??由于隨著操作的進(jìn)行打却，哈希表中保存的鍵值對(duì)數(shù)量會(huì)隨之不斷地變化，為了使哈希表的負(fù)載因子保持在一個(gè)合理的范圍谎倔，會(huì)對(duì)哈希表進(jìn)行相應(yīng)的擴(kuò)展或者收縮柳击，所以需要進(jìn)行 rehash 操作。
   ??所以每個(gè)字典都會(huì)帶有兩個(gè)哈希表 ht[0] 與 ht[1]片习，其中捌肴，ht[0] 用于在平時(shí)使用，而 ht[1] 用于在 rehash 進(jìn)行時(shí)使用：將 ht[0] 上的所有結(jié)點(diǎn) rehash 到 ht[1] 上藕咏。
   ??rehash状知，指的是對(duì)鍵的哈希值與索引值重新計(jì)算，然后將鍵值對(duì)放到 ht[1] 的指定位置孽查。
   ??在 rehash 進(jìn)行時(shí)饥悴，新添加的哈希節(jié)點(diǎn)會(huì)被添加到哈希表 ht[1] 當(dāng)中，確保哈希表 ht[0] 當(dāng)中的結(jié)點(diǎn)只減不增卦碾。當(dāng) ht[0] 表中的結(jié)點(diǎn)全部遷移到 ht[1] 表中后铺坞，會(huì)釋放 ht[0] 表，將 ht[1] 設(shè)置為 ht[0]洲胖，并重置 ht[1]济榨。

2. 漸進(jìn)式 Rehash
   ??對(duì)于上述提到的 rehash 操作，并不是一次性全部遷移完成绿映，而是分多次擒滑、漸進(jìn)式地完成的，因?yàn)樵趯?shí)際環(huán)境中叉弦，哈希表中保存的節(jié)點(diǎn)實(shí)際上是非常多的丐一，如果一次性全部遷移的話，會(huì)對(duì)服務(wù)器的性能造成很大影響淹冰，甚至?xí)?dǎo)致服務(wù)器服務(wù)停止库车。
   ??具體來(lái)說(shuō)程拭，就是在對(duì)字典進(jìn)行添加宝惰、刪除、查找和更新操作時(shí)，會(huì)在需要 rehash 操作時(shí)進(jìn)行單步 rehash荠呐，從而將龐大的工作量分?jǐn)傞_(kāi)來(lái)胀茵。

3. 鍵沖突
   ??哈希表使用鏈地址法來(lái)解決鍵沖突红符，即被分配到同一索引的多個(gè)鍵值會(huì)拉成一個(gè)單向鏈表赞弥，正因?yàn)槿绱耍诓檎也僮鲿r(shí)難免會(huì)用到循環(huán)結(jié)構(gòu)阵漏，而新的哈希節(jié)點(diǎn)插入時(shí)也是采用頭插法來(lái)實(shí)現(xiàn)的驻民。