hash结构里其实是一个字典，有许多的键值对（类似于python的dict类型）

Redis hash 哈希数据类型 - 图1

注意，哈希对象也有两种实现方式，Redis根据不同的策略使用不同的底层实现：

  • ziplist(压缩列表)
  • hashtable(哈希列表)

策略：

  • 只有当存储的数据量比较小的情况下，Redis 才使用压缩列表来实现哈希对象
  • 字典中保存的键和值的大小都要小于 64 字节；
  • 字典中键值对的个数要小于 512 个。

当不能同时满足上面两个条件的时候，Redis 就使用哈希表来实现哈希对象。

了解ziplist(压缩列表)

与SDS数据结构一样，压缩列表也是redis团队，自己设计为redis而产生的数据存储结构。它有点儿类似数组，通过一片连续的内存空间，来存储数据。不过，它跟数组不同的一点是，它允许存储的数据大小不同

简单压缩列表

压缩 = 节省内存【这是想比较数组存储来说的】

我们知道,数组要求每个元素的大小相同,如果我们要存储不同长度的字符串,那我们就需要用最大长度的字符串大小作为元素的大小(假设是20个字节)。存储小于 20 个字节长度的字符串的时候，便会浪费部分存储空间。

Redis hash 哈希数据类型 - 图2

数组的优势占用一片连续的空间可以很好的利用CPU缓存访问数据。如果我们想要保留这种优势，又想节省存储空间我们可以对数组进行压缩

Redis hash 哈希数据类型 - 图3

但是这样有一个问题，我们在遍历它的时候由于不知道每个元素的大小是多少，因此也就无法计算出下一个节点的具体位置。这个时候我们可以给每个节点增加一个lenght的属性

Redis hash 哈希数据类型 - 图4

如此。我们在遍历节点的之后就知道每个节点的长度(占用内存的大小)，就可以很容易计算出下一个节点再内存中的位置。这种结构就像一个简单的压缩列表了。

Redis的压缩列表

  • 压缩列表(zip1ist)是列表和哈希的底层实现之一。
  • 当一个列表只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表的底层实现。
  • 当一个哈希只包含少量键值对,比且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希的底层实现。

Redis 压缩列表的构成

压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型(sequential)数据结枃。

一个压缩列表可以包含任意多个节点(entry),每个节点可以保存一个字节数组或者一个整数值

Redis hash 哈希数据类型 - 图5

示例：

Redis hash 哈希数据类型 - 图6

PS：

  1. 如上图，展示了一个总长为80字节，包含3个节点的压缩列表。如果我们有一个指向压缩列表起始地址的指针p，那么表为节点的地址就是P+60。

Redis 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值。其中，字节数组可以是以下三种长度中的一种。

  • 长度小于等于63(2^6-1)字节的字节数组;
  • 长度小于等于16383(2^14-1)字节的字节数组
  • 长度小于等于4294967295(2^32-1)字节的字节数组

整数值可以是以下6种长度中的一种

  • 4位长,介于0至12之间的无符号整数
  • 1字节长的有符号整数
  • 3字节长的有符号整数
  • int16_t类型整数
  • int32_t类型整数
  • int64_t类型整数

Redis hash 哈希数据类型 - 图7

节点的 previous_entry_length属性以字节为单位,记录了压缩列表中前一个节点的长度。 previous_entry_length属性的长度可以是1字节或者5字节。

  • 如果前一节点的长度小于254字节,那么 previous_entry_length属性的长度为1字节，前一节点的长度就保存在这一个字节里面。
  • 如果前一节点的长度大于等于254字节,那么 previous_entry_length属性的长度为5字节:其中属性的第一字节会被设置为0xFE(十进制值254),而之后的四个字节则用于保存前一节点的长度.

节点的encoding属性记录了节点的content属性所保存数据的类型以及长度。

  • 一字节、两字节或者五字节长,值的最高位为00、01或者10的是字节数组编码这种编码表示节点的 content属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录。
  • 一字节长,值的最高位以11开头的是整数编码:这种编码表示节点的content属性保存着整数值,整数值的类型和长度由编码除去最高两位之后的其他位记录。

节点的content属性负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的encoding属性决定。

Redis hash 哈希数据类型 - 图8

  • 编码的最高两位00表示节点保存的是一个字节数组。
  • 编码的后六位001011记录了字节数组的长度11。
  • content属性保存着节点的值”hello world”。
  • 编码11000000表示节点保存的是一个int16_t类型的整数值;
  • content属性保存着节点的值10086

