面试题：Redis字典结构如何影响内存管理

Question

请阐述Redis字典采用的哈希表结构，以及这种结构在插入、删除和查找操作时，对内存管理方面的影响，例如如何分配和释放内存空间，如何处理哈希冲突等情况。

Answer 1

Redis字典哈希表结构

Redis的字典采用了链地址法（separate chaining）的哈希表结构。具体来说，哈希表由一个数组构成，数组中的每个元素是一个指向链表表头的指针。链表中的每个节点保存了键值对。哈希表结构定义如下：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

其中，table 是一个指向数组的指针，数组中每个元素为 dictEntry*，即指向链表表头的指针；size 为哈希表大小，也就是 table 数组的长度；sizemask 是 size - 1，用于计算哈希值的索引位置；used 记录哈希表中已使用的节点数量。

插入操作对内存管理的影响

1. 内存分配：
   • 当插入新的键值对时，如果哈希表当前负载因子（used / size）过高（默认负载因子大于1且没有执行过 rehash 操作），会进行 rehash 操作，重新分配更大的哈希表空间。新哈希表大小通常为原大小的2倍。
   • 为新的 dictEntry 节点分配内存，每个 dictEntry 结构如下：

   typedef struct dictEntry {
       void *key;
       union {
           void *val;
           uint64_t u64;
           int64_t s64;
           double d;
       } v;
       struct dictEntry *next;
   } dictEntry;
   

   2. 处理哈希冲突： 如果发生哈希冲突（不同键计算出相同的哈希索引），新的 dictEntry 节点会被插入到对应索引位置链表的表头。这种方式实现简单，在冲突较少时性能较好。

删除操作对内存管理的影响

1. 内存释放：
   • 当删除一个键值对时，首先找到对应的 dictEntry 节点，从链表中移除该节点。
   • 释放 dictEntry 节点占用的内存。如果该键值对的键和值是动态分配的内存，也需要释放相应的内存。
   • 在删除操作后，如果哈希表的负载因子过低（默认小于0.1），会进行 rehash 操作，缩小哈希表的大小，释放多余的内存空间。

查找操作对内存管理的影响

查找操作本身一般不直接涉及内存的分配和释放。它通过计算键的哈希值得到索引位置，然后在对应的链表中查找匹配的键。如果找到，则返回对应的值；如果没找到，则返回空。但在一些极端情况下，如果在查找过程中触发了 rehash 操作（例如在查找前因负载因子过高而进行 rehash），会涉及到内存的重新分配和数据迁移，和插入操作中 rehash 的内存管理类似。