钻研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中的删除操作主要涉及到对哈希桶中相应键值对的删除。对于通过哈希计算得到的键值对，我们可以直接在哈希桶中删除，如果是在哈希冲突链表中的键值对，则需要先查找链表中的该键值对，在将其删除。具体代码实现如下：

```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;
}