常用操作的时间复杂度
操作 时间复杂度
创建一个新的压缩列表 O(1)
创建一个包含给定值的新节点,并将这个新节点添加到压缩列表的表头或者表尾 平均O(N)，最坏O(N^2)(可能发生连锁更新)
将包含给定值的新节点插人到给定节点之后 平均O(N)，最坏O(N^2)(可能发生连锁更新)
返回压缩列表给定索引上的节点 O(N)
在压缩列表中査找并返回包含了给定值的节点 因为节点的值可能是一个字节数组,所以检查节点值和给定值是否相同的复杂度为O(N),而查找整个列表的复杂度则为(N^2)
返回给定节点的下一个节点 O(1)
返回给定节点的前一个节点 O(1)
获取给定节点所保存的值 O(1)
从压缩列表中删除给定的节点 平均O(N)，最坏O(N^2)(可能发生连锁更新)
删除压缩列表在给定索引上的连续多个 平均O(N)，最坏O(N^2)(可能发生连锁更新)
返回压缩列表目前占用的内存字节数 O(1)
返回压缩列表目前包含的节点数量 点数量小于65535时为O(1),大于65535时为O(N)

压缩列表小结：

  • 压缩列表是Redis为节约内存自己设计的一种顺序型数据结构。
  • 压缩列表被用作列表键和哈希键的底层实现之一。
  • 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。
  • 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高。

Redis 字典

字典在Redis中的应用非常广泛，数据库与哈希对象的底层实现就是字典

散列表

散列表(哈希表)，其思想主要是基于数组支持按照下标随机访问数据时间复杂度为O(1)的特性。可是说是数组的一种扩展。假设，我们为了方便记录某高校数学专业的所有学生的信息。要求可以按照学号(学号格式为:入学时间+年级+专业+专业内自增序号，如2011 1101 0001)能够快速找到某个学生的信息。这个时候我们可以取学号的自增序号部分，即后四位作为数组的索引下标，把学生相应的信息存储到对应的空间内即可。

Redis hash 哈希数据类型 - 图9

如上图所示,我们把学号作为key,通过截取学号后四位的函数后计算后得到索引下标，将数据存储到数组中。当我们按照键值(学号)查找时，只需要再次计算出索引下标，然后取出相应数据即可。以上便是散列思想。

散列函数

上面的例子中，截取学号后四位的函数即是一个简单的散列函数。

  1. //散列函数 伪代码 
  2. int Hash(string key) {
  3.   // 获取后四位字符
  4.   string hashValue =int.parse(key.Substring(key.Length-4, 4));
  5.   // 将后两位字符转换为整数
  6.   return hashValue;
  7. }

在这里散列函数的作用就是讲key值映射成数组的索引下标。关于散列函数的设计方法有很多，如:直接寻址法、数字分析法、随机数法等等。但即使是再优秀的设计方法也不能避免散列冲突。在散列表中散列函数不应设计太复杂。

散列冲突

Redis hash 哈希数据类型 - 图10

散列函数具有确定性和不确定性：

  • 确定性：哈希的散列值不同，那么哈希的原始输入也就不同。即:key1=key2,那么hash(key1)=hash(key2)。
  • 不确定性：同一个散列值很有可能对应多个不同的原始输入。即:key1≠key2，hash(key1)=hash(key2)。

散列冲突：即key1≠key2，hash(key1)=hash(key2)的情况。散列冲突是不可避免的，如果我们key的长度为100，而数组的索引数量只有50，那么再优秀的算法也无法避免散列冲突。关于散列冲突也有很多解决办法，这里简单复习两种：开放寻址法和链表法。

开放寻址法

开放寻址法的核心思想是，如果出现了散列冲突，我们就重新探测一一个空闲位置，将其插入。比如，我们可以使用线性探测法。当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，如果遍历到尾部都没有找到空闲的位置，那么我们就再从表头开始找，直到找到为止。

Redis hash 哈希数据类型 - 图11

  • 散列表中查找元素的时候，我们通过散列函数求出要查找元素的键值对应的散列值，然后比较数组中下标为散列值的元素和要查找的元素。如果相等，则说明就是我们要找的元素；否则就顺序往后依次查找。如果遍历到数组中的空闲位置还没有找到，就说明要查找的元素并没有在散列表中。 
    1. 对于删除操作稍微有些特别，不能单纯地把要删除的元素设置为空。因为在查找的时候，一旦我们通过线性探测方法，找到一个空闲位置，我们就可以认定散列表中不存在这个数据。但是，如果这个空闲位置是我们后来删除的，就会导致原来的查找算法失效。这里我们可以将删除的元素，特殊标记为 deleted。当线性探测查找的时候，遇到标记为 deleted 的空间，并不是停下来，而是继续往下探测。
  • 线性探测法存在很大问题。当散列表中插入的数据越来越多时，其散列冲突的可能性就越大，极端情况下甚至要探测整个散列表,因此最坏时间复杂度为O(N)。在开放寻址法中，除了线性探测法，我们还可以二次探测和双重散列等方式。

