面试题：Redis字典实现中内存分配的基本方式有哪些

Question

在Redis字典实现里，简述其内存分配的基本方式，例如使用何种内存分配函数，以及这些函数在不同场景下是如何被调用的。

Answer 1

内存分配函数

Redis 通常使用 zmalloc 作为内存分配函数，zmalloc 是对系统标准内存分配函数（如 malloc、calloc、realloc 等）的封装。在一些系统上，还会集成 jemalloc 这样的高性能内存分配器，通过宏定义 USE_JEMALLOC 来启用。

不同场景下的调用

1. 创建新字典：
   • 当创建一个新的 Redis 字典（dict）时，会调用 zmalloc 分配一个 dict 结构体的内存空间。这个结构体包含了哈希表、哈希表大小、已有元素数量等重要信息。
   • 同时，会为哈希表分配内存，哈希表是一个数组，数组中的每个元素是一个指向链表头的指针（采用链地址法解决哈希冲突）。这里会根据初始设定的哈希表大小，使用 zmalloc 分配相应大小的数组内存。
2. 插入新元素：
   • 在向字典插入新元素时，首先计算元素的哈希值，确定其在哈希表中的位置。
   • 如果该位置的链表为空，会使用 zmalloc 分配一个新的链表节点（dictEntry）来存储新元素，并将其插入到链表头。
   • 如果哈希表的负载因子超过一定阈值（默认为 1），会调用 dictExpand 函数进行哈希表扩展。此时会使用 zmalloc 分配一个更大的哈希表数组，并将旧哈希表中的所有元素重新计算哈希值并插入到新哈希表中，之后释放旧哈希表的内存（通过 zfree，它是对系统 free 的封装）。
3. 删除元素：
   • 从字典中删除元素时，先找到对应的链表节点，删除该节点（通过 zfree 释放该节点的内存）。
   • 如果删除元素后哈希表的负载因子过低（小于 0.1），且哈希表大小大于 dict_force_resize_ratio（默认为 4），会调用 dictResize 函数进行哈希表收缩。这涉及到重新分配一个较小的哈希表数组，将旧表元素重新插入新表，并释放旧表内存。
4. 释放字典：
   • 当释放整个字典时，会遍历哈希表数组中的每个链表，使用 zfree 释放每个链表节点的内存。
   • 然后使用 zfree 释放哈希表数组和 dict 结构体本身的内存。