Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)dict的作用是什么
本篇文章為大家展示了redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)dict的作用是什么，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。
成都創(chuàng)新互聯(lián)專業(yè)做網(wǎng)站、成都網(wǎng)站制作，集網(wǎng)站策劃、網(wǎng)站設(shè)計(jì)、網(wǎng)站制作于一體，網(wǎng)站seo、網(wǎng)站優(yōu)化、網(wǎng)站營(yíng)銷、軟文平臺(tái)等專業(yè)人才根據(jù)搜索規(guī)律編程設(shè)計(jì)，讓網(wǎng)站在運(yùn)行后，在搜索中有好的表現(xiàn)，專業(yè)設(shè)計(jì)制作為您帶來效益的網(wǎng)站！讓網(wǎng)站建設(shè)為您創(chuàng)造效益。
dict的數(shù)據(jù)結(jié)構(gòu)定義
為了實(shí)現(xiàn)增量式重哈希（incremental rehashing），dict的數(shù)據(jù)結(jié)構(gòu)里包含兩個(gè)哈希表。在重哈希期間，數(shù)據(jù)從第一個(gè)哈希表向第二個(gè)哈希表遷移。
dict的C代碼定義如下（出自Redis源碼dict.h）：
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
unsigned int (*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 {
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int iterators; /* number of iterators currently running */
} dict;為了能更清楚地展示dict的數(shù)據(jù)結(jié)構(gòu)定義，我們用一張結(jié)構(gòu)圖來表示它。如下。
結(jié)合上面的代碼和結(jié)構(gòu)圖，可以很清楚地看出dict的結(jié)構(gòu)。一個(gè)dict由如下若干項(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)來。
兩個(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ù)。這不是我們現(xiàn)在討論的重點(diǎn)，暫時(shí)忽略。
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ù)。
私有數(shù)據(jù)指針（privdata）就是在dictType的某些操作被調(diào)用時(shí)會(huì)傳回給調(diào)用者。
需要詳細(xì)察看的是dictht結(jié)構(gòu)。它定義一個(gè)哈希表的結(jié)構(gòu)，由如下若干項(xiàng)組成：
一個(gè)dictEntry指針數(shù)組（table）。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è)比值越大，哈希值沖突概率越高。
dictEntry結(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ù)。
dict的創(chuàng)建（dictCreate）
dict *dictCreate(dictType *type,
void *privDataPtr)
{
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;
}dictCreate為dict的數(shù)據(jù)結(jié)構(gòu)分配空間并為各個(gè)變量賦初值。其中兩個(gè)哈希表ht[0]和ht[1]起始都沒有分配空間，table指針都賦為NULL。這意味著要等第一個(gè)數(shù)據(jù)插入時(shí)才會(huì)真正分配空間。
dict的查找（dictFind）
#define dictIsRehashing(d) ((d)->rehashidx != -1)
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;
}上述dictFind的源碼，根據(jù)dict當(dāng)前是否正在重哈希，依次做了這么幾件事：
如果當(dāng)前正在進(jìn)行重哈希，那么將重哈希過程向前推進(jìn)一步（即調(diào)用_dictRehashStep）。實(shí)際上，除了查找，插入和刪除也都會(huì)觸發(fā)這一動(dòng)作。這就將重哈希過程分散到各個(gè)查找、插入和刪除操作中去了，而不是集中在某一個(gè)操作中一次性做完。
計(jì)算key的哈希值（調(diào)用dictHashKey，里面的實(shí)現(xiàn)會(huì)調(diào)用前面提到的hashFunction）。
先在第一個(gè)哈希表ht[0]上進(jìn)行查找。在table數(shù)組上定位到哈希值對(duì)應(yīng)的位置（如前所述，通過哈希值與sizemask進(jìn)行按位與），然后在對(duì)應(yīng)的dictEntry鏈表上進(jìn)行查找。查找的時(shí)候需要對(duì)key進(jìn)行比較，這時(shí)候調(diào)用dictCompareKeys，它里面的實(shí)現(xiàn)會(huì)調(diào)用到前面提到的keyCompare。如果找到就返回該項(xiàng)。否則，進(jìn)行下一步。
判斷當(dāng)前是否在重哈希，如果沒有，那么在ht[0]上的查找結(jié)果就是最終結(jié)果（沒找到，返回NULL）。否則，在ht[1]上進(jìn)行查找（過程與上一步相同）。
下面我們有必要看一下增量式重哈希的_dictRehashStep的實(shí)現(xiàn)。
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
}
int dictRehash(dict *d, int n) {
int empty_visits = n*10; /* Max number of empty buckets to visit. */
if (!dictIsRehashing(d)) return 0;
while(n-- && d->ht[0].used != 0) {
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) {
d->rehashidx++;
if (--empty_visits == 0) return 1;
}
de = d->ht[0].table[d->rehashidx];
/* Move all the keys in this bucket from the old to the new hash HT */
while(de) {
unsigned int h;
nextde = de->next;
/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
/* Check if we already rehashed the whole table... */
if (d->ht[0].used == 0) {
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
/* More to rehash... */
return 1;
}dictRehash每次將重哈希至少向前推進(jìn)n步（除非不到n步整個(gè)重哈希就結(jié)束了），每一步都將ht[0]上某一個(gè)bucket（即一個(gè)dictEntry鏈表）上的每一個(gè)dictEntry移動(dòng)到ht[1]上，它在ht[1]上的新位置根據(jù)ht[1]的sizemask進(jìn)行重新計(jì)算。rehashidx記錄了當(dāng)前尚未遷移（有待遷移）的ht[0]的bucket位置。
如果dictRehash被調(diào)用的時(shí)候，rehashidx指向的bucket里一個(gè)dictEntry也沒有，那么它就沒有可遷移的數(shù)據(jù)。這時(shí)它嘗試在ht[0].table數(shù)組中不斷向后遍歷，直到找到下一個(gè)存有數(shù)據(jù)的bucket位置。如果一直找不到，則最多走n*10步，本次重哈希暫告結(jié)束。
最后，如果ht[0]上的數(shù)據(jù)都遷移到ht[1]上了（即d->ht[0].used == 0），那么整個(gè)重哈希結(jié)束，ht[0]變成ht[1]的內(nèi)容，而ht[1]重置為空。
根據(jù)以上對(duì)于重哈希過程的分析，我們?nèi)菀卓闯?，本文前面的dict結(jié)構(gòu)圖中所展示的正是rehashidx=2時(shí)的情況，前面兩個(gè)bucket（ht[0].table[0]和ht[0].table[1]）都已經(jīng)遷移到ht[1]上去了。
dict的插入（dictAdd和dictReplace）
dictAdd插入新的一對(duì)key和value，如果key已經(jīng)存在，則插入失敗。
dictReplace也是插入一對(duì)key和value，不過在key存在的時(shí)候，它會(huì)更新value。
int dictAdd(dict *d, void *key, void *val)
{
dictEntry *entry = dictAddRaw(d,key);
if (!entry) return DICT_ERR;
dictSetVal(d, entry, val);
return DICT_OK;
}
dictEntry *dictAddRaw(dict *d, void *key)
{
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)) == -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 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];
while(he) {
if (key==he->key || dictCompareKeys(d, key, he->key))
return -1;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return idx;
}以上是dictAdd的關(guān)鍵實(shí)現(xiàn)代碼。我們主要需要注意以下幾點(diǎn)：
它也會(huì)觸發(fā)推進(jìn)一步重哈希（_dictRehashStep）。
如果正在重哈希中，它會(huì)把數(shù)據(jù)插入到ht[1]；否則插入到ht[0]。
在對(duì)應(yīng)的bucket中插入數(shù)據(jù)的時(shí)候，總是插入到dictEntry的頭部。因?yàn)樾聰?shù)據(jù)接下來被訪問的概率可能比較高，這樣再次查找它時(shí)就比較次數(shù)較少。
_dictKeyIndex在dict中尋找插入位置。如果不在重哈希過程中，它只查找ht[0]；否則查找ht[0]和ht[1]。
_dictKeyIndex可能觸發(fā)dict內(nèi)存擴(kuò)展（_dictExpandIfNeeded，它將哈希表長(zhǎng)度擴(kuò)展為原來兩倍，具體請(qǐng)參考dict.c中源碼）。
dictReplace在dictAdd基礎(chǔ)上實(shí)現(xiàn)，如下：
int dictReplace(dict *d, void *key, void *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)
return 1;
/* It already exists, get the entry */
entry = dictFind(d, 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;
dictSetVal(d, entry, val);
dictFreeVal(d, &auxentry);
return 0;
}在key已經(jīng)存在的情況下，dictReplace會(huì)同時(shí)調(diào)用dictAdd和dictFind，這其實(shí)相當(dāng)于兩次查找過程。這里Redis的代碼不夠優(yōu)化。
dict的刪除（dictDelete）
dictDelete的源碼這里忽略，具體請(qǐng)參考dict.c。需要稍加注意的是：
dictDelete也會(huì)觸發(fā)推進(jìn)一步重哈希（_dictRehashStep）
如果當(dāng)前不在重哈希過程中，它只在ht[0]中查找要?jiǎng)h除的key；否則ht[0]和ht[1]它都要查找。
刪除成功后會(huì)調(diào)用key和value的析構(gòu)函數(shù)（keyDestructor和valDestructor）。
上述內(nèi)容就是Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)dict的作用是什么，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
當(dāng)前題目：Redis中內(nèi)部數(shù)據(jù)結(jié)構(gòu)dict的作用是什么
網(wǎng)頁(yè)地址：http://bm7419.com/article38/pcegsp.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供Google、云服務(wù)器、服務(wù)器托管、網(wǎng)站收錄、搜索引擎優(yōu)化、外貿(mào)建站
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)
- 企業(yè)站選擇什么樣的虛擬主機(jī)更合適？ 2022-05-30
- 虛擬主機(jī)如何設(shè)置404頁(yè)面 2014-10-21
- 虛擬主機(jī)易被忽視的實(shí)用功能 2022-07-17
- 虛擬主機(jī)和云服務(wù)器怎么選 2021-02-04
- 哪些類型的網(wǎng)站不適合使用虛擬主機(jī)？ 2021-03-04
- 網(wǎng)站建設(shè)時(shí)虛擬主機(jī)和服務(wù)器應(yīng)該如何選擇？ 2016-11-07
- 獨(dú)立IP虛擬主機(jī)對(duì)網(wǎng)站的優(yōu)勢(shì) 2022-06-13
- 做網(wǎng)站需要智能雙線虛擬主機(jī) 2021-07-04
- 怎么選擇好的便宜云虛擬主機(jī)？分享挑選便宜云虛擬主機(jī)的小技巧 2022-10-07
- 網(wǎng)站優(yōu)化之怎樣選擇虛擬主機(jī) 2016-08-06
- 云主機(jī)？虛擬主機(jī)？傻傻分不清 2021-02-14
- 你的網(wǎng)站適合虛擬主機(jī)嗎？ 2022-08-01