redis学习系列（五）--redis基础字典的构造

最近真是有点疯啊，更新的有点勤快，主要还是最近项目处于一个真空期，迭代版本已经准备好，等着上线，下个版本需求已经完成大半，并且没什么复杂的，因此读书时间比较多，项目中其实用过redis，并且redis是集群的，用来保存分布式session和用作缓存使用的，配置文件我不知道，但是等这边的一些知识看完回去研究一下公司内部的redis代码，都是大神写的，看看还是不错的。

这一篇来看看字典的内部构造，其实看这些东西，感觉很枯燥，但是又必须要过一遍，不然你不知道用起来的时候它里面什么样子，只知道使用可不是个好现象。

字典的底层实现就是：字典-->哈希表-->哈希节点-->键值对

哈希表

typedef struct dictht {

    // 哈希表数组
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

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

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

} dictht;

table是一个数组，数组中每一个元素都是执行一个entry的指针，每一个entry都保存着一个键值对。

size保存了哈希表的大小，就是table数组的大小

used记录了哈希表目前已有节点的数量

sizemask属性的值总是等于size-1，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面

一个空的哈希表

redis学习系列（五）--redis基础字典的构造

哈希表节点

哈表表内的节点用entry表示，每个entry保存着一个键值对

typedef struct dictEntry {

    // 键
    void *key;

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

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

} dictEntry;

key保存着键值对中的键，而v属性保存着值，其内部保存的数据暂时不去追究，可以是指针，可以是uint64_t整数，可以是int64_t整数

next属性执行另一个哈希表节点的指针，注意这个指针可以将多个entry链接起来形成链表，其实就hashmap一样，是解决hash冲突的。

redis学习系列（五）--redis基础字典的构造

字典

回到最外层的构造，

typedef struct dict {

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

    // 私有数据
    void *privdata;

    // 哈希表
    dictht ht[2];

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

} dict;

type和privdata是针对不同类型的键值对而设置的，了解一下：

type是执行dictType结构的指针，每个type指针保存了一簇用于操作特定类型键值对的函数

privdata则是保存了需要传给那些特定函数的可选参数。

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;

ht属性则是我们上面说过的哈希表存放的地方，内部有两个数组组成，一般情况下字典只使用ht[0]哈希表，而ht[1]则是对ht[0]进行rehash时使用。

而要进行rehash，另一个值就是rehashidx。

图为普通状态下的字典：

redis学习系列（五）--redis基础字典的构造

hash算法

与hashmap类似，redis里面使用的hash算法也是需要先计算hash值，然后再计算索引值，最后再将元素放到指定位置上去。

# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;