最近工作有點忙，拖了好久才擠出時間學習dict源碼。還是希望能堅持讀下去。
先簡單介紹一下redis字典
字典的目的是為了通過某個信息(key) 找到另一個信息(value)。為了快速從key找到value，字典通常會用hash表作為底層的存儲，redis的字典也不例外，它的實現(xiàn)是基于時間復雜度為O(1)的hash算法（關(guān)于hash表的介紹可以參考《算法導論》"散列表"一章）
redis中字典的主要用途有以下兩個：
1.實現(xiàn)數(shù)據(jù)庫鍵空間（key space）；
2.用作 Hash 類型鍵的底層實現(xiàn)之一；
第一種情況：因為redis是基于key-val的存儲系統(tǒng)，整個db的鍵空間就是一個大字典，這個字典里放了許多key-val對，不論value是String、List、Hash、Set、Zset中的哪種類型，redis都會根據(jù)每個key生成一個字典的索引。
第二種情況：若value的類型是Redis中的Hash，在Hash數(shù)據(jù)量較大的情況下 redis會將Hash中的每個field也當作key生成一個字典(出于性能考慮，Hash數(shù)據(jù)量小的時候redis會使用壓縮列表ziplist來存Hash的filed)，最終 Hash的key是一個字典的索引，key中的所有field又分別是另一個字典的索引。
redis中dict的定義
上圖的結(jié)構(gòu)是dict.h文件的整個藍圖
首先從上圖能看出 redis解決hash沖突的方法用的是鏈地址法，將沖突的鍵值對按照一個單向鏈表來存儲，每個底層的key-val節(jié)點都是一個鏈表節(jié)點。
dictEntry
看看單個key-val節(jié)點結(jié)構(gòu)聲明的代碼：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;//下一個節(jié)點的地址
} dictEntry;
沒什么可說的，就是一個鏈表節(jié)點的聲明，節(jié)點里存了key、value以及下一個節(jié)點的指針(下文直接用"dictEntry"指代"key-val節(jié)點")。因為value有多種類型，所以value用了union來存儲，c語言的union總結(jié)起來就是兩句話: In union, all members share the same memory location...Size of a union is taken according the size of largest member in union.(union的所有成員共享同一塊內(nèi)存，union的size取決于它的最大的成員的size)
dictht
通常實現(xiàn)一個hash表時會使用一個buckets存放dictEntry的地址，將key代入hash函數(shù)得到的值就是buckets的索引，這個值決定了我們要將此dictEntry節(jié)點放入buckets的哪個索引里。這個buckets實際上就是我們說的hash表。
這個buckets存儲在哪里呢？
dict.h的dictht結(jié)構(gòu)中table存放的就是buckets的地址。以下是dictht的聲明：
typedef struct dictht {
dictEntry **table;//buckets的地址
unsigned long size;//buckets的大小,總保持為 2^n
unsigned long sizemask;//掩碼，用來計算hash值對應的buckets索引
unsigned long used;//當前dictht有多少個dictEntry節(jié)點
} dictht;
成員變量used：要注意 used跟size沒有任何關(guān)系，這是當前dictht包含多少個dictEntry節(jié)點的意思,漸進rehash(下文會詳細介紹rehash)時會用這個成員判斷是否已經(jīng)rehash完成，而size是buckets的大小。
成員變量sizemask：key通過hash函數(shù)得到的hash值 跟 sizemask 作"與運算"，得到的值就是這個key需要放入的buckets的索引：
h = dictHashKey(d, de->key) & d->ht[0].sizemask
d->ht[0].table[h]就是這個dictEntry該放入的地方。這應該也是bucekts大小總保持2^n的原因，方便通過hash值與sizemask得到索引。
dict
上面說了，dictht實際上就是hash表的核心，但是只有一個dictht很多事情還做不了，所以redis定義了一個叫dict的結(jié)構(gòu)以支持字典的各種操作，如rehash和遍歷hash等。
typedef struct dict {
dictType *type;//dictType里存放的是一堆工具函數(shù)的函數(shù)指針，
void *privdata;//保存type中的某些函數(shù)需要作為參數(shù)的數(shù)據(jù)
dictht ht[2];//兩個dictht，ht[0]平時用，ht[1] rehash時用
long rehashidx; /* rehashing not in progress if rehashidx == -1 *///當前rehash到buckets的哪個索引，-1時表示非rehash狀態(tài)
int iterators; /* number of iterators currently running *///安全迭代器的計數(shù)。
} dict;
迭代器的定義先不管，等下文講到安全非安全迭代器的時候再細說。
hash算法
redis內(nèi)置3種hash算法
- dictIntHashFunction，對正整數(shù)進行hash
- dictGenHashFunction，對字符串進行hash
- dictGenCaseHashFunction，對字符串進行hash，不區(qū)分大小寫
這些hash函數(shù)沒什么好說的，有興趣google一下就好。
在講redis字典基本操作之前，有必要介紹一下rehash，因為dict的增刪改查(CRUD)都會執(zhí)行被動rehash。
rehash
什么是rehash
當字典的dictEntry節(jié)點擴展到一定規(guī)模時，hash沖突的鏈表會越來越長，使原本O(1)的hash運算轉(zhuǎn)換成了O(n)的鏈表遍歷，從而導致字典的增刪改查(CRUD)越來越低效，這個時候redis會利用dict結(jié)構(gòu)中的dictht[1]擴充一個新的buckets(調(diào)用dictExpand)，然后慢慢將dictht[0]的節(jié)點遷移至dictht[1]、用dictht[1]替換掉dictht[0] (調(diào)用dictRehash)。
具體擴充過程如下：
- 1.調(diào)用dictAdd為dict添加一個dictEntry節(jié)點。
- 2.調(diào)用_dictKeyIndex找到應該放置在buckets的哪個索引里。順便調(diào)用_dictExpandIfNeeded判斷是否需要擴充 dictht[1]。
- 3.若滿足條件：dictht[0]的dictEntry節(jié)點數(shù)/buckets的索引數(shù)>=1則調(diào)用dictExpand，若dictEntry節(jié)點數(shù)/buckets的索引數(shù)>=dict_force_resize_ratio(默認是5)，則強制執(zhí)行dictExpand擴充dictht[1]。
需要注意的是上面的條件不是rehash的條件，而是擴充dictht[1]并打開dict rehash開關(guān)的條件。(因為rehash不是一次性完成的，若dictEntry節(jié)點非常多，rehash過程會進行很久從而block其他操作。所以redis采用了漸進rehash，分步進行，下文講rehash方式時會詳細介紹)。dictExpand做的只是把dictht[1]的buckets擴充到合適的大小，再把dict的rehashidx從-1置為0(打開rehash開關(guān))。打開rehash開關(guān)之后該dict每次增刪改查(CRUD)都會執(zhí)行一次rehash，把dictht[0]的buckets中的一個索引里的鏈表移動到dictht[1]。rehash的條件是rehashidx是否為-1。
放源碼:
static int dict_can_resize = 1;
static unsigned int dict_force_resize_ratio = 5;
//判斷dictht[1]是否需要擴充(并將dict調(diào)整為正在rehash狀態(tài))；若dict剛創(chuàng)建，則擴充dictht[0]
static int _dictExpandIfNeeded(dict *d)
{
/* Incremental rehashing already in progress. Return. */
if (dictIsRehashing(d)) return DICT_OK;
/* If the hash table is empty expand it to the initial size. */
//這是為剛創(chuàng)建的dict準備的，d->ht[0].size == 0時調(diào)用dictExpand只會擴充dictht[0]，不會改變dict的rehash狀態(tài)
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
/* If we reached the 1:1 ratio, and we are allowed to resize the hash
* table (global setting) or we should avoid it but the ratio between
* elements/buckets is over the "safe" threshold, we resize doubling
* the number of buckets. */
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
//1:1時如果全局變量dict_can_resize為1則expand，
//或者節(jié)點數(shù)/bucket數(shù)超過dict_force_resize_ratio(5)則擴充
return dictExpand(d, d->ht[0].used*2);buckets大小擴充至 dict已使用節(jié)點的2倍的下一個2^n。假如used=4，buckets會擴充到8；used=5，buckets會擴充到16
}
return DICT_OK;
}
/* Expand or create the hash table */
//三個功能:
//1.為剛初始化的dict的dictht[0]分配table(buckets)
//2.為已經(jīng)達到rehash要求的dict的dictht[1]分配一個更大(下一個2^n)的table(buckets),并將rehashidx置為0
//3.為需要縮小bucket的dict分配一個更小的buckets，并將rehashidx置為0(打開rehash開關(guān))
int dictExpand(dict *d, unsigned long size)
{
dictht n; /* the new hash table *///最終會賦值給d->ht[0]和d->ht[1]，所以不用new一個dictht
unsigned long realsize = _dictNextPower(size);//從4開始找大于等于size的最小2^n作為新的slot數(shù)量
/* the size is invalid if it is smaller than the number of
* elements already inside the hash table */
if (dictIsRehashing(d) || d->ht[0].used > size)//如果當前使用的bucket數(shù)目大于想擴充之后的size
return DICT_ERR;
/* Rehashing to the same table size is not useful. */
if (realsize == d->ht[0].size) return DICT_ERR;
/* Allocate the new hash table and initialize all pointers to NULL */
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
/* Is this the first initialization? If so it's not really a rehashing
* we just set the first hash table so that it can accept keys. */
if (d->ht[0].table == NULL) {//剛創(chuàng)建的dict
d->ht[0] = n;//為d->ht[0]賦值
return DICT_OK;
}
/* Prepare a second hash table for incremental rehashing */
d->ht[1] = n;
d->rehashidx = 0;//設(shè)置rehash狀態(tài)為正在進行rehash
return DICT_OK;
}
畫圖分析一下擴充流程:
假設(shè)一個dict已經(jīng)有4個dictEntry節(jié)點(value分別為"a","b","c","d")，根據(jù)key的不同，存放在buckets的不同索引下。
現(xiàn)在如果我們想添加一個dictEntry，由于d->ht[0].used >= d->ht[0].size (4>=4)，滿足了擴充dictht[1]的條件，會執(zhí)行dictExpand。根據(jù)擴充規(guī)則，dictht[1]的buckets會擴充到8個槽位。
之后再將要添加的dictEntry加入到dictht[1]的buckets中的某個索引下，不過這個操作不屬于dictExpand，不展開了。
擴充之后的dict的成員變量rehashidx被賦值為0，此后每次CRUD都會執(zhí)行一次被動rehash把dictht[0]的buckets中的一個鏈表遷移到dictht[1]中，直到遷移完畢。
rehash的方式
剛才提到了被動rehash，實際上dict的rehash分為兩種方式:
- 主動方式：調(diào)用dictRehashMilliseconds執(zhí)行一毫秒。在redis的serverCron里調(diào)用，看名字就知道是為redis服務端準備的定時事件，每次執(zhí)行1ms的dictRehash，簡單粗暴。。
- 被動方式：字典的增刪改查(CRUD)調(diào)用dictAdd，dicFind，dictDelete，dictGetRandomKey等函數(shù)時，會調(diào)用_dictRehashStep，遷移buckets中的一個非空bucket。
放上源碼:
int dictRehashMilliseconds(dict *d, int ms) {
long long start = timeInMilliseconds();
int rehashes = 0;
while(dictRehash(d,100)) {//每次最多執(zhí)行buckets的100個鏈表rehash
rehashes += 100;
if (timeInMilliseconds()-start > ms) break;//最多執(zhí)行ms毫秒
}
return rehashes;
}
static void _dictRehashStep(dict *d) {//只rehash一個bucket
//沒有安全迭代器綁定在當前dict上時才能rehash，下文講"安全迭代器"時會細說，這里只需要知道這是rehash buckets的1個鏈表
if (d->iterators == 0) dictRehash(d,1);
}
上面可以看出，不論是哪種rehash方式，底層都是通過dictRehash實現(xiàn)的，它是字典rehash的核心代碼。
dictRehash
dictRehash有兩個參數(shù)，d是rehash的dict指針，n是需要遷移到dictht[1]的非空桶數(shù)目；返回值0表示rehash完畢，否則返回1。
int dictRehash(dict *d, int n) {//rehash n個bucket到ht[1]，或者掃了n*10次空bucket就退出
int empty_visits = n*10; /* Max number of empty buckets to visit. *///最多只走empty_visits個空bucket，一旦遍歷的空bucket數(shù)超過這個數(shù)則返回1，所以可能執(zhí)行這個函數(shù)的時候一個bucket也沒有rehash到ht[1]
if (!dictIsRehashing(d)) return 0;//rehash已完成
while(n-- && d->ht[0].used != 0) {//遍歷n個bucket,ht[0]中還有dictEntry
dictEntry *de, *nextde;
/* Note that rehashidx can't overflow as we are sure there are more
* elements because ht[0].used != 0 */
assert(d->ht[0].size > (unsigned long)d->rehashidx);
while(d->ht[0].table[d->rehashidx] == NULL) {
//當前bucket為空時跳到下一個bucket并且
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
//直到當前bucket不為空bucket時
de = d->ht[0].table[d->rehashidx];//當前bucket里第一個dictEntry的指針(地址)
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {//把當前bucket的所有ditcEntry節(jié)點都移到ht[1]
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;//hash函數(shù)算出的值& 新hashtable(buckets)的sizemask,保證h會小于新buckets的size
de->next = d->ht[1].table[h];//插入到鏈表的最前面！省時間
d->ht[1].table[h] = de;
d->ht[0].used--;//老dictht的used(節(jié)點數(shù))-1
d->ht[1].used++;//新dictht的used(節(jié)點數(shù))+1
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;//當前bucket已經(jīng)完全移走
d->rehashidx++;//下一個bucket
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);//釋放掉ht[0].table的內(nèi)存(buckets)
d->ht[0] = d->ht[1];//淺復制，table只是一個地址，直接給ht[0]就好
_dictReset(&d->ht[1]);//ht[1]的table置空
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}
拿上面的圖作為的例子調(diào)用一次dictRehash(d, 1)，會產(chǎn)生如下布局:
- 之前a和b的放在dictht[0]的同一個buckets索引[0]下，但是經(jīng)過rehash，h = dictHashKey(d, de->key) & d->ht[1].sizemask，h可能依舊為0，也有可能變?yōu)?。ps:如果兩個dictEntry仍然落在同一個索引下，它倆順序會顛倒。
- rehashidx+1
- 返回1 More to rehash
若在此基礎(chǔ)上在執(zhí)行一次dictRehash(d, 1)，則會跳過索引為1的那個空bucket，遷移下一個bucket。
字典的基本操作
dictCreate:創(chuàng)建一個dict
有了rehash的基本認識，下面就可以說說redis字典支持的一些常規(guī)操作了：
redis用dictCreate創(chuàng)建并初始化一個dict，放源碼一看就明白：
dict *dictCreate(dictType *type,
void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
/* Initialize the hash table */
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;
}
需要注意的是創(chuàng)建初始化一個dict時并沒有為buckets分配空間，table是賦值為null的。只有在往dict里添加dictEntry節(jié)點時才會為buckets分配空間，真正意義上創(chuàng)建一張hash表。
執(zhí)行dictCreate后會得到如下布局：
dictAdd(增):添加一個dictEntry節(jié)點
int dictAdd(dict *d, void *key, void *val)//完整的添加dictEntry節(jié)點的流程
{
dictEntry *entry = dictAddRaw(d,key);//只在buckets的某個索引里新建一個dictEntry并調(diào)整鏈表的位置,只設(shè)置key，不設(shè)置不設(shè)置val
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);//為這個entry設(shè)置值
return DICT_OK;
}
//_dictKeyIndex會判斷是否達到expand條件,若達到條件則執(zhí)行dictExpand將dictht[1]擴大 并將改dict的rehash狀態(tài)置為正在進行中(-1置為0)
dictEntry *dictAddRaw(dict *d, void *key)//new一個dictEntry然后把它放到某個buckets索引下的鏈表頭部，填上key
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);//如果正在rehash則被動rehash一步
/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(d, key)) == -1)//計算這個key在當前dict應該放到bucket的哪個索引里,key已存在則返回-1
return NULL;
/* Allocate the memory and store the new entry.
* Insert the element in top, with the assumption that in a database
* system it is more likely that recently added entries are accessed
* more frequently. */
//雖然_dictKeyIndex()時已經(jīng)確認過是哪張dictht,但是調(diào)用者沒辦法知道，所以再確認一下
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];//在rehash則把dictEntry加到ht[1]
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);//如果dict d沒有keyDup則直接entry->key = xxx,賦值
return entry;
}
static int _dictKeyIndex(dict *d, const void *key)//根據(jù)dict和key返回這個key該存放的buckets的索引（但是用哪個dictht(ht[0]或ht[1])上層調(diào)用者是未知的）,key已存在則返回-1
{
unsigned int h, idx, table;
dictEntry *he;
/* Expand the hash table if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
/* Compute the key hash value */
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];//buckets 的idx索引下的第一個dictEntry的地址
while(he) {//遍歷一遍這個dictEntry鏈表
if (key==he->key || dictCompareKeys(d, key, he->key))//如果key已經(jīng)存在,返回-1
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break;//不在rehash時，直接跳出循環(huán)不做第二個dictht[1]的計算
}
return idx;
}
主要分為以下幾個步驟:
- 1.根據(jù)key的hash值找到應該存放的位置(buckets索引)。
- 2.若dict是剛創(chuàng)建的還沒有為bucekts分配內(nèi)存，則會在找位置(_dictKeyIndex)時調(diào)用_dictExpandIfNeeded，為dictht[0]expand一個大小為4的buckets；若dict正好到了expand的時機，則會expand它的dictht[1]，并將rehashidx置為0打開rehash開關(guān)，_dictKeyIndex返回的會是dictht[1]的索引。
- 3.申請一個dictEntry大小的內(nèi)存插入到buckets對應索引下的鏈表頭部，并給dictEntry設(shè)置next指針和key。
- 4.為dictEntry設(shè)置value
dictDelete(刪):刪除一個dictEntry節(jié)點
dict刪除函數(shù)主要有三個，從低到高依次刪除dictEntry、dictht、dict。
- dictDelete在redis在字典里的作用是刪除一個dictEntry并釋放dictEntry成員key和成員v指向的內(nèi)存；
- _dictClear刪除并釋放一個dict的指定dictht；
- dictRelease刪除并釋放整個dict。
//刪除dictEntry并釋放dictEntry成員key和成員v指向的內(nèi)存
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0);
}
static int dictGenericDelete(dict *d, const void *key, int nofree)//刪除一個dictEntry節(jié)點，nofree參數(shù)指定是否釋放這個節(jié)點的key和val的內(nèi)存(如果key和val是指針的話),nofree為1不釋放，0為釋放
{
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
if (dictIsRehashing(d)) _dictRehashStep(d);//被動rehash一次
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;//找到key對應的bucket索引
he = d->ht[table].table[idx];//索引的第一個dictEntry節(jié)點指針
prevHe = NULL;
while(he) {
//單向鏈表刪除步驟
if (key==he->key || dictCompareKeys(d, key, he->key)) {//key匹配
/* Unlink the element from the list */
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (!nofree) {
dictFreeKey(d, he);
dictFreeVal(d, he);
}
zfree(he);
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;//如果不在rehash，則不查第二個table(dictht[1])
}
return DICT_ERR; /* not found */
}
//刪除一個dict的指定dictht，釋放dictht的table內(nèi)相關(guān)的全部內(nèi)存，并reset dictht
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {//傳遞dict指針是為了調(diào)用dictType的相關(guān)函數(shù),dictFreeVal里會調(diào)
unsigned long i;
/* Free all the elements */
for (i = 0; i < ht->size && ht->used > 0; i++) {//buckets大小，dictEntry使用數(shù)
dictEntry *he, *nextHe;
if (callback && (i & 65535) == 0) callback(d->privdata);
if ((he = ht->table[i]) == NULL) continue;
while(he) {
//遍歷刪除dictEntry鏈表
nextHe = he->next;
dictFreeKey(d, he);
dictFreeVal(d, he);
zfree(he);
ht->used--;
he = nextHe;
}
}
/* Free the table and the allocated cache structure */
zfree(ht->table);
/* Re-initialize the table */
_dictReset(ht);
return DICT_OK; /* never fails */
}
//刪除并釋放整個dict
void dictRelease(dict *d)
{
_dictClear(d,&d->ht[0],NULL);
_dictClear(d,&d->ht[1],NULL);
zfree(d);
}
dictReplace(改):修改一個dictEntry節(jié)點的成員v(值)
//修改一個dictEntry的val，也是一種添加dictEntry的方式，如果dictAdd失敗(key已存在)則replace這個dictEntry的val
int dictReplace(dict *d, void *key, void *val)//用新val取代一個dictEntry節(jié)點的舊val
{
dictEntry *entry, auxentry;
/* Try to add the element. If the key
* does not exists dictAdd will suceed. */
if (dictAdd(d, key, val) == DICT_OK)//試著加一個新dictEntry，失敗則說明key已存在
return 1;
/* It already exists, get the entry */
entry = dictFind(d, key);//創(chuàng)建節(jié)點失敗則一定能找到這個已經(jīng)存在了的key
/* Set the new value and free the old one. Note that it is important
* to do that in this order, as the value may just be exactly the same
* as the previous one. In this context, think to reference counting,
* you want to increment (set), and then decrement (free), and not the
* reverse. */
auxentry = *entry;//需要替換val的dictEntry節(jié)點,auxentry用來刪除(釋放)val
dictSetVal(d, entry, val);//替換val的操作
dictFreeVal(d, &auxentry);//考慮val可能是一個指針，指針指向的內(nèi)容不會被刪除，所以調(diào)用這個dict的type類里的dictFreeVal釋放掉那塊內(nèi)存
return 0;
}
代碼里還有一個dictReplaceRaw函數(shù)，這個函數(shù)跟replace沒啥關(guān)系，只是封裝了一下dictAddRaw，沒有替換的功能。
dictFind(查):根據(jù)key找到當前dict存放該key的dictEntry
//返回dictEntry的地址
dictEntry *dictFind(dict *d, const void *key)//會執(zhí)行被動rehash
{
dictEntry *he;
unsigned int h, idx, table;
if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
if (dictIsRehashing(d)) _dictRehashStep(d);//查找key的時候也會被動rehash
h = dictHashKey(d, key);
for (table = 0; table <= 1; table++) {
idx = h & d->ht[table].sizemask;//先計算當前buckets中key應存放的索引
he = d->ht[table].table[idx];//buckets 的idx索引下的第一個dictEntry的地
while(he) {//遍歷查找該鏈表
if (key==he->key || dictCompareKeys(d, key, he->key))//如果key已經(jīng)存在,返回-1
return he;
he = he->next;
}
if (!dictIsRehashing(d)) return NULL;//不在rehash時，直接跳出循環(huán)不在dictht[1]里查找
}
return NULL;
}
安全 非安全迭代器
介紹一下字典的迭代器
redis字典的迭代器分為兩種，一種是safe迭代器另一種是unsafe迭代器:
safe迭代器在迭代的過程中用戶可以對該dict進行CURD操作，unsafe迭代器在迭代過程中用戶只能對該dict執(zhí)行迭代操作。
- 上文說過每次執(zhí)行CURD操作時，如果dict的rehash開關(guān)已經(jīng)打開，則會執(zhí)行一次被動rehash操作將dictht[0]的一個鏈表遷移到dictht[1]上。這時若迭代器進行迭代操作會導致重復迭代幾個剛被rehash到dictht[1]的dictEntry節(jié)點。那么一邊迭代一遍CRUD，這是怎么實現(xiàn)的呢？
redis在dict結(jié)構(gòu)里增加一個iterator成員，用來表示綁定在當前dict上的safe迭代器數(shù)量，dict每次CRUD執(zhí)行_dictRehashStep時判斷一下是否有綁定safe迭代器，如果有則不進行rehash以免擾亂迭代器的迭代，這樣safe迭代時字典就可以正常進行CRUD操作了。
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}
- unsafe迭代器在執(zhí)行迭代過程中不允許對dict進行其他操作，如何保證這一點呢？
redis在第一次執(zhí)行迭代時會用dictht[0]、dictht[1]的used、size、buckets地址計算一個fingerprint(指紋)，在迭代結(jié)束后釋放迭代器時再計算一遍fingerprint看看是否與第一次計算的一致，若不一致則用斷言終止進程，生成指紋的函數(shù)如下:
//unsafe迭代器在第一次dictNext時用dict的兩個dictht的table、size、used進行hash算出一個結(jié)果
//最后釋放iterator時再調(diào)用這個函數(shù)生成指紋，看看結(jié)果是否一致，不一致就報錯.
//safe迭代器不會用到這個
long long dictFingerprint(dict *d) {
long long integers[6], hash = 0;
int j;
integers[0] = (long) d->ht[0].table;//把指針類型轉(zhuǎn)換成long
integers[1] = d->ht[0].size;
integers[2] = d->ht[0].used;
integers[3] = (long) d->ht[1].table;
integers[4] = d->ht[1].size;
integers[5] = d->ht[1].used;
/* We hash N integers by summing every successive integer with the integer
* hashing of the previous sum. Basically:
*
* Result = hash(hash(hash(int1)+int2)+int3) ...
*
* This way the same set of integers in a different order will (likely) hash
* to a different number. */
for (j = 0; j < 6; j++) {
hash += integers[j];
/* For the hashing step we use Tomas Wang's 64 bit integer hash. */
hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
hash = hash ^ (hash >> 24);
hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
hash = hash ^ (hash >> 14);
hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
hash = hash ^ (hash >> 28);
hash = hash + (hash << 31);
}
return hash;
}
介紹完redis迭代器的兩種類型，看看dictIterator的定義:
dictIterator定義
typedef struct dictIterator {
dict *d;
long index;//當前buckets索引，buckets索引類型是unsinged long，而這個初始化會是-1,所以long
int table, safe;//table是ht的索引只有0和1，safe是安全迭代器和不安全迭代器
//安全迭代器就等于加了一個鎖在dict，使dict在CRUD時ditcEntry不能被動rehash
dictEntry *entry, *nextEntry;//當前hash節(jié)點以及下一個hash節(jié)點
/* unsafe iterator fingerprint for misuse detection. */
long long fingerprint;//dict.c里的dictFingerprint(),不安全迭代器相關(guān)
} dictIterator;
接下來介紹迭代器相關(guān)函數(shù)
dictGetIterator:創(chuàng)建一個迭代器
//默認是new一個unsafe迭代器
dictIterator *dictGetIterator(dict *d)//獲取一個iterator就是為這個dict new一個迭代器
{
//不設(shè)置成員變量fingerprint，在dictNext的時候才設(shè)置。
dictIterator *iter = zmalloc(sizeof(*iter));
iter->d = d;
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;
}
為指定dict創(chuàng)建一個unsafe迭代器：dictGetIterator()
為指定dict創(chuàng)建一個safe迭代器：dictGetSafeIterator()
需要注意的是創(chuàng)建safe迭代器時并不會改變dict結(jié)構(gòu)里iterator成員變量的計數(shù)，只有迭代真正發(fā)生的時候才會+1 表明該dict綁定了一個safe迭代器。
dictNext:迭代一個dictEntry節(jié)點
dictEntry *dictNext(dictIterator *iter)//如果下一個dictEntry不為空，則返回。為空則繼續(xù)找下一個bucket的第一個dictEntry
{
while (1) {
if (iter->entry == NULL) {//新new的dictIterator的entry是null，或者到達一個bucket的鏈表尾部
dictht *ht = &iter->d->ht[iter->table];//dictht的地址
if (iter->index == -1 && iter->table == 0) {
//剛new的dictIterator
if (iter->safe)
iter->d->iterators++;
else
iter->fingerprint = dictFingerprint(iter->d);//初始化unsafe迭代器的指紋，只進行一次
}
iter->index++;//buckets的下一個索引
if (iter->index >= (long) ht->size) {
//如果buckets的索引大于等于這個buckets的大小，則這個buckets迭代完畢
if (dictIsRehashing(iter->d) && iter->table == 0) {//當前用的dictht[0]
//考慮rehash，換第二個dictht
iter->table++;
iter->index = 0;//index復原成0，從第二個dictht的第0個bucket迭代
ht = &iter->d->ht[1];//設(shè)置這個是為了rehash時更新下面的iter->entry
} else {
break;//迭代完畢了
}
}
iter->entry = ht->table[iter->index];//更新entry為下一個bucket的第一個節(jié)點
} else {
iter->entry = iter->nextEntry;
}
if (iter->entry) {
/* We need to save the 'next' here, the iterator user
* may delete the entry we are returning. */
iter->nextEntry = iter->entry->next;
return iter->entry;
}
}
return NULL;
}
雖然safe迭代器會禁止rehash，但在迭代時有可能已經(jīng)rehash了一部分，所以迭代器也會遍歷在dictht[1]中的所有dictEntry。
dictScan
前面說的safe迭代器和unsafe迭代器都是建立在不能rehash的前提下。要通過這種迭代的方式遍歷所有節(jié)點會停止該dict的被動rehash，阻止了rehash的正常進行。dictScan就是用來解決這種問題的，它可以在不停止rehash的前提下遍歷到所有dictEntry節(jié)點，不過也有非常小的可能性返回重復的節(jié)點，具體如何做到的可能得另花大量篇幅介紹，有興趣可以借助這篇博客理解。