链表法

链表法是一种比较常用的散列冲突解决办法,Redis使用的就是链表法来解决散列冲突。链表法的原理是:如果遇到冲突，他就会在原地址新建一个空间，然后以链表结点的形式插入到该空间。当插入的时候，我们只需要通过散列函数计算出对应的散列槽位，将其插入到对应链表中即可。

Redis hash 哈希数据类型 - 图12

负载因子与rehash

我们可以使用装载因子来衡量散列表的“健康状况”。

散列表的负载因子 = 填入表中的元素个数/散列表的长度

  • 散列表负载因子越大，代表空闲位置越少，冲突也就越多，散列表的性能会下降。
  • 对于散列表来说，负载因子过大或过小都不好，负载因子过大，散列表的性能会下降。而负载因子过小，则会造成内存不能合理利用，从而形成内存浪费。因此我们为了保证负载因子维持在一个合理的范围内，要对散列表的大小进行收缩或扩展，即rehash。散列表的rehash过程类似于数组的收缩与扩容。

开放寻址法与链表法比较

对于开放寻址法解决冲突的散列表，由于数据都存储在数组中，因此可以有效地利用 CPU 缓存加快查询速度(数组占用一块连续的空间)。但是删除数据的时候比较麻烦，需要特殊标记已经删除掉的数据。而且，在开放寻址法中，所有的数据都存储在一个数组中，比起链表法来说，冲突的代价更高。所以，使用开放寻址法解决冲突的散列表，负载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

对于链表法解决冲突的散列表,对内存的利用率比开放寻址法要高。因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。链表法比起开放寻址法，对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于1的情况。接近1时，就可能会有大量的散列冲突，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。但是，链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，而且链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这对于执行效率有一定的影响。

Redis 字典的实现

Redis字典使用散列表最为底层实现，一个散列表里面有多个散列表节点，每个散列表节点就保存了字典中的一个键值对。

Redis hash 哈希数据类型 - 图13

字典结构

  1. typedef struct dict{
  2.          //类型特定函数
  3.          void *type;
  4.          //私有数据
  5.          void *privdata;
  6.          //哈希表-见2.1.2
  7.          dictht ht[2];
  8.          //rehash 索引 当rehash不在进行时 值为-1
  9.          int trehashidx; 
  10. }dict;

type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。

  • type属性是一个指向dictType结构的指针，每个dictType用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数。
  • privdata属性则保存了需要传给给那些类型特定函数的可选参数。
  1. typedef struct dictType
  2. {
  3.          //计算哈希值的函数 
  4.          unsigned int  (*hashFunction) (const void *key);
  5.          //复制键的函数
  6.          void *(*keyDup) (void *privdata,const void *key);
  7.          //复制值的函数
  8.          void *(*keyDup) (void *privdata,const void *obj);
  9.           //复制值的函数
  10.          void *(*keyCompare) (void *privdata,const void *key1, const void *key2);
  11.          //销毁键的函数
  12.          void (*keyDestructor) (void *privdata, void *key);
  13.          //销毁值的函数
  14.          void (*keyDestructor) (void *privdata, void *obj);
  15. }dictType;
  • ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表， 一般情况下，字典只使用ht[0] 哈希表,ht[1]哈希表只会对ht[0]哈希表进行rehash时使用。
  • rehashidx记录了rehash目前的进度，如果目前没有进行rehash，值为-1。

散列表

  1. typedef struct dictht
  2. {
  3.          //哈希表数组，C语言中，*号是为了表明该变量为指针，有几个* 号就相当于是几级指针，这里是二级指针，理解为指向指针的指针
  4.          dictEntry **table;
  5.          //哈希表大小
  6.          unsigned long size;
  7.          //哈希表大小掩码，用于计算索引值
  8.          unsigned long sizemask;
  9.          //该哈希已有节点的数量
  10.          unsigned long used;
  11. }dictht;
  • table属性是一个数组，数组中的每个元素都是一个指向dict.h/dictEntry结构的指针，每个dictEntry结构保存着一个键值对
  • size属性记录了哈希表的大小，也是table数组的大小
  • used属性则记录哈希表目前已有节点(键值对)的数量
  • sizemask属性的值总是等于 size-1(从0开始)，这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面（索引下标值）。

散列表节点

  1. //哈希表节点定义dictEntry结构表示，每个dictEntry结构都保存着一个键值对。
  2. typedef struct dictEntry
  3. {
  4.          //键
  5.          void *key;
  6.          //值
  7.          union{
  8.            void *val;
  9.             uint64_tu64;
  10.             int64_ts64;
  11.             }v;
  12.          // 指向下个哈希表节点，形成链表
  13.          struct dictEntry *next;
  14. }dictEntry;

