钻研Redis源码，掌握Dict结构（redis源码 dict）
钻研Redis源码，掌握Dict结构
Redis作为一种高性能的key-value存储系统，被广泛应用于数据缓存、消息队列等场景。其核心数据结构包括String、List、Set、ZSet和Hash等类型，在Redis的代码实现中，很多数据结构采用C语言实现。其中，Dict结构作为Redis中常用的哈希表，被广泛使用。本文将介绍Dict的结构、原理和实现，并且详细探讨Dict的部分源码，希望对读者了解Redis的数据结构有所帮助。
1. Dict结构
在源码中，Dict结构被定义在dict.h文件中。Dict是一个哈希表的结构体，包含以下几个成员：
“`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结构体表示哈希表中的一个键值对，包含键、值、指向下一个dictEntry的指针等成员；dictType结构体用于定义字典操作的相关函数，比如哈希函数、键值复制函数和键值比较函数等；dictht结构体则是哈希表的关键结构体，包含哈希桶指针数组、桶大小、桶数量等成员；而dict则包含dictType、dictht等成员，用于表示一个完整的字典结构。
2. 原理
Dict通过哈希表实现快速查找键值对。哈希表是一种用于实现关联数组的数据结构，其基本思路是将键通过哈希函数转换成索引，存放在哈希桶中，从而实现快速的查找和插入。Dict中的哈希桶使用指针数组来存储，每个哈希桶元素对应一个dictEntry结构体。当插入或查找键值对时，先通过哈希函数计算出对应的哈希值，并将其映射到哈希桶上，找到对应的桶元素指针，然后在桶中查找或插入dictEntry。
为了解决哈希冲突的问题，Dict中使用了拉链法作为哈希桶的冲突解决方法。当多个键值对的哈希值相同时，将这些键值对通过一个链表连接在一起，从而解决了哈希冲突问题。
3. 实现
Dict的源码实现分为几个部分，包括初始化、添加、删除、查找、哈希冲突处理等。下面我们通过具体的代码实例来详细介绍Dict的源码实现。
初始化
Dict的初始化主要是对哈希桶进行初始化，同时设置字典类型和哈希扩展因子等信息。下面是Dict初始化代码的实现：
```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]);
// 设置字典类型信息 d->type = type;
// 设置字典类型私有数据 d->privdata = privdata;
d->rehashidx = -1; d->iterators = 0;
}
添加
Dict的添加操作主要是对键值对进行哈希计算，并将该键值对插入到对应的哈希桶中。如果哈希冲突，则将该键值对插入到链表的尾部，如果链表中已经存在相同的键，则更新该键所对应的值。
“`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对应的table index
if ((index = _dictKeyIndex(d, key, dictHashKey(d, key), existing)) == -1)
return NULL;
// 计算kv对应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中的删除操作主要涉及到对哈希桶中相应键值对的删除。对于通过哈希计算得到的键值对，我们可以直接在哈希桶中删除，如果是在哈希冲突链表中的键值对，则需要先查找链表中的该键值对，在将其删除。具体代码实现如下：
```cint 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中的查找操作是对键值对的查询，通过哈希函数得到该键对应的哈希桶，再在哈希桶中查找该键值对。具体代码实现如下：
“`c
dictEntry *dictFind(dict *d, const void *key)
{
dictEntry *he;
