結構
Redis 字典的結構和 Java 中的 HashMap 有點類似，都是存放鍵值對，在底層都是使用數組加鏈表（稱為一個哈希表）的形式來實現的，但與 HashMap 不同的是，在 Redis 中，它由兩個哈希表組成，它的結構大致如下圖所示：
由上圖可以看到，它使用兩個 hashtable ，姑且稱之為 0 號哈希表和 1 號哈希表，每次只會使用 0 號哈希表，那么 1 號哈希表有什么用呢？當哈希表的鍵值對很多或很少的話，就需要對哈希表進行擴展或縮小，比如哈希表中數組的大小默認為 4 ，如果哈希表中鍵值對很多，則數組中每項的鏈表就會很長，而鏈表查找速度很很慢，不像數組那樣根據索引定位，所以為了讓哈希表的負載因子（load factor）維持在一個合理的范圍內，就需要對哈希表進行擴展或縮小，稱為 rehash。
結構定義
接下來看下上述結構圖的定義，
首先看下字典結構的定義：
typedef struct dict {
dictType *type; //字典類型
void *privdata; //私有數據
dictht ht[2]; // 哈希表，有兩個，實現漸進式rehash
long rehashidx; // rehash 索引，當不進行rehash的時候，值為-1
unsigned long iterators; // 當前正在運行的迭代器的數量
} dict;
其中，dictht ht[2] 對應的是上圖中的ht[0]和[1]。
之后，看下哈希表的定義：
/*
* 哈希表
*/
typedef struct dictht {
// 哈希表數組
dictEntry **table;
// 哈希表大小
unsigned long size;
unsigned long sizemask;
// 該哈希表已有節點的數量
unsigned long used;
} dictht;
對應的上圖中的哈希表數組，數組中的每一項是鏈表，鏈表節點使用 dictEntry 表示，接下來看下 dictEntry 的定義：
//哈希表節點
typedef struct dictEntry {
// 鍵
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下個哈希表節點，形成鏈表
struct dictEntry *next;
} dictEntry;
以上的定義就表示的字典的數據結構，上述的定義代碼是在 dict.h 文件中，該文件中，除了上述代碼外，還有一些其他的API定義，如迭代器等。
接下來看下字典的操作，如添加元素，刪除元素，查找元素，rehash 等，這個操作代碼主要是在 dict.c 文件中
字典操作
首先看下幾個公共的方法；
_dictInit
初始化哈希表
int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
// 初始化兩個哈希表的各項屬性值
// 但暫時還不分配內存給哈希表數組
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
d->type = type; // 設置類型
d->privdata = privDataPtr; // 設置私有數據
d->rehashidx = -1; // 設置 rehash的狀態，表示不正在rehash
d->iterators = 0; // 設置安全迭代器數量
return DICT_OK;
}
_dictKeyIndex
根據 key 來獲取添加的這個鍵值對應該存放在哈希表中的索引。
//如果 key 已經存在于哈希表，那么返回 -1
//如果字典正在進行 rehash ，那么總是返回 1 號哈希表的索引。因為在字典進行 rehash 時，新節點總是插入到 1 號哈希表。
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
unsigned long idx, table;
dictEntry *he;
if (existing) *existing = NULL;
// 哈希表是否需要擴展
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
// 遍歷 0 號哈希表和 1 號哈希表
for (table = 0; table <= 1; table++) {
// 獲取哈希表中的每一項
idx = hash & d->ht[table].sizemask;
//獲取每一項的鏈表
he = d->ht[table].table[idx];
// 遍歷鏈表
while(he) {
// 如果key 存在，則放回 -1
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
return -1;
}
he = he->next;
}
// 如果哈希表沒有正在進行rehash操作，則表示只有 0 號哈希表中有數據，就不要在 1 號哈希表中進行查找
// 否則的話，就還需要遍歷 1 號哈希表進行查找
if (!dictIsRehashing(d)) break;
}
// 返回索引
return idx;
}
_dictExpandIfNeeded
哈希表是否需要擴展
static int _dictExpandIfNeeded(dict *d)
{
// 如果正在進行 rehash，則表示正在進行擴展，直接返回 OK
if (dictIsRehashing(d)) return DICT_OK;
// 如果 0 號哈希表為空，則需要對哈希表進行初始化，初始化哈希表數組的大小為DICT_HT_INITIAL_SIZE
// #define DICT_HT_INITIAL_SIZE 4
// 可以看到，哈希表數組的初始大小為 4
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 以下兩個條件之一為真時，對字典進行擴展
// 1）字典已使用節點數和字典大小之間的比率接近 1：1 并且 dict_can_resize 為真
// 2）已使用節點數和字典大小之間的比率超過 dict_force_resize_ratio
// static unsigned int dict_force_resize_ratio = 5;
if (d->ht[0].used >= d->ht[0].size && (dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
// 新哈希表的大小至少是目前已使用節點數的兩倍
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
上述代碼中，如果哈希表為空，即是次添加元素的時候，需要初始化哈希表，哈希表的大小為 4 ，如下所示：
擴展的哈希表大小為已使用節點的2倍，如果哈希表的大小為 4 ，已使用節點數量為24， 則 24/4 > 5 ，就需要對哈希表進行擴展，此時哈希表的大小為 24*2 = 48。
擴展哈希表的過程
如下圖所示：
刪除節點
// 刪除成功，返回 OK ， 如果找不到對應的鍵，則刪除失敗
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
// 查找并刪除包含給定鍵的節點
// 參數 nofree 決定是否調用鍵和值的釋放函數, 0 表示調用，1 表示不調用
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
uint64_t h, idx;
dictEntry *he, *prevHe;
int table;
// 0 號哈希表和 1 號哈希表中使用節點的數量都為0，表示哈希表為空
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
//計算key的哈希值
h = dictHashKey(d, key);
//兩個哈希表，表示需要在兩個哈希表中查找
for (table = 0; table <= 1; table++) {
//計算索引值
idx = h & d->ht[table].sizemask;
//指向該索引上的鏈表
he = d->ht[table].table[idx];
// 當前節點的上一個節點
prevHe = NULL;
//遍歷該鏈表上的所有節點
while(he) {
// 找到要刪除的key
if (key==he->key || dictCompareKeys(d, key, he->key)) {
//從鏈表上刪除該節點
if (prevHe) // 如果要刪除的節點的前一個節點不為空，表示刪除節點不是個節點
prevHe->next = he->next;
else // 如果要刪除的節點是個節點，則直接把該節點的下一個節點設置為該鏈表的頭節點
d->ht[table].table[idx] = he->next;
//釋放鍵和值
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
}
//使用節點減1
d->ht[table].used--;
//返回刪除的節點
return he;
}
// 把當前節點設置為前一個節點
prevHe = he;
//查找下一個節點
he = he->next;
}
// 如果字典不正在進行 rehash，表示只有 0 號哈希表中有數據，不需要在 1 號哈希表中進行查找
// 否則，如果 rehash 正在進行，則還需要在 1 號哈希表中進行查找刪除
if (!dictIsRehashing(d)) break;
}
return NULL; /* not found */
}
刪除節點的過程如下：
if (prevHe) // 如果要刪除的節點的前一個節點不為空，則刪除該節點
prevHe->next = he->next;
else // 如果要刪除的節點是個節點，則直接把該節點的下一個節點設置為該鏈表的頭節點
d->ht[table].table[idx] = he->next;
前一個節點不為空：prevHe->next = he->next
要刪除的是個節點：d->ht[table].table[idx] = he->next
dictFetchValue
查找對應鍵的值，
//返回對應鍵的值
void *dictFetchValue(dict *d, const void *key) {
dictEntry *he;
he = dictFind(d,key);
return he ? dictGetVal(he) : NULL;
}
//查找key對應的節點
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
uint64_t h, idx, table;
//哈希表為空
if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
// 正在rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 計算鍵的哈希值
h = dictHashKey(d, key);
//在 0 號哈希表和 1 號哈希表中查找
for (table = 0; table <= 1; table++) {
// 索引值
idx = h & d->ht[table].sizemask;
// 索引值對應的鏈表
he = d->ht[table].table[idx];
// 遍歷鏈表
while(he) {
// 找到就返回
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 如果正在進行rehash，1號哈希表中可能也有數據，則需要再在1號哈希表中進行查找，
// 如果rehash完畢了，表示只有0號哈希表中有數據，就不需要在1號哈希表中查找了，直接返回null
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
命令操作字典
接下來看下 hash， sets 和 sorted sets 命令是如何操作字典的。
hash 操作字典
添加操作：
// hash 底層存放數據不僅僅是字典這種數據結構，還有壓縮列表等結構
int hashTypeSet(robj *o, sds field, sds value, int flags) {
int update = 0;
if (o->encoding == OBJ_ENCODING_ZIPLIST) {
........................
// 如果該對象的編碼方式是字典的方式，則需要在字典中添加該鍵值對
} else if (o->encoding == OBJ_ENCODING_HT) {
dictEntry *de = dictFind(o->ptr,field);
// 如果已存在，則更新
if (de) {
sdsfree(dictGetVal(de));
if (flags & HASH_SET_TAKE_VALUE) {
dictGetVal(de) = value;
value = NULL;
} else {
dictGetVal(de) = sdsdup(value);
}
update = 1;
} else {
sds f,v;
if (flags & HASH_SET_TAKE_FIELD) {
f = field;
field = NULL;
} else {
f = sdsdup(field);
}
if (flags & HASH_SET_TAKE_VALUE) {
v = value;
value = NULL;
} else {
v = sdsdup(value);
}
// 向字典中添加元素
dictAdd(o->ptr,f,v);
}
}
......................
return update;
}
查找操作：
sds hashTypeGetFromHashTable(robj *o, sds field) {
dictEntry *de;
// 編碼格式為哈希表
serverAssert(o->encoding == OBJ_ENCODING_HT);
// 在哈希表中查找
de = dictFind(o->ptr, field);
if (de == NULL) return NULL;
// 返回對應的值
return dictGetVal(de);
}
刪除操作：
int hashTypeDelete(robj *o, sds field) {
int deleted = 0;
if (o->encoding == OBJ_ENCODING_ZIPLIST) {
......................
// 編碼方式為哈希表
} else if (o->encoding == OBJ_ENCODING_HT) {
// 從哈希表中刪除元素
if (dictDelete((dict*)o->ptr, field) == C_OK) {
deleted = 1;
if (htNeedsResize(o->ptr)) dictResize(o->ptr);
}
} else {
serverPanic("Unknown hash encoding");
}
return deleted;
}
sets 操作字典
添加操作:
int setTypeAdd(robj *subject, sds value) {
long long llval;
// 如果編碼方式為哈希表
if (subject->encoding == OBJ_ENCODING_HT) {
dict *ht = subject->ptr;
// 在哈希表中添加元素
dictEntry *de = dictAddRaw(ht,value,NULL);
if (de) {
dictSetKey(ht,de,sdsdup(value));
dictSetVal(ht,de,NULL);
return 1;
}
} else if (subject->encoding == OBJ_ENCODING_INTSET) {
....................
} else {
serverPanic("Unknown set encoding");
}
return 0;
}
刪除操作：
int setTypeRemove(robj *setobj, sds value) {
long long llval;
// 編碼方式為哈希表
if (setobj->encoding == OBJ_ENCODING_HT) {
// 在哈希表中刪除元素
if (dictDelete(setobj->ptr,value) == DICT_OK) {
if (htNeedsResize(setobj->ptr)) dictResize(setobj->ptr);
return 1;
}
} else if (setobj->encoding == OBJ_ENCODING_INTSET) {
..............
} else {
serverPanic("Unknown set encoding");
}
return 0;
}
以上就是 Redis 中字典的實現原理