链表
列表键的底层实现之一就是使用链表
链表节点结构
链表结构
链表特征
- 双端：链表节点带有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] 最终变为空表。