dict是一個(gè)用于維護(hù)key和value映射關(guān)系的數(shù)據(jù)結(jié)構(gòu)烦却，與很多語言中的Map或dictionary類似矾芙。redis實(shí)現(xiàn)了自己的dict實(shí)現(xiàn)菱鸥。redis數(shù)據(jù)庫底層主要使用字典dict來實(shí)現(xiàn)的铆帽，對(duì)redis數(shù)據(jù)庫db的增刪改查都是基于字典進(jìn)行操作的胞枕。這只是它在Redis中的一個(gè)用途而已压真，它在Redis中被使用的地方還有很多娩嚼。比如，一個(gè)Redis hash結(jié)構(gòu)滴肿，當(dāng)它的field較多時(shí)岳悟，便會(huì)采用dict來存儲(chǔ)。再比如泼差，Redis配合使用dict和skiplist來共同維護(hù)一個(gè)sorted set贵少。下面這篇文章先簡(jiǎn)單介紹redis的dict結(jié)構(gòu)體實(shí)現(xiàn)。
字典實(shí)體節(jié)點(diǎn)
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下個(gè)表節(jié)點(diǎn)堆缘，形成鏈表滔灶，解決鏈表沖突
struct dictEntry *next;
} dictEntry;
dictEntry是redis存儲(chǔ)數(shù)據(jù)的真正實(shí)體，其結(jié)構(gòu)中包含k, v和指向鏈表下一項(xiàng)的next指針吼肥。
- k是void指針录平，這意味著它可以指向任何類型。
- v是個(gè)union缀皱，當(dāng)它的值是uint64_t斗这、int64_t或double類型時(shí)，就不再需要額外的存儲(chǔ)啤斗，這有利于減少內(nèi)存碎片表箭。當(dāng)然，v也可以是void指針钮莲，以便能存儲(chǔ)任何類型的數(shù)據(jù)免钻。
- next指向下個(gè)表節(jié)點(diǎn)彼水，形成鏈表，解決hash沖突
字典表結(jié)構(gòu)體
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;
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
// hash表數(shù)組
dictEntry **table;
// hash表大小
unsigned long size;
// hash表大小掩碼极舔，用于計(jì)算索引值猿涨，大小等于size-1
unsigned long sizemask;
// hash表已有節(jié)點(diǎn)數(shù)量
unsigned long used;
} dictht;
dictType結(jié)構(gòu)包含若干函數(shù)指針，用于dict的調(diào)用者對(duì)涉及key和value的各種操作進(jìn)行自定義姆怪。這些操作包含：
- hashFunction叛赚，對(duì)key進(jìn)行哈希值計(jì)算的哈希算法。
- keyDup和valDup稽揭，分別定義key和value的拷貝函數(shù)俺附，用于在需要的時(shí)候?qū)ey和value進(jìn)行深拷貝，而不僅僅是傳遞對(duì)象指針溪掀。
- keyCompare事镣，定義兩個(gè)key的比較操作，在根據(jù)key進(jìn)行查找時(shí)會(huì)用到揪胃。
- keyDestructor和valDestructor璃哟，分別定義對(duì)key和value的析構(gòu)函數(shù)。
dictht結(jié)構(gòu)喊递，它定義一個(gè)哈希表的結(jié)構(gòu)随闪，由如下若干項(xiàng)組成：
- table: 一個(gè)dictEntry指針數(shù)組。key的哈希值最終映射到這個(gè)數(shù)組的某個(gè)位置上（對(duì)應(yīng)一個(gè)bucket）骚勘。如果多個(gè)key映射到同一個(gè)位置铐伴，就發(fā)生了沖突，那么就拉出一個(gè)dictEntry鏈表俏讹。
- size：標(biāo)識(shí)dictEntry指針數(shù)組的長(zhǎng)度当宴。它總是2的指數(shù)。
- sizemask：用于將哈希值映射到table的位置索引泽疆。它的值等于(size-1)户矢，比如7, 15, 31, 63，等等殉疼，也就是用二進(jìn)制表示的各個(gè)bit全1的數(shù)字梯浪。每個(gè)key先經(jīng)過hashFunction計(jì)算得到一個(gè)哈希值，然后計(jì)算(哈希值 & sizemask)得到在table上的位置株依。相當(dāng)于計(jì)算取余(哈希值 % size)驱证。
- used：記錄dict中現(xiàn)有的數(shù)據(jù)個(gè)數(shù)。它與size的比值就是裝載因子（load factor）恋腕。這個(gè)比值越大抹锄，哈希值沖突概率越高。
字典
typedef struct dict {
// 類型特定函數(shù)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 包含兩個(gè)dictht的數(shù)組，一般使用ht[0]伙单，rehash才會(huì)使用的ht[1]
dictht ht[2];
// rehash索引
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
dict的結(jié)構(gòu)由如下若干項(xiàng)組成：
- 一個(gè)指向dictType結(jié)構(gòu)的指針（type）获高。它通過自定義的方式使得dict的key和value能夠存儲(chǔ)任何類型的數(shù)據(jù)。
- 一個(gè)私有數(shù)據(jù)指針（privdata）吻育。由調(diào)用者在創(chuàng)建dict的時(shí)候傳進(jìn)來念秧。type與privdata針對(duì)不同類型的鍵值對(duì)，實(shí)現(xiàn)多態(tài)布疼。
- 兩個(gè)哈希表（ht[2]）摊趾。只有在重哈希的過程中，ht[0]和ht[1]才都有效游两。而在平常情況下砾层，只有ht[0]有效，ht[1]里面沒有任何數(shù)據(jù)贱案。上圖表示的就是重哈希進(jìn)行到中間某一步時(shí)的情況肛炮。
- 當(dāng)前重哈希索引（rehashidx）。如果rehashidx = -1宝踪，表示當(dāng)前沒有在重哈希過程中侨糟；否則，表示當(dāng)前正在進(jìn)行重哈希瘩燥，且它的值記錄了當(dāng)前重哈希進(jìn)行到哪一步了秕重。
- 當(dāng)前正在進(jìn)行遍歷的iterator的個(gè)數(shù)。
下圖可以清晰展示redis的dict的數(shù)據(jù)結(jié)構(gòu)
參考：
http://zhangtielei.com/posts/blog-redis-dict.html
《redis設(shè)計(jì)與實(shí)現(xiàn)》第二版
