深入学习Redisdict源码剖析（redis源码之dict）

深入学习Redis：dict源码剖析

Redis是一个高性能的键值存储系统，其中的数据结构dict扮演了至关重要的角色。dict是Redis内部用来实现哈希表的数据结构，它的性能决定了Redis的性能。本文将深入探究Redis中的dict数据结构源码以及如何使用它。

dict的基本结构

在Redis的源码中，dict的实现在字典结构体dictType中定义。dictType的结构如下：

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;

dictType中定义了dict的6个回调函数，包括了键的哈希函数、键的复制函数、值的复制函数、键的比较函数、键的析构函数以及值的析构函数。

接着我们看dictEntry的定义，dictEntry正好能代表dict中的一项，其结构体如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

dictEntry中存放了一个key以及一个val，其中val是一个Union，能存放多种类型的值。next是为了解决hash算法冲突而存在的指针。

最后是dict的定义了，它的结构体定义如下：

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的定义中，我们可以看到dict是由两个dictht结构体组成的，也就是说，dict中包含了两个哈希表（table）。其中一个叫做ht[0]，它是正在被使用的哈希表，ht[1]则是用来在rehash（rehash是Redis用来动态扩容的）过程中存放数据的哈希表。

dict的方法实现

dict的方法可以分为两类：通用方法和私有方法。通用方法是指dict的外部接口，提供给外部程序使用的方法。它们包括dictAdd、dictFind、dictDelete等方法。而私有方法是指dict内部使用的方法，只供dict内部调用。它们包括_dictRehashStep、_dictKeyIndex、_dictExpandIfNeeded等方法。

dict的添加函数dictAdd的实现如下：

int dictAdd(dict *ht, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(ht,key,NULL);
    if (!entry) return DICT_ERR;
    dictSetVal(ht, entry, val);
    return DICT_OK;
}

dictAdd方法调用了dictAddRaw方法来添加一个新的键值对，如果添加成功，则返回DICT_OK，否则返回DICT_ERR。

dict的查找函数dictFind实现如下：

dictEntry *dictFind(dict *ht, const void *key)
{
    dictEntry *he;
    unsigned int h;

    if (ht->size == 0) return NULL;
    if (dictIsRehashing(ht)) _dictRehashStep(ht);
    h = dictHashKey(ht, key);
    for (int table = 0; table 
        he = ht->ht[table].table[h & ht->ht[table].sizemask];
        while (he) {
            if (dictCompareKeys(ht, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(ht)) return NULL;
    }
    return NULL;
}

dictFind方法通过dictHashKey方法计算出key对应的哈希值，然后从两个哈希表中查找对应的dictEntry对象。查找时，先从正在使用的哈希表（table[0]）开始查找，如果找到了就返回当前的dictEntry对象，如果在table[0]中没有找到，再到table[1]中查找。如果在table[1]中依然没有找到，说明该key不存在于Redis里。

dict的删除函数dictDelete实现如下：

int dictDelete(dict *ht, const void *key)
{
    dictEntry *he, *prevHe = NULL;
    unsigned int h;
    int table;
    if (ht->ht[0].size == 0 && ht->ht[1].size == 0) return DICT_ERR;
    if (dictIsRehashing(ht)) _dictRehashStep(ht);
    h = dictHashKey(ht, key);

    for (table = 0; table 
        he = ht->ht[table].table[h & ht->ht[table].sizemask];
        while (he) {
            if (dictCompareKeys(ht, key, he->key)) {
                if (prevHe)
                    prevHe->next = he->next;
                else
                    ht->ht[table].table[h & ht->ht[table].sizemask] = he->next;
                dictFreeEntryKey(ht, he);
                dictFreeEntryVal(ht, he);
                zfree(he);
                ht->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(ht)) break;
    }
    return DICT_ERR;
}

dictDelete方法先计算key的哈希值，然后从两个哈希表中查找包含该key的dictEntry对象。找到该对象后，从链表上删除，并释放内存。如果删除成功，返回DICT_OK，否则返回DICT_ERR。

使用dict实现缓存机制

dict的高效性能为Redis实现缓存机制提供了极大的便利。我们可以将常用数据放入Redis中，它们会被存储在内存中，当需要访问数据时可以直接从内存中读取，减少了文件I/O操作，提升了访问速度。

我们可以编写以下代码来实现缓存机制：

#include "redis.h"
void cacheData(redisClient *c) {
    dictEntry *de;
    dict *dictPtr;
    long long bytes = 0;
    /* If the key already exists in the cache, delete it first */
    if (lookupKeyRead(c->db,c->argv[1]->ptr) != NULL) {
        dbDelete(c->db,c->argv[1]);
    }
    /* Add the key-value pr to the cache */
    dictPtr = c->db->dict;
    de = dictAddRaw(dictPtr,c->argv[1]->ptr,NULL);
    bytes += sdslen(c->argv[1]->ptr)+dictSize(dictPtr->valsize);
    dictSetVal(dictPtr, de, c->argv[2]);
    incrRefCount(c->argv[2]);
    c->db->dict->expire = 0;
    addReply(c,shared.ok);
}