Redis 数据结构之Map(字典)

Lowky 发布于2019-07-24 16:15 / 703人阅读

摘要：渐进式的操作步骤为分配指定空间，让字典同时持有和两个哈希表。其实这就是哈希表结构中字段的意义，就是用来保存这个数字直接用于计算。

概念

哈希表：也叫散列表，是根据关键码值(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 操作步骤

哈希表的扩容：

为字典ht[1]分配空间，大小为第一个大于等于 ht[0].used * 2 的 2 的幂；
比如：ht[0].used 当前的值为 4 ， 4 * 2 = 8 ，而 8 （2^3）恰好是第一个大于等于 4 的 2 的 n 次方，所以程序会将 ht[1] 哈希表的大小设置为 8 。

将保存在 ht[0] 上的键值对 rehash 到 ht[1] 上，rehash 就是重新计算哈希值和索引，并且重新插入到 ht[1] 中，插入一个删除一个

当 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的操作步骤：

为 ht[1] 分配指定空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表。

将 rehashidx 设置为0，表示正式开始 rehash。

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

最后，当 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这个数字直接用于计算。

云内存存储UMem Redis map数据类型字典结构数据字典 js map数据

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/37073.html

redis 学习笔记

摘要：集合集合是等命令的操作对象它使用和两种方式编码中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是。这篇 redis 学习笔记主要介绍 redis 的数据结构和数据类型，并讨论数据结构的选择以及应用场景的优化。 redis 是什么? Redis是一种面向键/值对类型数据的分布式NoSQL数据库系统，特点是高性能，持久存储，适应高并发的应用场景。 Redis 数据结构动态字符...

Batkid 2019-07-25 12:16 评论0 收藏0
redis 学习笔记

摘要：集合集合是等命令的操作对象它使用和两种方式编码中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是。这篇 redis 学习笔记主要介绍 redis 的数据结构和数据类型，并讨论数据结构的选择以及应用场景的优化。 redis 是什么? Redis是一种面向键/值对类型数据的分布式NoSQL数据库系统，特点是高性能，持久存储，适应高并发的应用场景。 Redis 数据结构动态字符...

draveness 2019-07-24 15:06 评论0 收藏0
跟着大彬读源码 - Redis 8 - 对象编码之字典

摘要：属性记录了哈希表目前已有节点键值对的数量。字典字典的结构类型特定函数私有数据哈希表两个记录进度的标志。此外，字典在进行时，删除查找更新等操作会在两个哈希表上进行。在对哈希表进行扩容或收缩操作时，使用渐进式完成。字典，是一种用于保存键值对的抽象数据结构。由于 C 语言没有内置字典这种数据结构，因此 Redis 构建了自己的字典实现。在 Redis 中，就是使用字典来实现数据库底层的。...

kun_jian 2019-08-06 13:45 评论0 收藏0
redis数据结构

摘要：序正好写应用之分布式会话这篇文章，用到了。于是就补充一些的基本常识。对象当在新建键值对的时候，新建两个对象，一个是键对象，一个是值对象。序正好写SpringBoot应用之分布式会话这篇文章，用到了redis。于是就补充一些redis的基本常识。 redis对象当在redis新建键值对的时候，新建两个对象，一个是键对象，一个是值对象。键对象一般键对象都是string对象值对象...

Travis 2019-07-24 14:37 评论0 收藏0
【3y】从零单排学Redis【青铜】

摘要：从代码上看字典也是在哈希表基础上再抽象了一层而已。在中，哈希表实际上就是数组链表的形式来构建的。后，在哈希冲突时是将新的节点添加到链表的表尾。在对哈希表进行扩展或者收缩操作时，过程并不是一次性地完成的，而是渐进式地完成的。前言只有光头才能变强 showImg(https://segmentfault.com/img/remote/1460000016837794); 最近在学Red...

lookSomeone 2019-08-16 13:33 评论0 收藏0