Redis是如何避免“数组+链表”的过长问题

本文主要是介绍Redis是如何避免“数组+链表”的过长问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、扩展和收缩

二、使用高质量的哈希函数

三、使用跳跃表（skiplist）或其他数据结构

四、哈希表分片

一、扩展和收缩

Redis通过动态调整哈希表的大小来解决“数组+链表”的长度问题，这涉及到两个过程：扩展(Expand)和收缩(Shrink)。

扩展:
- 当哈希表的负载因子(load factor)超过一个阈值时，Redis会进行扩展操作。
- 负载因子是哈希表已存储的元素数量与哈希表大小的比值。
- 扩展操作包括分配一个新的更大的哈希表，并逐渐将旧表中的所有键值对rehash到新表中。
收缩:
- 相对地，当负载因子低于另一个阈值时，Redis会执行收缩操作，减少哈希表的大小。
- 这通常发生在删除大量键值对后，为了节省内存空间，Redis会将键值对rehash到一个更小的哈希表中。

负载因子和rehash

负载因子的计算:
- 负载因子 = 哈希表中的元素数量 / 哈希表的大小
- 当负载因子太高时，意味着发生哈希冲突的可能性增加，链表会变得较长，影响性能。
- 当负载因子太低时，意味着内存使用不够高效。
- 默认扩展负载因子:
  - 在没有进行BGSAVE或BGREWRITEAOF操作时，负载因子超过1时进行扩展。
  - 如果正在进行BGSAVE或BGREWRITEAOF操作，则负载因子阈值提高到5，即负载因子超过5时进行扩展。这意味着在正常情况下，当哈希表的负载因子超过1时，Redis就会触发扩展操作。但是，如果Redis正在进行磁盘写操作，如BGSAVE或BGREWRITEAOF，为了避免在磁盘IO已经很高的情况下进一步增加内存重分配的负担，它会提高扩展操作的负载因子阈值到5。这样可以在一定程度上平衡内存使用和磁盘IO之间的性能。
- 当哈希表的负载因子小于0.1时，Redis会进行收缩操作。
rehash过程:
- rehash是将所有键值对从旧的哈希表移动到新的哈希表的过程。
- Redis使用渐进式rehash，它不是一次性完成，而是分多次进行，以避免长时间的阻塞。