面试题：Redis的字典实现中如何优化键冲突对性能的影响

Question

已知Redis在处理大量键值对时，键冲突可能对性能产生显著影响。请详细分析Redis在字典实现层面，是通过哪些机制（如哈希函数设计、扩容策略等）来优化键冲突对性能造成的负面效应的。

Answer 1

哈希函数设计

Redis采用MurmurHash2哈希函数。该函数计算速度快，能在不同输入数据下，均匀地将键映射到哈希表的不同位置。这使得键在哈希表中的分布更为均匀，减少键冲突的概率。比如对于不同的字符串键，MurmurHash2能尽可能将它们映射到哈希表不同槽位，降低多个键映射到同一槽位导致冲突的可能性。

链地址法解决冲突

当出现键冲突，即不同键经哈希函数计算得到相同哈希值时，Redis使用链地址法。在哈希表的每个槽位上，实际是一个链表的头指针。当多个键映射到同一槽位，这些键值对以链表节点形式依次串联在该槽位对应的链表上。虽然存在冲突，但通过链表能存储多个键值对，避免数据丢失。

扩容策略

1. 触发条件：
   • 当哈希表的负载因子（已使用的槽位数与哈希表总槽位数的比值）大于1且Redis没有在执行BGSAVE或BGREWRITEAOF命令时，会触发扩容。负载因子过高意味着哈希表过于拥挤，键冲突概率大增，此时扩容可改善性能。
   • 当哈希表的负载因子大于5时，无论是否在执行持久化命令，都会强制扩容。这是为了避免哈希表过度拥挤，严重影响性能。
2. 扩容过程：
   • 分配新的更大的哈希表空间，新哈希表的大小通常是原哈希表大小的2倍。
   • 将旧哈希表中的所有键值对重新计算哈希值并插入到新哈希表中。这个过程会逐步进行，避免一次性操作影响Redis性能。例如在渐进式rehash过程中，会同时保留新旧两个哈希表，在处理客户端请求时，会在新旧哈希表上同时查找键值对，并逐步将旧哈希表数据迁移到新哈希表，直到旧哈希表为空，然后释放旧哈希表空间。

缩容策略

1. 触发条件：当哈希表的负载因子小于0.1时，会触发缩容。负载因子过小说明哈希表空间利用率低，存在大量空闲槽位，此时缩容可节省内存。
2. 缩容过程：与扩容类似，分配新的更小的哈希表空间，通常为原哈希表大小的1/2，然后将旧哈希表中的键值对重新计算哈希值并插入到新哈希表中，同样采用渐进式方式进行，避免对Redis性能产生过大影响。