這一篇文章主要介紹dict的主要操作函數(shù)狸相，代碼詳見redis的代碼src/dict.c源文件掘而，主要涉及dict的創(chuàng)建始赎，查找鄙早，增加撬腾，替換钓试，刪除等基本操作装黑。
dict的創(chuàng)建（dictCreate）
dictCreate為dict的數(shù)據(jù)結(jié)構(gòu)分配空間并為各個(gè)變量賦初值。其中兩個(gè)哈希表ht[0]和ht[1]起始都沒有分配空間弓熏，table指針都賦為NULL
/* Reset a hash table already initialized with ht_init().
* NOTE: This function should only be called by ht_destroy(). */
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
}
/* Create a new hash table */
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;
}
dict的查找（dictFind）
- 1恋谭，dict是否為空
- 2，dict是否在進(jìn)行重哈希硝烂，如果在進(jìn)行箕别，則向前推進(jìn)一步
- 3，計(jì)算key的hash值h
- 4滞谢，先在dict的ht[0]：根據(jù)hash值h和ht[0]的sizemask計(jì)算索引值串稀，根據(jù)索引值獲取dictEntry鏈表的指針，根據(jù)指針在鏈表上查找是否存在為key的entry狮杨，如果有就返回母截，
- 5，第4步如果dict的ht[0]沒有找到橄教，判斷當(dāng)前是否在重哈希清寇，如果沒有返回空喘漏，否則在dict的ht[1]上進(jìn)行同樣的查找步驟
dictEntry *dictFind(dict *d, const void *key)
{
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);
h = dictHashKey(d, key);
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;
}
if (!dictIsRehashing(d)) return NULL;
}
return NULL;
}
dict的添加（dictAdd）
- 1，包含兩個(gè)過程华烟，首先根據(jù)key在dict中找到dictEntry（dictAddRaw）翩迈，然后在這個(gè)entry插入value（dictSetVal）
- 2，尋找entry的過程中盔夜，如果發(fā)現(xiàn)dict在重哈希的過程中负饲，則向前推進(jìn)一步
- 3，獲取entry在dict的索引調(diào)用_dictKeyIndex函數(shù)喂链，如果不在重哈希過程中返十，它只查找ht[0]；否則查找ht[0]和ht[1]椭微，如果dict已經(jīng)存在這個(gè)key洞坑，則會返回-1，進(jìn)而dictAddRaw函數(shù)會返回NULL
- 4蝇率，如果dict在進(jìn)行重哈希迟杂，則插入到dict的ht[1]中，否則插入到ht[0]中
- 5瓢剿，插入過程會插入到entry鏈表的第一個(gè)節(jié)點(diǎn)(新數(shù)據(jù)再次訪問概率比較高)逢慌，used數(shù)目會更新，調(diào)用宏定義函數(shù)dictSetKey在entry中設(shè)置key
- 6间狂，_dictKeyIndex可能觸發(fā)dict內(nèi)存擴(kuò)展（_dictExpandIfNeeded攻泼，它將哈希表長度擴(kuò)展為原來兩倍）
/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key,NULL);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
int index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d)) _dictRehashStep(d);
/* Get the index of the new element, or -1 if
* the element already exists. */
if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -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. */
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
/* Set the hash entry fields. */
dictSetKey(d, entry, key);
return entry;
}
static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
unsigned int idx, table;
dictEntry *he;
if (existing) *existing = NULL;
/* Expand the hash table if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
for (table = 0; table <= 1; table++) {
idx = hash & d->ht[table].sizemask;
/* Search if this slot does not already contain the given key */
he = d->ht[table].table[idx];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key)) {
if (existing) *existing = he;
return -1;
}
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}
dict的刪除（dictDelete）
dictDelete會進(jìn)一步調(diào)用dictGenericDelete函數(shù)，該函數(shù)多了一個(gè)標(biāo)志位nofree鉴象，以區(qū)分是否釋放需要?jiǎng)h除的entry忙菠，這里標(biāo)記為0，代表需要釋放纺弊。
dictUnlink也會調(diào)用dictGenericDelet牛欢，這里nofree的標(biāo)志位設(shè)置為1，此時(shí)不釋放entry淆游，這個(gè)entry會被返回傍睹，為什么如此設(shè)計(jì)呢？如下作者解釋的很清楚：如果需要使用查找到的entry再刪除犹菱，分別調(diào)用
dictFind和dictDelete函數(shù)拾稳，后者也會進(jìn)行一次查找，整個(gè)包含兩次查找過程腊脱，而調(diào)用dictUnlink和dictFreeUnlinkedEntry則只有一次查找過程访得。
- This function is useful when we want to remove something from the hash
- table but want to use its value before actually deleting the entry.
- Without this function the pattern would require two lookups:
- entry = dictFind(...);
- // Do something with entry
- dictDelete(dictionary,entry);
- Thanks to this function it is possible to avoid this, and use
- instead:
- entry = dictUnlink(dictionary,entry);
- // Do something with entry
- dictFreeUnlinkedEntry(entry); // <- This does not need to lookup again.
刪除過程會觸發(fā)推進(jìn)一步重哈希（_dictRehashStep）
如果當(dāng)前不在重哈希過程中，它只在ht[0]中查找要?jiǎng)h除的key陕凹；否則ht[0]和ht[1]它都要查找悍抑。
刪除過程中鳄炉，由于需要釋放entry，會通過Free函數(shù)調(diào)用key和value的析構(gòu)函數(shù)（keyDestructor和valDestructor）搜骡。
int dictDelete(dict *ht, const void *key) {
return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
unsigned int h, idx;
dictEntry *he, *prevHe;
int table;
if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
if (dictIsRehashing(d)) _dictRehashStep(d);
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) {
if (key==he->key || dictCompareKeys(d, key, he->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 he;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return NULL; /* not found */
}
dictEntry *dictUnlink(dict *ht, const void *key) {
return dictGenericDelete(ht,key,1);
}
參考：
http://zhangtielei.com/posts/blog-redis-dict.html
《redis設(shè)計(jì)與實(shí)現(xiàn)》第二版
