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