面试题：Redis哈希对象在内存中的结构是怎样的？

Question

请详细描述Redis哈希对象在内存中的存储结构，以及这种结构对于数据读写操作的影响。

Answer 1

Redis哈希对象内存存储结构

1. ziplist（压缩列表）：
   • 当哈希对象中的键值对数量较少（默认小于512个，可通过hash-max-ziplist-entries配置），并且所有键和值的长度都较短（默认单个键值长度小于64字节，可通过hash-max-ziplist-value配置）时，Redis会使用ziplist来存储哈希对象。
   • ziplist是一种紧凑的、连续内存布局的数据结构。它由一系列entry组成，每个entry存储一个键或值。在ziplist的开头有一个zlbytes字段记录整个ziplist占用的字节数，然后是zltail记录尾节点距离起始地址的偏移量，还有zllen记录entry的数量。
   • 例如，对于哈希对象{"name":"John","age":"30"}，在ziplist中会按顺序存储"name"、"John"、"age"、"30"这些entry。
2. hashtable（哈希表）：
   • 当哈希对象不符合ziplist的条件（键值对数量较多或有较长的键值）时，会使用hashtable存储。
   • Redis的hashtable由dict结构组成，它包含两个哈希表ht[0]和ht[1]（用于rehash）。每个哈希表是一个数组，数组中的每个元素是一个指向dictEntry结构的指针。
   • dictEntry结构存储了键值对，它包含键、值、指向下一个dictEntry的指针（用于解决哈希冲突，采用链地址法）。例如，对于哈希对象{"key1":"value1","key2":"value2"}，key1和key2会通过哈希函数计算出索引值，存储在哈希表数组对应的位置，如果发生冲突，会通过指针链接到下一个dictEntry。

对数据读写操作的影响

1. ziplist对读写操作的影响：
   • 读操作：
     • 由于是紧凑的连续内存结构，在读取少量键值对时，缓存命中率较高，读性能较好。但如果要查找特定的键值对，需要从头开始遍历ziplist，时间复杂度平均为O(n)，在键值对数量较多时性能会下降。
     • 例如，要查找"age"对应的值，需要从ziplist头部开始依次比较每个entry的键。
   • 写操作：
     • 插入和删除操作可能会导致ziplist的重新分配内存。因为ziplist是连续内存结构，插入或删除一个entry可能需要移动后续的所有entry，在键值对较多时，性能开销较大。
     • 例如，在已有{"name":"John","age":"30"}的ziplist中插入{"city":"New York"}，可能需要移动"age"和"30"这两个entry的位置。
2. hashtable对读写操作的影响：
   • 读操作：
     • 基于哈希表的结构，通过哈希函数可以快速定位键值对所在的哈希表数组位置，平均时间复杂度为O(1)，读性能非常高效，尤其是在键值对数量较多时优势明显。即使发生哈希冲突，通过链地址法查找冲突链表中的元素，平均时间复杂度也接近O(1)。
     • 例如，要查找"key1"对应的值，通过哈希函数计算出索引，直接定位到哈希表数组位置，若有冲突再遍历链表查找。
   • 写操作：
     • 插入操作平均时间复杂度也是O(1)，非常高效。但在哈希表元素逐渐增多，负载因子超过一定阈值（默认1）时，会触发rehash操作，将ht[0]的数据重新分配到ht[1]，这个过程会消耗较多的CPU和内存资源，导致写性能短暂下降。
     • 删除操作同样平均时间复杂度为O(1)，但删除后可能会导致哈希表空间利用率降低，不过Redis有机制会在适当的时候进行内存优化。