面试题：Redis键冲突解决基础及效率提升方法

Question

在Redis中，简要阐述常见的键冲突解决方法，并说明其中一种方法如何提升解决效率。

Answer 1

常见键冲突解决方法

1. 开放定址法：当发生键冲突时，通过某种探测算法，在散列表中寻找下一个空闲位置来存储新元素。例如线性探测法，就是从冲突位置开始，依次往后探测，直到找到空闲位置。
2. 链地址法（哈希链表法）：在哈希表每个槽位维护一个链表，当键冲突发生时，将冲突的元素插入到对应槽位的链表中。
3. 再哈希法：准备多个哈希函数，当使用第一个哈希函数发生冲突时，就换用下一个哈希函数计算地址。

以链地址法提升解决效率的方式

• 优化链表结构：采用更高效的链表结构，如双向链表，在查找、删除元素时可以提高效率，因为双向链表可以双向遍历，对于某些操作无需从链表头开始遍历。
• 动态扩容：当链表长度超过一定阈值时，对哈希表进行扩容，重新计算元素的哈希值并分配到新的槽位，这样可以降低每个链表的长度，减少查找元素的时间复杂度。例如Redis中使用的字典结构，会在负载因子过高时进行扩容操作，提升整体性能。