面试题：Redis字典在缓存系统中如何实现数据快速查询

Question

在缓存系统里使用Redis字典，简述它是怎样实现数据快速查询的，以及其底层数据结构对查询效率的影响。

Answer 1

Redis字典数据快速查询实现

1. 哈希表结构：Redis字典底层使用哈希表实现。哈希表由数组和链表组成，每个数组元素称为哈希桶。当插入一个键值对时，通过哈希函数计算键的哈希值，再对哈希表大小取模，得到该键值对应放入的哈希桶位置。这样，理论上在理想情况下，通过一次哈希计算和一次数组访问就能定位到对应的值，时间复杂度接近O(1)。
2. 解决哈希冲突：当不同键通过哈希函数计算得到相同的哈希值（哈希冲突）时，Redis采用链地址法解决。即每个哈希桶是一个链表头指针，冲突的键值对会以链表节点的形式挂在该链表上。在查询时，首先通过哈希值定位到哈希桶，若链表上只有一个节点，可直接获取值；若有多个节点，则需遍历链表，依次比较键，直到找到目标键对应的值。

底层数据结构对查询效率的影响

1. 哈希表负载因子：负载因子 = 哈希表已保存节点数量 / 哈希表大小。当负载因子过大时，意味着哈希表中节点过多，哈希冲突的概率会增加，导致链表变长，查询时遍历链表的时间增加，查询效率降低。Redis会在负载因子超过一定阈值（如1.5）时进行rehash操作，重新分配哈希表空间，降低负载因子，提高查询效率。
2. rehash操作：Redis的rehash不是一次性完成的，而是渐进式的。在进行rehash时，会同时保留新旧两个哈希表，在后续的字典操作（如插入、删除、查找）中逐步将旧哈希表中的键值对迁移到新哈希表。这既避免了一次性rehash带来的性能开销，又保证了在rehash过程中字典操作的正常进行，不过在一定程度上会使单次操作的时间略有增加。
3. 链表长度：链表长度直接影响哈希冲突时的查询效率。若链表过长，查询时间复杂度会从接近O(1)退化为O(n)。因此，合理设置哈希表大小、及时进行rehash以及优化哈希函数，减少哈希冲突，能有效控制链表长度，提高查询效率。