面试题：Redis解决字典键冲突的基本方法有哪些

Question

在Redis中，当使用字典结构存储数据时，不可避免会遇到键冲突问题。请阐述Redis解决字典键冲突所采用的基本方法，并简要说明每种方法的原理和特点。

Answer 1

开放定址法

• 原理：当发生键冲突时，通过一个探测函数在哈希表中寻找下一个空的哈希桶。例如线性探测，就是从发生冲突的位置开始，依次往后探测，直到找到一个空桶。
• 特点：
  • 优点：实现简单，不需要额外的数据结构来存储冲突的元素。
  • 缺点：容易产生聚集现象，即连续的多个位置都被占用，导致后续查找时间增加。

链地址法（哈希链表法）

• 原理：Redis采用链地址法解决字典键冲突。每个哈希桶中不再只是存储一个元素，而是一个链表的头指针。当有多个键映射到同一个哈希桶时，这些键值对就通过链表连接起来。
• 特点：
  • 优点：
    • 处理冲突简单高效，在平均情况下，查找、插入和删除操作的时间复杂度都是O(1)。
    • 链表的长度不受限制，适合存储大量数据。
  • 缺点：需要额外的指针空间来维护链表，对于内存比较敏感的场景不太友好。