建站
咨詢
售后
建站咨詢
新聞中心
鉆研Redis源碼，掌握DICT結(jié)構(gòu)
在驛城等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作按需規(guī)劃網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),營(yíng)銷型網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站建設(shè),驛城網(wǎng)站建設(shè)費(fèi)用合理。
Redis作為一種高性能的KEY-value存儲(chǔ)系統(tǒng)，被廣泛應(yīng)用于數(shù)據(jù)緩存、消息隊(duì)列等場(chǎng)景。其核心數(shù)據(jù)結(jié)構(gòu)包括String、List、Set、ZSet和Hash等類型，在Redis的代碼實(shí)現(xiàn)中，很多數(shù)據(jù)結(jié)構(gòu)采用C語(yǔ)言實(shí)現(xiàn)。其中，Dict結(jié)構(gòu)作為Redis中常用的哈希表，被廣泛使用。本文將介紹Dict的結(jié)構(gòu)、原理和實(shí)現(xiàn)，并且詳細(xì)探討Dict的部分源碼，希望對(duì)讀者了解Redis的數(shù)據(jù)結(jié)構(gòu)有所幫助。
1. Dict結(jié)構(gòu)
在源碼中，Dict結(jié)構(gòu)被定義在dict.h文件中。Dict是一個(gè)哈希表的結(jié)構(gòu)體，包含以下幾個(gè)成員：
“`c
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictType {
uint64_t (*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;
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;
unsigned long iterators;
} dict;
其中，dictEntry結(jié)構(gòu)體表示哈希表中的一個(gè)鍵值對(duì)，包含鍵、值、指向下一個(gè)dictEntry的指針等成員；dictType結(jié)構(gòu)體用于定義字典操作的相關(guān)函數(shù)，比如哈希函數(shù)、鍵值復(fù)制函數(shù)和鍵值比較函數(shù)等；dictht結(jié)構(gòu)體則是哈希表的關(guān)鍵結(jié)構(gòu)體，包含哈希桶指針數(shù)組、桶大小、桶數(shù)量等成員；而dict則包含dictType、dictht等成員，用于表示一個(gè)完整的字典結(jié)構(gòu)。
2. 原理
Dict通過(guò)哈希表實(shí)現(xiàn)快速查找鍵值對(duì)。哈希表是一種用于實(shí)現(xiàn)關(guān)聯(lián)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，其基本思路是將鍵通過(guò)哈希函數(shù)轉(zhuǎn)換成索引，存放在哈希桶中，從而實(shí)現(xiàn)快速的查找和插入。Dict中的哈希桶使用指針數(shù)組來(lái)存儲(chǔ)，每個(gè)哈希桶元素對(duì)應(yīng)一個(gè)dictEntry結(jié)構(gòu)體。當(dāng)插入或查找鍵值對(duì)時(shí)，先通過(guò)哈希函數(shù)計(jì)算出對(duì)應(yīng)的哈希值，并將其映射到哈希桶上，找到對(duì)應(yīng)的桶元素指針，然后在桶中查找或插入dictEntry。
為了解決哈希沖突的問(wèn)題，Dict中使用了拉鏈法作為哈希桶的沖突解決方法。當(dāng)多個(gè)鍵值對(duì)的哈希值相同時(shí)，將這些鍵值對(duì)通過(guò)一個(gè)鏈表連接在一起，從而解決了哈希沖突問(wèn)題。
3. 實(shí)現(xiàn)
Dict的源碼實(shí)現(xiàn)分為幾個(gè)部分，包括初始化、添加、刪除、查找、哈希沖突處理等。下面我們通過(guò)具體的代碼實(shí)例來(lái)詳細(xì)介紹Dict的源碼實(shí)現(xiàn)。
初始化
Dict的初始化主要是對(duì)哈希桶進(jìn)行初始化，同時(shí)設(shè)置字典類型和哈希擴(kuò)展因子等信息。下面是Dict初始化代碼的實(shí)現(xiàn)：
```c
// 初始化一個(gè)新的字典
dict *dictCreate(dictType *type, void *privDataPtr)
{
dict *d = zmalloc(sizeof(*d));
_dictInit(d,type,privDataPtr);
return d;
}
// 配置字典信息
void _dictInit(dict *d, dictType *type, void *privdata)
{
// 對(duì)兩張哈希表分別進(jìn)行初始化操作
_dictReset(&d->ht[0]);
_dictReset(&d->ht[1]);
// 設(shè)置字典類型信息
d->type = type;
// 設(shè)置字典類型私有數(shù)據(jù)
d->privdata = privdata;
d->rehashidx = -1;
d->iterators = 0;
}
添加
Dict的添加操作主要是對(duì)鍵值對(duì)進(jìn)行哈希計(jì)算，并將該鍵值對(duì)插入到對(duì)應(yīng)的哈希桶中。如果哈希沖突，則將該鍵值對(duì)插入到鏈表的尾部，如果鏈表中已經(jīng)存在相同的鍵，則更新該鍵所對(duì)應(yīng)的值。
“`c
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)
{
long index;
dictEntry *entry;
dictht *ht;
if (dictIsRehashing(d))
_dictRehashStep(d);
// 找到kv對(duì)應(yīng)的table index
if ((index = _dictKeyIndex(d, key, dictHashKey(d, key), existing)) == -1)
return NULL;
// 計(jì)算kv對(duì)應(yīng)bucket
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
entry = zmalloc(sizeof(*entry));
entry->next = ht->table[index];
ht->table[index] = entry;
ht->used++;
dictSetKey(d, entry, key);
return entry;
}
刪除
Dict中的刪除操作主要涉及到對(duì)哈希桶中相應(yīng)鍵值對(duì)的刪除。對(duì)于通過(guò)哈希計(jì)算得到的鍵值對(duì)，我們可以直接在哈希桶中刪除，如果是在哈希沖突鏈表中的鍵值對(duì)，則需要先查找鏈表中的該鍵值對(duì)，在將其刪除。具體代碼實(shí)現(xiàn)如下：
```c
int dictDelete(dict *d, const void *key)
{
return dictGenericDelete(d,key,NULL);
}
int dictGenericDelete(dict *d, const void *key, dictEntry **existing)
{
unsigned long h, idx;
dictEntry *he, *prevHe;
int table;
// 確定刪除的位置以及table
if (d->ht[0].used == 0 && d->ht[1].used == 0) return DICT_ERR;
if (dictIsRehashing(d)) _dictRehashStep(d);
h = dictHashKey(d, key);
for (table = 0; 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)) {
if (existing)
*existing = he;
if (prevHe)
prevHe->next = he->next;
else
d->ht[table].table[idx] = he->next;
if (d->type->keyDestructor)
d->type->keyDestructor(d->privdata, he->key);
if (d->type->valDestructor)
d->type->valDestructor(d->privdata, he->v.val);
zfree(he);
d->ht[table].used--;
return DICT_OK;
}
prevHe = he;
he = he->next;
}
if (!dictIsRehashing(d)) break;
}
return DICT_ERR;
}
查找
Dict中的查找操作是對(duì)鍵值對(duì)的查詢，通過(guò)哈希函數(shù)得到該鍵對(duì)應(yīng)的哈希桶，再在哈希桶中查找該鍵值對(duì)。具體代碼實(shí)現(xiàn)如下：
“`c
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
香港服務(wù)器選創(chuàng)新互聯(lián)，香港虛擬主機(jī)被稱為香港虛擬空間/香港網(wǎng)站空間，或者簡(jiǎn)稱香港主機(jī)/香港空間。香港虛擬主機(jī)特點(diǎn)是免備案空間開(kāi)通就用， 創(chuàng)新互聯(lián)香港主機(jī)精選cn2+bgp線路訪問(wèn)快、穩(wěn)定！
分享標(biāo)題：鉆研Redis源碼，掌握Dict結(jié)構(gòu)（redis源碼dict）
文章鏈接：http://www.dlmjj.cn/article/cdhegpj.html
