redis解决哈希冲突

链式哈希。每个哈希表节点都有一个 next 指针用于指向下一个哈希表节点，因此多个哈希表节点可以用next指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来，这样就解决了哈希冲突。

局限性：随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)。要想解决问题就需要进行rehash，也就是对哈希表大小进行扩展。

rehash实现

在实际使用哈希表时，Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。

在正常服务请求阶段，插入的数据都会写入到「哈希表 1」，此时的「哈希表 2 」 并没有被分配空间。随着数据逐步增多，触发rehash，这个过程分为三步：

  • 给「哈希表 2」 分配空间，一般会比「哈希表 1」 大 2 倍；
  • 将「哈希表 1 」的数据迁移到「哈希表 2」 中；
  • 迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」 设置为「哈希表 1」，然后在「哈希表 2」 新创建一个空白的哈希表，为下次 rehash 做准备。

局限性：第二步如果「哈希表 1 」数据量非常大，那么在迁移至「哈希表 2 」时因为会涉及大量的数据拷贝，此时可能会对Redis造成阻塞。可用渐进式rehash。

渐进式rehash实现

数据迁移的工作不再是一次性迁移完成，而是分多次迁移。

  • 给「哈希表 2」 分配空间；
  • 在 rehash 期间，每次哈希表元素进行增删查改时，Redis 除了会执行对应的操作还会顺序将「哈希表 1 」中索引位置上的所有kv迁移到「哈希表 2」 上
  • 随着处理客户端发起的哈希表操作请求数量越多，最终会把「哈希表 1 」的所有 kv迁移到「哈希表 2」，完成 rehash 操作

rehash触发条件

跟负载因子有关系（负载因子=哈希表已保存节点数量/哈希表大小）触发条件俩个：

  • 负载因子>= 1且Redis没在执行RDB快照或AOF重写时
  • 负载因子>=5时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作