Redis 中的字典（dict）是一种用来保存键值对的常见数据结构

概念

Redis 中的字典结构由三个不同的部分构成：字典主体（dict）、哈希表（dictht）和哈希节点（dictEntry）。

哈希表节点的定义为：

typedef struct dictEntry {
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

可以看出，每个节点不光持有了节所必须的键名和键值，还保存了一个指向下个节点的指针 Next ,这个指针的主要作用是用来形成链表，用来解决哈希值冲突的问题；

哈希表的结构为：

typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈希表大小掩码，用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    //该哈希表已有节点的数量
    unsigned long used;
} dictht;

哈希表节点除了用于指向第一个哈希节点外，还存储了当前哈希表的尺寸和已经使用的节点数量，这两个字段用来评估哈希表的负载情况，后续对哈希表执行 rehash 时候会用到；

字典主体的结构为：

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    // rehash索引
    //当rehash不在进行时，值为-1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;

可以看出，字典结构体中承载了不止一个哈希表，这样做的目的是为了在实际使用时候防止单个hash表出现负载过重的情况，如果单个hash表承载的节点过多的时候，就会通过 rehash ，将一张哈希表中的节点逐渐的迁移到另外一张表中。

源码

最新的源码结构体定义在：https://github.com/redis/redis/blob/7.2.4/src/dict.h#L84

先来看看字典主体的定义：

struct dict {
    dictType *type;

    dictEntry **ht_table[2];
    unsigned long ht_used[2];

    long rehashidx; /* rehashing not in progress if rehashidx == -1 */

    /* Keep small vars at end for optimal (minimal) struct padding */
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
    signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */

    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as defined
                                 * by dictType's dictEntryBytes. */
};

再看看 dictEntry 的定义：https://github.com/redis/redis/blob/7.2.4/src/dict.c#L63

struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     /* Next entry in the same hash bucket. */
    void *metadata[];           /* An arbitrary number of bytes (starting at a
                                 * pointer-aligned address) of size as returned
                                 * by dictType's dictEntryMetadataBytes(). */
};

可以看到最新的字典结构中，去掉了哈希表的概念，直接将字典节点指针存入字典主题的 dictEntry **ht_table[2] 属性，同样的，在 dict 的结构中增加了分别记录两个哈希节点列表的长度和使用数量的字段：unsigned long ht_used[2] 和 signed char ht_size_exp[2]。

这里注意到字典主体并没有直接记录哈希表的实际长度值，而是用一个幂指数signed char ht_size_exp[2] 来实现，要获取对应哈希表的长度，需要通过位移运算size = 1<<exp来获得，这样的话，事实上哈希表在内存中占用的长度都是2字节对齐的（因为每次位移运算都是相当于对2求一次指数，位移n次后 size=2^n），这又是为什么呢？

这就要从哈希表的使用场景说起了，每次往哈希表里面填入新的键值对时候，都要通过字典的哈希函数计算新 key 的哈希值，再和哈希表的长度取模，最终得到一个新key在哈希表中的索引值：

idx = hashFunc(key) % size

如果存在 size 满足条件 size = 2^n，那上面的取模运算可以等价转换成运算效率更快的位运算：

idx = hashFunc(key) & (size - 1)

真是因为这个原因，redis 才要求哈希表的长度一定是2字节对齐的。

继续看源码中的结构体定义，可以发现源码中还定义了一个 dictType：

typedef struct dictType {
    uint64_t (*hashFunction)(const void *key);
    void *(*keyDup)(dict *d, const void *key);
    void *(*valDup)(dict *d, const void *obj);
    int (*keyCompare)(dict *d, const void *key1, const void *key2);
    void (*keyDestructor)(dict *d, void *key);
    void (*valDestructor)(dict *d, void *obj);
    int (*expandAllowed)(size_t moreMem, double usedRatio);
    /* Flags */
    /* The 'no_value' flag, if set, indicates that values are not used, i.e. the
     * dict is a set. When this flag is set, it's not possible to access the
     * value of a dictEntry and it's also impossible to use dictSetKey(). Entry
     * metadata can also not be used. */
    unsigned int no_value:1;
    /* If no_value = 1 and all keys are odd (LSB=1), setting keys_are_odd = 1
     * enables one more optimization: to store a key without an allocated
     * dictEntry. */
    unsigned int keys_are_odd:1;
    /* TODO: Add a 'keys_are_even' flag and use a similar optimization if that
     * flag is set. */

    /* Allow each dict and dictEntry to carry extra caller-defined metadata. The
     * extra memory is initialized to 0 when allocated. */
    size_t (*dictEntryMetadataBytes)(dict *d);
    size_t (*dictMetadataBytes)(void);
    /* Optional callback called after an entry has been reallocated (due to
     * active defrag). Only called if the entry has metadata. */
    void (*afterReplaceEntry)(dict *d, dictEntry *entry);
} dictType;

这个结构体里面存放了一些和字典类型有关的元数据和函数，如uint64_t (*hashFunction)(const void *key)这个函数用来计算哈希值，每次元素写入字段时候，都先调用这个函数计算出对应在节点列表中的位置，然后加入。

最后再来看看字典是如何解决hash冲突的，dictFindPositionForInsert （https://github.com/redis/redis/blob/7.2.4/src/dict.c#L1442）这个函数用来在向 Dict 中添加新的键值对时候，为新插入的键值对寻找字典中合适的位置：

/* Finds and returns the position within the dict where the provided key should
 * be inserted using dictInsertAtPosition if the key does not already exist in
 * the dict. If the key exists in the dict, NULL is returned and the optional
 * 'existing' entry pointer is populated, if provided. */
void *dictFindPositionForInsert(dict *d, const void *key, dictEntry **existing) {
    ...
    for (table = 0; table <= 1; table++) {
        idx = hash & DICTHT_SIZE_MASK(d->ht_size_exp[table]);
        /* Search if this slot does not already contain the given key */
        he = d->ht_table[table][idx];
        while(he) {
            void *he_key = dictGetKey(he);
            if (key == he_key || dictCompareKeys(d, key, he_key)) {
                if (existing) *existing = he;
                return NULL;
            }
            he = dictGetNext(he);
        }
        if (!dictIsRehashing(d)) break;
    }
    ...
}

这里 idx 是经过哈希运算以后得出的新键值对在哈希表中插入后的位置，he = d->ht_table[table][idx] 获取到对应位置的字典节点之后，因为哈希节点是个链表，redis 会遍历这个链表，如果找到之前已经插入过的相同 key 值，就会返回重复的节点所在位置，否则就一直遍历链表到末端（dictEntry->next == NULL）,后续代码就会将新的键值对插入到节点末端。