key属性保存着键值中的键，而v属性则保存着键值对中的值，其中键值(v属性)可以是一个指针，或uint64_t整数，或int64_t整数。 next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，解决键冲突问题。

Redis如何解决散列冲突

链表法

当有两个或以上的键被分配到散列表数组同一个索引上时，就发生了键冲突。Redis使用链表法解决散列冲突。每个散列表节点都有一个next指针，多个散列表节点next可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以使用这个单向链表连接起来。

Redis hash 哈希数据类型 - 图14

PS：

当键k0和k1的经过散列函数得到索引值都为1时，就会使用next指针将两个节点连接起来。而由于节点没有指向链尾的指针，因此新的节点总是插入到链表的头部，排在已有节点的前面。

Redis rehash

随着操作的进行，散列表中保存的键值对会也会不断地增加或减少，为了保证负载因子维持在一个合理的范围，当散列表内的键值对过多或过少时，内需要定期进行rehash，以提升性能或节省内存。Redis的rehash的步骤如下:

Redis hash 哈希数据类型 - 图15

  1. 为字典的**ht[1]**散列表分配空间，这个空间的大小取决于要执行的操作以及**ht[0]**当前包含的键值对数量(即:**ht[0].used**的属性值)
    • 扩展操作：ht[1]的大小为 第一个大于等于ht[0].used*2的2的n次方幂。如:ht[0].used=3则ht[1]的大小为8，ht[0].used=4则ht[1]的大小为8
    • 收缩操作: ht[1]的大小为 第一个大于等于ht[0].used的2的n次方幂

Redis hash 哈希数据类型 - 图16

  1. 将保存在**ht[0]**中的键值对重新计算键的散列值和索引值，然后放到**ht[1]**指定的位置上

Redis hash 哈希数据类型 - 图17

  1. 将**ht[0]**包含的所有键值对都迁移到了**ht[1]**之后，释放**ht[0]**,将**ht[1]**设置为**ht[0]**,并创建一个新的**ht[1]**哈希表为下一次**rehash**做准备

Redis hash 哈希数据类型 - 图18

rehash操作需要满足以下条件:

  • 服务器目前没有执行BGSAVE(rdb持久化)命令或者BGREWRITEAOF(AOF文件重写)命令，并且散列表的负载因子大于等于1。
  • 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且负载因子大于等于5。
  • 当负载因子小于0.1时，程序自动开始执行收缩操作。

Redis这么做的目的是基于操作系统创建子进程后写时复制技术，避免不必要的写入操作

渐进式 rehash

对于rehash我们思考一个问题如果散列表当前大小为 1GB，要想扩容为原来的两倍大小，那就需要对 1GB 的数据重新计算哈希值，并且从原来的散列表搬移到新的散列表。这种情况听着就很耗时，而生产环境中甚至会更大。为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。当负载因子触达阈值之后，只申请新空间，但并不将老的数据搬移到新散列表中。当有新数据要插入时，将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次一次性数据搬移，插入操作就都变得很快了。

Redis为了解决这个问题采用渐进式**rehash**方式。以下是Redis渐进式rehash的详细步骤:

  1. 为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
  2. 在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ，表示 rehash 工作正式开始。
  3. 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
  4. 随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

说明:

1.因为在进行渐进式 rehash 的过程中，字典会同时使用 **ht[0]** 和 **ht[1]** 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。

2. 在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 **ht[1]** 里面，而 **ht[0]** 则不再进行任何添加操作：这一措施保证了 **ht[0]** 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表

Redis 字段操作时间复杂度

操作 时间复杂度
创建一个新字典 O(1)
将给定的键值对添加到字典内 O(1)
将给定的键值对添加到字典内，如果键存在则替换之 O(1)
返回给定键的值 O(1)
从字典中随机返回一个键值对 O(1)
从字典中删除给定键所对应的键值对 O(1)
释放给定字典以及字典中包含的键值对 O(N)，N为字典包含的键值对的数量

Redis字典总结：

  1. 字典在redis中广泛应用，包括数据库和hash数据结构。
  2. 每个字典有两个哈希表，一个是正常使用，一个用于rehash期间使用。
  3. 当redis计算哈希时，采用的是MurmurHash2哈希算法。
  4. 哈希表采用链表法解决散列冲突，被分配到同一个地址的键会构成一个单向链表。
  5. 在rehash对哈希表进行扩展或者收缩过程中，会将所有键值对进行迁移，并且这个迁移是渐进式的迁移。

大佬原文，redis对象hash/)