【Redis】链表和字典

链表

列表键的底层实现之一就是使用链表

链表节点结构

链表结构

链表特征

• 双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的复杂度都是O(1)
• 无环：表头节点的prev 指针和表尾节点的next 指针都指向NULL，对链表的访问以NULL为终点
• 带表头指针和表尾指针：通过list结构的head 指针和tail 指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)
• 带链表长度计数器：程序使用list 结构的len 属性来对list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为O(1)
• 多态

字典

简单的说，就是key=>value键值对的抽象数据结构

哈希键的底层实现之一

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对

字典结构定义

• 第一：type属性和privdata属性是针对不同类型的键值对，为创建多态字典而设置的
• 第二：type属性是一个指向dictType结构的指针，每一个dictType 结构保存了一些特定的函数
• 第三：ht 属性是一个只包含两个项的数组，数组中的每个项都是一个dictht 哈希表，一般情况下，字典只使用ht[0] 哈希表，ht[1] 哈希表只会对ht[0]哈希表进行rehash 时使用。
• 第四：rehashidx属性的含义是 -1 代表着没有进行rehash ,反之记录着rehash 进度。

哈希表结构定义

简单说明一下，sizemask这个属性，这个属性和哈希值一起决定一个键应该被放到table 数组的哪个索引上面

哈希表节点结构定义

说明一下：next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决哈希键冲突的问题

哈希算法

redis计算哈希值和索引值的方法

• 第一步：使用字典设置的哈希函数，计算键key的哈希值
  hash = dict->type->hashFunction(key)
• 第二步：使用哈希表的sizemask属性和哈希值，计算出索引值，根据情况不同，ht[x] 可以是 ht[0] 或者 ht[1]
  index = hash & dict->ht[x].sizemask

键冲突

当两个或以上数量的键被分配到了哈希表数组的同一个索引上时，我们称为键冲突

redis的哈希表使用链地址法来解决键冲突，每个哈希表节点都有一个next 指针，多个哈希表节点可以用nex指针构成一个单向链表，这就就解决了键冲突

需要说明一下：新增加的节点总是添加到链表的表头位置，就是排在已有节点前面。

rehash

当哈希表保存的键值对达到一定的范围，程序会对哈希表的大小进行相应的扩展或者收缩

redis进行rehash的步骤

• 第一步：为字典的ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，和ht[0].used 属性的值
  如果是扩展操作，那么ht[1] 的大小为第一个大于等于ht[0].used*2的2的n次幂
  如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used 的 2的n次幂
• 第二步：将保存在ht[0] 中的所有键值对rehash 到ht[1] 上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1] 哈希表的指定位置上
• 第三步：当ht[0] 包含的所有键值对都迁移到了ht[1] 之后（ht[0] 变为空表）,释放ht[0] ,将ht[1] 设置为ht[0]，并为ht[1] 新创建一个空白哈希表。

渐进式rehash

使用rehash 一次性将很多键值对全部rehash到ht[1]的话，可能会导致一段时间内停止服务，这个是在生产环境决不允许的，所以采用渐进式rehash

上面属性存在一个rehashidx 索引计数器，没有进行rehash 时 ,rehashidx=-1, 当进行rehash 时，rehashidx=0，表示rehash 工作正式开始。当哈希表节点上的一个索引的键值对rehash到ht[1] , 程序会将rehashidx 的值加1，当ht[0] 全部同步到ht[1] 时, rehashidx = -1。

渐进式rehash 的好处在于采用分而治之的方式，避免了集中式rehash 带来的庞大计算量。

渐进式rehash 执行期间的哈希表操作

渐进式rehash 执行期间的哈希表操作，会同时使用ht[0]和ht[1]两个哈希表，字典的删除，查询，更新，会在两个表上进行，例如，需要在字典中查询某个值时，会先到ht[0] 上查询，没查到，会到ht[1] 上查询。但是在字典上新增，则会直接新增到ht[1],这样保证了ht[0] 上只会减少不会增加，随着rehash的执行ht[0] 最终变为空表。