Redis 源码--字典 P1.字典结构。

字典是一种进行利用key快速查找value的key-value结构。从定义上来说key应该具有唯一性，即从编程语言的层面上来说，一个字典里不能存在两个语义相同的key。同样的C也没有自己的字典实现，于是Redis实现了自己的字典。
Redis的字典是通过HashTable来实现的，相比红黑树，hash的实现真的挺简单了。Hahs表必须要解决hashode的冲突问题（hashcode的冲突并不意味中hashcode一定是相等的。），常见的解决方法是拉链法和线性探测法。
简单来说拉链法是使用一个桶（bucket）来聚集所有hashcode()冲突的key，而线性探测则是将冲突的key简单的后移。
Redis的HashTable的实现方法是拉链法。通过两个table的渐进式的hash，保证了性能不会有太大的损失。
与链表类似，Redis使用了一个dict结构来操作字典（dict）。

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} dict;

逐个来看一下里面的结构：第一个是dicTtype结构体，其定义如下,主要存储了所使用的各个用于HashTable操作的函数指针。

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;

void *privdata是保存的传给dictType的可选参数。

dictht ht[2]声明的两个结构体数组。

typedef struct dictht {
    
    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

    // 该哈希表已有节点的数量
    unsigned long used;

} dictht;

其中最主要的结构应该是dictEntry 数组dictEntry **table，它定义了size个保存dictEntry 的桶(解决链冲突)的数组。dictEntry是每个hash表的结点，是保存每个key-value对的实体。

typedef struct dictEntry {
    
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下个哈希表节点，形成链表
    struct dictEntry *next;

} dictEntry;

可以看到redis在值内部允许一个指向任意值的指针，或者是一个64位的无符号数，亦或是64的有符号数。

总的来说：在文档里是这写的：
Hash tables will auto-resize if needed

• tables of power of two in size are used, collisions are handled by
• chaining.

dictEntry数组会以2的指数倍的形式进行自动扩容，键冲突通过拉链法完成。