字典是Redis的重要數(shù)據(jù)結(jié)構(gòu)题禀，Redis的數(shù)據(jù)庫就是使用字典作為底層實(shí)現(xiàn)的。代碼位于dict.h和dict.c中。
1. 字典（Dict）
1.1 哈希表（Hash Table）
Redis使用哈希表實(shí)現(xiàn)字典伙判。
哈希表存儲鍵值對，將鍵的哈希值映射到存儲位置（即索引值）黑忱，加快訪問速度宴抚。
Redis默認(rèn)哈希算法為SipHash（待以后寫文分析）勒魔，使用數(shù)組+鏈表作為哈希表數(shù)據(jù)結(jié)構(gòu)（即鏈地址法），哈希值模數(shù)組大小即為索引值菇曲。
1.2 Redis哈希表
哈希表結(jié)構(gòu)
哈希表結(jié)構(gòu)如上圖所示冠绢，為行文方便定義幾個(gè)名詞指代上圖中的組件結(jié)構(gòu)：
- ht（哈希表）：最左邊的組件即為哈希表
- table（桶數(shù)組）：ht中有字段指向數(shù)組，此數(shù)組稱為table常潮，數(shù)組長度即為哈希表大小
- bucket（桶）：table的每一項(xiàng)稱為bucket弟胀，bucket指向具有相同索引值的鍵值對鏈表
- entry（節(jié)點(diǎn)）：鏈表里的節(jié)點(diǎn)稱為entry，entry包裝了鍵值對的key和value喊式，同時(shí)包含next指針指向鏈表的下一節(jié)點(diǎn)
- 哈希表
typedef struct dictht {
// 哈希桶數(shù)組
dictEntry **table;
// 哈希表大小孵户，即數(shù)組長度
unsigned long size;
// 哈希表大小掩碼常量，為數(shù)組長度-1岔留，與哈希值與計(jì)算得出索引值
unsigned long sizemask;
// 哈希表已有鍵值對數(shù)量
// 裝載因子 = used / size
unsigned long used;
} dictht;
- 哈希表節(jié)點(diǎn)
typedef struct dictEntry {
// 鍵
void *key;
// 值延届，使用union以適應(yīng)不同類型的值
union {
void *val; // 整數(shù)與浮點(diǎn)數(shù)直接存儲，其它類型使用引用
uint64_t u64; // 無符號整數(shù)
int64_t s64; // 有符號整數(shù)
double d; // 浮點(diǎn)數(shù)
} v;
// 指向下一個(gè)節(jié)點(diǎn)
struct dictEntry *next;
} dictEntry;
1.3 字典
字典結(jié)構(gòu)
字典結(jié)構(gòu)為上圖所示贸诚，左邊組件即為字典（本文稱為dict）方庭，每個(gè)字典包含兩個(gè)哈希表（本文稱之為ht[0]和ht[1]）。代碼定義如下：
- 字典
typedef struct dict {
// 指向字典類型結(jié)構(gòu)
dictType *type;
// 私有數(shù)據(jù)
void *privdata;
// 2個(gè)哈希表
dictht ht[2];
// rehash索引酱固，rehash未進(jìn)行時(shí)其值為-1
long rehashidx;
// 當(dāng)前的迭代器數(shù)量
unsigned long iterators;
} dict;
- 字典類型
// 字典類型械念，保存一組操作特定類型鍵值對的函數(shù)
// Redis為不同的字典設(shè)置不同的類型特定函數(shù)
typedef struct dictType {
// 計(jì)算哈希值
uint64_t (*hashFunction)(const void *key);
// 復(fù)制鍵
void *(*keyDup)(void *privdata, const void *key);
// 復(fù)制值
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;
1.4 rehash（重哈希）
在初期，字典只使用ht[0]哈希表运悲，ht[1]為空龄减。隨著操作的不斷進(jìn)行，ht[0]中元素最終會偏多或偏少班眯，為了使哈希表的裝載因子維持在一個(gè)合理范圍希停，Redis使用rehash對哈希表進(jìn)行伸縮。
rehash的基本原理是新建ht[1]哈希表署隘，將ht[0]中的元素重新計(jì)算哈希值和索引值宠能，然后遷移到ht[1]。但是如果字典中的元素?cái)?shù)量太多磁餐，一次性地遷移所有元素會耗費(fèi)很長時(shí)間违崇，因此Redis采用分步漸進(jìn)式rehash。
分步rehash的基本原理是將一次rehash拆分成多步來完成诊霹，每步只將ht[0]中一個(gè)bucket的元素遷移到ht[1]羞延，直到全部遷移。分步rehash詳細(xì)步驟如下：
- 每次添加元素時(shí)脾还，判斷是否需要rehash
- 允許rehash伴箩，裝載因子達(dá)到1時(shí)
- 不允許rehash，但裝載因子達(dá)到5時(shí)
- 需要rehash鄙漏，則
- 新建ht[1]哈希表嗤谚，其大小是：
- 若是擴(kuò)張棺蛛，為大于等于現(xiàn)有節(jié)點(diǎn)數(shù)2倍的最小2次冪
- 若是收縮，為大于等于現(xiàn)有節(jié)點(diǎn)的最小2次冪
- 將字典的rehashidx字段置為0呵恢，表示開始rehash（未開始時(shí)為-1）
- rehash對table中的bucket按順序逐個(gè)遷移鞠值，rehashidx實(shí)際是下一步要遷移bucket的數(shù)組下標(biāo)
- 新建ht[1]哈希表嗤谚，其大小是：
- 開始rehash后，每次對字典進(jìn)行增刪查改操作時(shí)渗钉，順帶進(jìn)行一步rehash彤恶，將一個(gè)bucket的所有元素從ht[0]遷移到ht[1]
- 最終，ht[0]中的所有元素遷移到ht[1]鳄橘，然后釋放ht[0]声离，將ht[1]置為ht[0]，rehashidx復(fù)位為-1瘫怜，一次完整的rehash結(jié)束术徊。
2. 創(chuàng)建字典
// 傳入字典類型和私有數(shù)據(jù)，創(chuàng)建字典
dict *dictCreate(dictType *type, void *privDataPtr)
{
// 申請內(nèi)存
dict *d = zmalloc(sizeof(*d));
// 初始化
_dictInit(d,type,privDataPtr);
return d;
}
// 初始化字典
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;
d->iterators = 0;
return DICT_OK;
}
// 重置哈希表：全部置空
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
3. 添加元素
3.1 哈希值鲸湃、鍵赠涮、值
- 計(jì)算鍵的哈希值
// 調(diào)用字典類型的hashFunction函數(shù)計(jì)算鍵的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)
- 比較鍵
// 若字典類型的keyCompare函數(shù)存在，則使用函數(shù)比較暗挑，否則比較是否是相同引用
#define dictCompareKeys(d, key1, key2) \
(((d)->type->keyCompare) ? \
(d)->type->keyCompare((d)->privdata, key1, key2) : \
(key1) == (key2))
- 設(shè)置鍵
// 若字典類型的keyDup函數(shù)存在笋除，則使用函數(shù)計(jì)算后賦值，否則直接賦值
#define dictSetKey(d, entry, _key_) do { \
if ((d)->type->keyDup) \
(entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
else \
(entry)->key = (_key_); \
} while(0)
- 釋放鍵
// 若字典類型的keyDestructor函數(shù)存在炸裆，則使用函數(shù)銷毀鍵
#define dictFreeKey(d, entry) \
if ((d)->type->keyDestructor) \
(d)->type->keyDestructor((d)->privdata, (entry)->key)
- 設(shè)置值
// 若字典類型的valDup函數(shù)存在垃它，則使用函數(shù)計(jì)算后賦值，否則直接賦值
#define dictSetVal(d, entry, _val_) do { \
if ((d)->type->valDup) \
(entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
else \
(entry)->v.val = (_val_); \
} while(0)
- 釋放值
// 若字典類型的valDestructor函數(shù)存在烹看，則使用函數(shù)銷毀值
#define dictFreeVal(d, entry) \
if ((d)->type->valDestructor) \
(d)->type->valDestructor((d)->privdata, (entry)->v.val)
3.2 rehash
- 判斷是否處于rehash中
#define dictIsRehashing(d) ((d)->rehashidx != -1)
- 完成一步rehash
static void _dictRehashStep(dict *d) {
// 只有在無迭代器才進(jìn)行rehash
// 如果rehash時(shí)有迭代器国拇，不能對哈希表中的元素遷移，否則可能導(dǎo)致迭代時(shí)元素錯(cuò)過或重復(fù)
if (d->iterators == 0) dictRehash(d,1);
}
- 通用：完成n步rehash
// 進(jìn)行n步rehash惯殊，如果還有鍵需要遷移則返回1酱吝，否則返回0
// 如果遇到空桶則繼續(xù)，遇到N*10個(gè)空桶則返回靠胜，避免阻塞過久
int dictRehash(dict *d, int n) {
// 允許遇到的最大空桶數(shù)
int empty_visits = n*10;
if (!dictIsRehashing(d)) return 0;
// 如果ht[0]仍有元素掉瞳，則進(jìn)行下一步rehash
while(n-- && d->ht[0].used != 0) {
dictEntry *de, *nextde;
// rehashidx是下一個(gè)要遷移的桶的數(shù)組下標(biāo)，自然要小于數(shù)組長度
assert(d->ht[0].size > (unsigned long)d->rehashidx);
// 如果遇到空桶浪漠，則順延到下一個(gè)bucket，直到遇到最大空桶數(shù)霎褐，就返回
while(d->ht[0].table[d->rehashidx] == NULL) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
// 獲取bucket鏈表的頭節(jié)點(diǎn)
de = d->ht[0].table[d->rehashidx];
// 遍歷鏈表的節(jié)點(diǎn)址愿，全部遷移到ht[1]
while(de) {
unsigned int h;
// 獲取下一節(jié)點(diǎn)
nextde = de->next;
// 計(jì)算遷移元素在ht[1]的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 遷移到ht[1]相應(yīng)bucket鏈表頭部
// ht[0]中的鏈表，因?yàn)槿窟w移冻璃，所以遷移單個(gè)節(jié)點(diǎn)時(shí)不進(jìn)行處理
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
// 修改計(jì)數(shù)
d->ht[0].used--;
d->ht[1].used++;
// 迭代下一節(jié)點(diǎn)
de = nextde;
}
// ht[0]遷移的bucket置空
d->ht[0].table[d->rehashidx] = NULL;
// 設(shè)置下一步rehash要處理的bucket索引下標(biāo)
d->rehashidx++;
}
// 如果ht[0]中元素全部遷移完畢
if (d->ht[0].used == 0) {
// 釋放ht[0]
zfree(d->ht[0].table);
// 將ht[1]哈希表設(shè)置為ht[0]
d->ht[0] = d->ht[1];
// ht[1]清空復(fù)位响谓，以待下次rehash
_dictReset(&d->ht[1]);
// rehash狀態(tài)設(shè)置為未開始
d->rehashidx = -1;
// 此次rehash完畢损合，返回0
return 0;
}
// 未遷移完畢，還需下一步rehash娘纷，返回1
return 1;
}
3.3 字典的擴(kuò)張
- 如果需要?jiǎng)t對字典進(jìn)行擴(kuò)張
static int _dictExpandIfNeeded(dict *d)
{
// 如果正在rehash中嫁审，返回
if (dictIsRehashing(d)) return DICT_OK;
// 如果ht[0]為空哈希表，則對其進(jìn)行初始化
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 如果允許resize赖晶，且裝載因子達(dá)到1
// 如果不允許resize律适，且裝載因子達(dá)到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)) {
// 按照當(dāng)前節(jié)點(diǎn)數(shù)的2倍進(jìn)行擴(kuò)張（進(jìn)行rehash）
return dictExpand(d, d->ht[0].used*2);
}
return DICT_OK;
}
- 相關(guān)參數(shù)
// 字典初始大小
#define DICT_HT_INITIAL_SIZE 4
// 默認(rèn)允許resize
static int dict_can_resize = 1;
// 不允許resize時(shí)，強(qiáng)制進(jìn)行resize要達(dá)到的負(fù)載因子
static unsigned int dict_force_resize_ratio = 5;
- 獲取大于等于指定大小的最小2次冪遏插，作為實(shí)際哈希表的大小
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size) return i;
i *= 2;
}
}
- 將字典擴(kuò)張到指定大小
int dictExpand(dict *d, unsigned long size)
{
// 創(chuàng)建新哈希表ht[1]
dictht n;
// 將指定大小值進(jìn)行規(guī)整：不小于size的最小2次冪值
unsigned long realsize = _dictNextPower(size);
// 判斷擴(kuò)張大小無效的情況
if (dictIsRehashing(d) || d->ht[0].used > size)
return DICT_ERR;
if (realsize == d->ht[0].size) return DICT_ERR;
// 設(shè)置新哈希表屬性
n.size = realsize;
n.sizemask = realsize-1;
// 按新的哈希表大小創(chuàng)建table數(shù)組
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 若是初始化捂贿，則此次不是rehash，將新哈希表設(shè)置為ht[0]即可胳嘲。
if (d->ht[0].table == NULL) {
d->ht[0] = n;
return DICT_OK;
}
// 若ht[0]存在厂僧，則此次是rehash，將新哈希表設(shè)置為ht[1]
// 并且設(shè)置為開始rehash狀態(tài)了牛，以便操作元素時(shí)進(jìn)行rehash
d->ht[1] = n;
d->rehashidx = 0;
return DICT_OK;
}
3.4 添加元素
- 向字典添加鍵值對
int dictAdd(dict *d, void *key, void *val)
{
// 將鍵構(gòu)造成節(jié)點(diǎn)加入哈希表
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
// 設(shè)置節(jié)點(diǎn)的值
dictSetVal(d, entry, val);
return DICT_OK;
}
- 添加或查找鍵颜屠，若查找到則existing指向節(jié)點(diǎn)返回null，若添加成功則返回節(jié)點(diǎn)
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
int index;
dictEntry *entry;
dictht *ht;
// 若處于rehash中鹰祸，則完成一步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 計(jì)算鍵的哈希值甫窟，判斷鍵是否已存在
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
return NULL;
// 若正在rehash，則使用ht[1]哈希表福荸，否則使用ht[0]哈希表
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 為哈希表節(jié)點(diǎn)申請內(nèi)存
entry = zmalloc(sizeof(*entry));
// 根據(jù)鍵的索引值尋找bucket鏈表蕴坪，插入到表頭
entry->next = ht->table[index];
ht->table[index] = entry;
// 增加節(jié)點(diǎn)計(jì)數(shù)
ht->used++;
// 設(shè)置節(jié)點(diǎn)的鍵
dictSetKey(d, entry, key);
return entry;
}
- 查找鍵是否已在哈希表中，若存在返回-1敬锐，若不存在則返回鍵的索引值
// 若existing非空背传，且鍵在哈希表中，則設(shè)置其指向鍵的節(jié)點(diǎn)
static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
unsigned int idx, table;
dictEntry *he;
if (existing) *existing = NULL;
// 檢查字典裝載因子台夺，若需要?jiǎng)t擴(kuò)張字典
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
// 遍歷哈希表
for (table = 0; table <= 1; table++) {
// 找到鍵的索引值對應(yīng)的bucket
idx = hash & d->ht[table].sizemask;
// 遍歷bucket中的節(jié)點(diǎn)
he = d->ht[table].table[idx];
while(he) {
// 判斷節(jié)點(diǎn)與鍵是否相同
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
// 如果找到鍵径玖，返回-1
return -1;
}
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
4. 查找元素
// 查找鍵對應(yīng)的節(jié)點(diǎn)
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
unsigned int h, idx, table;
// 若字典為空返回NULL
if (d->ht[0].used + d->ht[1].used == 0) return NULL;
// 若正在rehash，進(jìn)行一步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 計(jì)算鍵的哈希值
h = dictHashKey(d, key);
// 遍歷兩個(gè)哈希表
for (table = 0; table <= 1; table++) {
// 計(jì)算鍵在哈希表的索引值
idx = h & d->ht[table].sizemask;
// 獲取鍵所在bucket鏈表的頭節(jié)點(diǎn)
he = d->ht[table].table[idx];
// 遍歷鏈表節(jié)點(diǎn)
while(he) {
// 若鍵相同颤介，則返回節(jié)點(diǎn)
if (key==he->key || dictCompareKeys(d, key, he->key))
return he;
he = he->next;
}
// 若沒有在rehash梳星，則ht[1]為空，不需要遍歷滚朵，直接返回
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
5. 替代元素
// 若鍵存在則替代值冤灾，若不存在則添加鍵值對
// 添加成功返回1，替代成功返回0
int dictReplace(dict *d, void *key, void *val)
{
dictEntry *entry, *existing, auxentry;
// dictAddRaw：若鍵存在辕近，則existing指向節(jié)點(diǎn)返回null韵吨，若鍵不存在，則添加并返回節(jié)點(diǎn)
entry = dictAddRaw(d,key,&existing);
if (entry) {
// 添加成功移宅，設(shè)置值归粉，返回1
dictSetVal(d, entry, val);
return 1;
}
// 更新節(jié)點(diǎn)：設(shè)置新值椿疗、釋放舊值、返回0
auxentry = *existing;
dictSetVal(d, existing, val);
dictFreeVal(d, &auxentry);
return 0;
}
6. 刪除元素
// 刪除鍵對應(yīng)的元素糠悼，成功返回DICT_OK届榄，找不到元素返回DICT_ERR
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
// 刪除鍵對應(yīng)的元素，刪除成功返回其節(jié)點(diǎn)倔喂，找不到元素返回NULL
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
// 字典為空返回NULL
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
// 正在rehash铝条，進(jìn)行一步rehash
if (dictIsRehashing(d)) _dictRehashStep(d);
// 計(jì)算鍵的哈希值
h = dictHashKey(d, key);
// 遍歷哈希表
for (table = 0; table <= 1; table++) {
// 計(jì)算鍵的索引值
idx = h & d->ht[table].sizemask;
// 鍵所在bucket鏈表的頭節(jié)點(diǎn)
he = d->ht[table].table[idx];
prevHe = NULL;
// 從頭節(jié)點(diǎn)依次遍歷整個(gè)鏈表
while(he) {
// 若找到相同鍵節(jié)點(diǎn)
if (key==he->key || dictCompareKeys(d, key, he->key)) {
// 將節(jié)點(diǎn)從鏈表中移除
if (prevHe) // 若是中間節(jié)點(diǎn)
prevHe->next = he->next;
else // 若是頭節(jié)點(diǎn)
d->ht[table].table[idx] = he->next;
if (!nofree) {
// 釋放鍵
dictFreeKey(d, he);
// 釋放值
dictFreeVal(d, he);
// 釋放節(jié)點(diǎn)
zfree(he);
}
// 節(jié)點(diǎn)計(jì)數(shù)減1
d->ht[table].used--;
// 返回刪除的節(jié)點(diǎn)
return he;
}
// 當(dāng)前節(jié)點(diǎn)不是，移動到下一節(jié)點(diǎn)
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL;
}
7. 釋放字典
// 清空并釋放字典
void dictRelease(dict *d)
{
// 清空兩個(gè)哈希表
_dictClear(d,&d->ht[0],NULL);
_dictClear(d,&d->ht[1],NULL);
// 釋放字典內(nèi)存
zfree(d);
}
// 清空哈希表
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
unsigned long i;
// 遍歷哈希表所有節(jié)點(diǎn)
for (i = 0; i < ht->size && ht->used > 0; i++) {
dictEntry *he, *nextHe;
if (callback && (i & 65535) == 0) callback(d->privdata);
// 若遇到空桶滴劲，跳過
if ((he = ht->table[i]) == NULL) continue;
// 從桶的頭節(jié)點(diǎn)開始遍歷節(jié)點(diǎn)攻晒，釋放節(jié)點(diǎn)的鍵、值和內(nèi)存
while(he) {
nextHe = he->next;
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
ht->used--;
he = nextHe;
}
}
// 釋放table數(shù)組
zfree(ht->table);
// 重置字典
_dictReset(ht);
return DICT_OK;
}
8. 迭代器
8.1 迭代器定義
// 如果safe為1班挖，則是安全迭代器鲁捏，可在迭代時(shí)可調(diào)用dictAdd、dictFind以及其它函數(shù)
// 如果safe為0萧芙，則是非安全迭代器给梅，在迭代時(shí)只可調(diào)用dictNext()
typedef struct dictIterator {
// 字典引用
dict *d;
// 字典的哈希表下標(biāo)
int table;
// 哈希表的bucket數(shù)組下標(biāo)
long index;
// 指向bucket的鏈表中上一次返回的節(jié)點(diǎn)
dictEntry *entry;
// 指向bucket的鏈表中下一次返回的節(jié)點(diǎn)
dictEntry *nextEntry;
// 1，安全模式双揪；0动羽，非安全模式
int safe;
// 非安全模式下，在迭代器創(chuàng)建時(shí)渔期，計(jì)算字典狀態(tài)的指紋
long long fingerprint;
} dictIterator;
8.2 獲取迭代器
// 非安全迭代器
dictIterator *dictGetIterator(dict *d)
{
dictIterator *iter = zmalloc(sizeof(*iter));
// 設(shè)置字典引用
iter->d = d;
// 指向ht[0]哈希表
iter->table = 0;
iter->index = -1;
// 非安全模式
iter->safe = 0;
iter->entry = NULL;
iter->nextEntry = NULL;
return iter;
}
// 安全迭代器
dictIterator *dictGetSafeIterator(dict *d) {
dictIterator *i = dictGetIterator(d);
i->safe = 1;
return i;
}
8.3 獲取下一元素
// 使用迭代器獲取下一元素
// 按照哈希表數(shù)組运吓、bucket數(shù)組、節(jié)點(diǎn)鏈表依次遍歷節(jié)點(diǎn)
dictEntry *dictNext(dictIterator *iter)
{
while (1) {
// entry為null疯趟，表示已遍歷完一個(gè)bucket的鏈表拘哨，或者是第一次使用迭代器
if (iter->entry == NULL) {
// 獲取當(dāng)前的哈希表
dictht *ht = &iter->d->ht[iter->table];
// 如果是初次使用迭代器，設(shè)置相關(guān)參數(shù)
if (iter->index == -1 && iter->table == 0) {
// 若為安全迭代器信峻，則字典的迭代器計(jì)數(shù)加1
if (iter->safe)
iter->d->iterators++;
// 若為非安全迭代器倦青，計(jì)算字典當(dāng)前狀態(tài)的指紋
else
iter->fingerprint = dictFingerprint(iter->d);
}
// 遍歷完一個(gè)bucket，則順延至下一bucket
iter->index++;
// 若當(dāng)前哈希表已遍歷完
if (iter->index >= (long) ht->size) {
// 若為遍歷完ht[0]且正在rehash盹舞，則還需要遍歷ht[1]产镐；否則ht[1]為空，不需遍歷
if (dictIsRehashing(iter->d) && iter->table == 0) {
iter->table++;
iter->index = 0;
ht = &iter->d->ht[1];
} else {
break;
}
}
// 開始遍歷新的bucket鏈表踢步，此次返回鏈表的頭節(jié)點(diǎn)
iter->entry = ht->table[iter->index];
} else { // 還在遍歷一個(gè)bucket鏈表
// 將下一節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)
iter->entry = iter->nextEntry;
}
if (iter->entry) {
// 設(shè)置下一節(jié)點(diǎn)
iter->nextEntry = iter->entry->next;
// 返回當(dāng)前節(jié)點(diǎn)
return iter->entry;
}
}
return NULL;
}
8.4 釋放迭代器
void dictReleaseIterator(dictIterator *iter)
{
if (!(iter->index == -1 && iter->table == 0)) { // 如果迭代器使用過
if (iter->safe) // 若為安全模式癣亚，字典迭代器計(jì)數(shù)減1
iter->d->iterators--;
else // 若為非安全模式，檢查迭代期間字典是否變更
assert(iter->fingerprint == dictFingerprint(iter->d));
}
// 釋放迭代器內(nèi)存
zfree(iter);
}
