Redis数据结构(3)：hash(字典)

1. 概述

　　Redis hash 是一个string类型的field和value的映射表，hash特别适合用于存储对象。

　　Redis 中每个 hash 可以存储 2³² - 1 键值对（40多亿）。

2. 基本结构

typedef struct dictEntry {
    void *key; // 键
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 指向下个节点的指针, hash 值相同的键值对构成单向链表 头插法
} dictEntry;

// 哈希表结构。 每个字典都有两个，因为我们实现了从旧表到新表的增量重写
typedef struct dictht {
    dictEntry **table;
    PORT_ULONG size; // hash 表大小
    PORT_ULONG sizemask; // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
    PORT_ULONG used; // 节点个数
} dictht;

typedef struct dict {
    dictType *type; // 类型特定函数  实现多态
    void *privdata; // 私有数据
    dictht ht[2]; // 两个 hash table
    PORT_LONG rehashidx; // 如果rehashidx == -1则不进行重复
    int iterators; // 当前正在运行的迭代器数
} dict;

3. 渐进式 rehash

　　a. 它就是一个键值对，对于hash冲突的处理采用了头插法的链式存储来解决。新节点添加到链表的表头位置

　　b. 对rehash，扩展就是取第一个大于等于 used * 2 的2 ^ n的数作为新的hash表大小；缩紧就是取第一个大于等于 used 的2 ^ n的数作为新的hash表大小。

　　c. 有个负载因子的概念（负载因子 = used / size）,没有执行BGSAVE或者BGREWRITEAOF时大于1就会扩展，小于0.1就会缩紧。

3.1 详细步骤

为 ht [1] 分配空间, 字典同时持有两个哈希表
rehashidx 设置为 0 , rehash正式开始
rehash 期间, 每次对字典的增删改查操作时, 程序除了执行特定的操作外, 还会将 ht [0] 中节点数组的 rehashidx 位置上的数据迁移到 ht [1] , 然后 rehashidx +1;
当rehash完成后, rehashidx 赋值为 -1 ;

3.2 rehash期间的哈希表操作

　　rehash 期间, 哈希表的删改查操作先在 ht [0] 上执行, 找不到则在 ht [1]上进行操作.

　　增加操作在 ht [1]上进行操作,

　　保证 ht[0]上的数据只减不增,