redis-字典 - k先生

定义

typedef struct dictEntry {      // 哈希节点
    void *key;      // 键
    union {     // 值
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;     // 解决键冲突
} dictEntry;

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

typedef struct dict {       // 字典
    dictType *type;     // 类型特定函数，创建多态字典而设置
    void *privdata;     // 私有数据，创建多态字典而设置
    dictht ht[2];       // 哈希表
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */      // rehash索引
    unsigned long iterators; /* number of iterators currently running */        // 正在运行中的遍历器数量
} dict;

结构图：
字典结构

字典也是redis键值对的结构，即数据库底层的实现。

哈希算法

// 定义
#define dictHashKey(d, key) (d)->type->hashFunction(key)

/* Get the index in the new hash table */
h = dictHashKey(d, de->key) & d->ht[1].sizemask;

redis使用MurmurHash2算法来计算键的hash值,这个算法的优点在于即使输入的键有规律，也能给出一个很好的随机分布性；
MurmurHash2算法

解决冲突

redis的哈希表使用链地址法来解决键冲突，新加入的节点会添加到链表的表头，排在其他所有节点的前面。

rehash算法

rehash步骤：

使用地点的ht[1]作为备份进行扩容或收缩空间
扩容和收缩时，ht[1]的大小大于等于ht[0].used*2的2^n（2的n次方幂）

1.执行扩容前

2.扩容时分配空间
扩容前

3.迁移节点
扩容前

哈希表的扩容与收缩

以下条件任意一个被满足，就会执行扩容：

没有执行BGSAVE或BGREWRITEAOF命令，hash表的负载因子大于等于1
正在执行BGSAVE或BGREWRITEAOF命令，hash表的负载因子大于等于5

负载因子计算公式：
load_factor = ht[0].used/ht[0].size 即，负载因子 = 哈希表已保存节点数量/哈希表大小；

当哈希表的负载因子小于0.1时，程序自动开始对hash表进行收缩操作；

rehash动作并不是一次性、集中式完成的，而分多次、渐进式地完成的。

Contents

定义

哈希算法

解决冲突

rehash算法

哈希表的扩容与收缩