面试题：Redis解决键冲突动态调整方案之基础原理

Question

请简要阐述Redis在面对键冲突时，常用的动态调整方案的基本原理，例如哈希表扩容相关原理。

Answer 1

哈希表扩容原理

1. 触发条件：
   • Redis的哈希表有两个参数load_factor = 已使用的哈希桶数量 / 哈希桶总数量。当load_factor超过一定阈值（如server.hz为10时，默认阈值是1.5，server.hz为1时，默认阈值是5）时，会触发哈希表扩容。
   • 另外，当Redis执行BGREWRITEAOF或BGSAVE命令时，如果哈希表的load_factor超过1，也可能触发扩容，目的是减少写时复制（COW）带来的内存消耗。
2. 扩容过程：
   • 创建新哈希表：创建一个大小为原哈希表2倍的新哈希表（如果是在执行BGREWRITEAOF或BGSAVE时触发扩容，新哈希表大小为原哈希表的1.5倍）。
   • 重新计算哈希值和索引：遍历原哈希表中的所有键值对，对每个键重新计算其哈希值，并根据新哈希表的大小确定其在新哈希表中的索引位置。
   • 迁移数据：将原哈希表中的键值对逐个迁移到新哈希表的相应位置。为了避免在迁移过程中阻塞主线程，Redis采用渐进式rehash方式，即每次处理客户端请求时，从原哈希表中迁移一小部分数据到新哈希表，直到全部迁移完成，此时原哈希表被释放。

链地址法处理冲突

1. 基本原理：在哈希表的每个桶（bucket）中，并非只存储一个键值对，而是存储一个链表头指针。当发生键冲突时，即不同的键计算出相同的哈希值指向同一个桶时，这些键值对会被存储在该桶对应的链表中。
2. 查找过程：在查找某个键时，先根据键计算哈希值确定桶位置，然后遍历该桶对应的链表，逐个比较链表节点中的键，找到目标键后返回对应的值。这种方法使得哈希表可以动态适应键冲突的情况，只要链表不太长，查找性能仍能保持在可接受范围内。