Redis 数据结构之Map(字典)

概念

• 哈希表：也叫散列表，是根据关键码值(Key value)而直接进行访问的数据结构也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。
• 哈希函数：哈希表中元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为哈希函数）
• 哈希冲突：计算关键码获取的位置可能会重复，就就是冲突。如何解决冲突Redis中使用了链址法

字典实现

哈希表

typedef struct dictht{
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    //哈小标大小掩码，用于计算 下面一小节的如何计算位置可以看到具体的意义。
    unsigned long sizemask;
    //哈希表已有节点的数量
    unsigned long used;
}

• table：是一个数组，数组的每个元素都是一个指向 dict.h/dictEntry 结构的指针；(结构下面可见)
• size：记录哈希表的大小，即 table 数组的大小，且一定是2的幂；
• used：记录哈希表中已有结点的数量；
• sizemask：用于对哈希过的键进行映射，索引到 table 的下标中，且值永远等于 size-1。具体映射方法很简单，就是对 哈希值 和 sizemask 进行位与操作，由于 size 一定是2的幂，所以 sizemask=size-1，自然它的二进制表示的每一个位(bit)都是1，等同于下文提到的取模；

哈希表节点

typedef struct dictEntry{
    // 键
    void *key
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;
    //只想下一个哈希表节点，形成链表
    struct dictEntry *next;
}dictEntry;

• key：是键值对中的键；
• v：是键值对中的值，它是一个联合类型，方便存储各种结构；
• next：是链表指针，指向下一个哈希表节点，他将多个哈希值相同的键值对串联在一起，用于解决键冲突；如图所示，两个dictEntry 的 key 分别是 k0 和 k1，通过某种哈希算法计算出来的哈希值和 sizemask 进行位与运算后都等于 3，所以都被放在了 table 数组的 3号槽中，并且用 next 指针串联起来。

redis中的字典

typedef struct dict{
    //
    dictType *type
    //
    void *privdata;
    //
    dictht ht[2]
    //
    int trehashidx;
}dict;

• type： 是一个指向 dict.h/dictType 结构的指针，保存了一系列用于操作特定类型键值对的函数；
• ht：是两个哈希表，一般情况下，只使用ht[0]，只有当哈希表的键值对数量超过负载(元素过多)时，才会将键值对迁移到ht[1]
• trehashidx：由于哈希表键值对有可能很多很多，所以 rehash 不是瞬间完成的，需要按部就班，那么 rehashidx 就记录了当前 rehash 的进度，当 rehash 完毕后，将 rehashidx 置为-1；

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;

Rehash

其实没有想象中的那么复杂，随着字典操作的不断执行，哈希表保存的键值对会不断增多（或者减少），为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，需要对哈希表大小进行扩展或者收缩。

扩展与收缩的条件

负载因子：load_factor=ht[0].used/ht[0].size 当前使用过的节点数除以哈希大小。
当以下条件满足任意一个时，程序就会对哈希表进行扩展操作

• 服务器目前没有执行bgsave或bgrewriteaof命令，并且哈希表的负载因子>=1
• 服务器目前正在执行bgsave或bgrewriteaof命令，并且哈希表的负载因子>=5

当负载因子的值小于0.1时，程序就会对哈希表进行收缩操作

Rehash 操作步骤

哈希表的扩容：

1. 为字典ht[1]分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂；
   比如：ht[0].used 当前的值为 4 ， 4 * 2 = 8 ， 而 8 （2^3）恰好是第一个大于等于 4 的 2 的 n 次方， 所以程序会将 ht[1] 哈希表的大小设置为 8 。
2. 将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个
3. 当 ht[0] 包含的所有键值对全部 rehash 到 ht[1] 上后，释放 ht[0] 的控件， 将 ht[1] 设置为 ht[0]，并且在 ht[1] 上新创件一个空的哈希表，为下一次 rehash 做准备；

哈希表的收缩：
同样是为 ht[1] 分配空间， 大小等于 max( ht[0].used, DICT_HT_INITIAL_SIZE )，然后和扩展做同样的处理即可。

渐进式rehash

扩展或者收缩哈希表的时候，需要将 ht[0] 里面所有的键值对 rehash 到 ht[1] 里，当键值对数量非常多的时候，这个操作如果在一帧内完成，大量的计算很可能导致服务器宕机，所以不能一次性完成，需要渐进式的完成。
渐进式Rehash的操作步骤：

1. 为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
2. 将 rehashidx 设置为0，表示正式开始 rehash。
3. 在进行 rehash 期间，每次对字典执行 增、删、改、查操作时，程序除了执行指定的操作外，还会将 哈希表 ht[0].table中下标为 rehashidx 位置上的所有的键值对 全部迁移到 ht[1].table 上，完成后 rehashidx 自增。这一步就是 rehash 的关键一步。为了防止 ht[0] 是个稀疏表 （遍历很久遇到的都是NULL），从而导致函数阻塞时间太长，这里引入了一个 “最大空格访问数”，也即代码中的 enmty_visits，初始值为 n*10。当遇到NULL的数量超过这个初始值直接返回。
4. 最后，当 ht[0].used 变为0时，代表所有的键值对都已经从 ht[0] 迁移到 ht[1] 了，释放 ht[0].table， 并且将 ht[0] 设置为 ht[1]，rehashidx 标记为 -1 代表 rehash 结束。

心中的疑问

如何计算位置

其实哈希表、字典、map，我们并不陌生但是我对这个位置如何计算出的一直是一知半解。也查了一些资料下面整合一下。
如果我们有一个长度为4的哈希表，有4个数字要放入（6，7，9，12）那很简单只要对4个数字用4取模就可以。结果为：[12,9,6,7]。
我们知道取模操作的效率是很低的，那么我们可以用位运算来代替。
解决方案为：把哈希表的长度 L 设置为2的幂（L = 2^n），那么 L-1 的二进制表示就是n个1，任何值 x 对 L 取模等同于和
(L-1) 进行位与（C语言中的&）运算。

如何解决冲突

那么问题来了如果数字是（6，7，9，11） 如果用4取模[nil,9,6,7 11]这样就会出现7 11
对4取模结果都为3发生了冲突。 这就是所谓的哈希键冲突，那么如何解决这样的冲突有很多解决方法，开放地址法、再散列法、链地址法
等等。redis中使用的是链址法，在对象中保存下一个值得地址。接下来继续上面的算法。其实这就是redis 哈希表结构中 sizemask
字段的意义，就是用来保存L-1这个数字直接用于计算。