Redis源代码分析：哈希表实现与扩展

"Redis源代码分析（上）1" 在Redis中，哈希表（hash table）是核心数据结构之一，用于实现键值对（Key-Value）存储以及内部数据结构和命令函数映射。Redis选择了哈希表作为基础，虽然牺牲了范围查询等功能，但通过高效的哈希函数实现了快速查询，同时代码实现简洁。哈希表的实现主要集中在`src/dict.c`和`src/dict.h`两个文件中。 `dict`结构体是Redis中的哈希表主体，它包含了两个`dictht`（哈希表）结构，这是为了rehash过程中平滑迁移数据。`dictht`是一个中间数据结构，它的`buckets`数组存储了哈希后的键值对。当rehash发生时，可以逐步将旧哈希表的数据迁移到新哈希表，避免在高负载期间进行大量一次性操作。 哈希函数计算键的哈希值，然后与`sizemask`进行位与运算，得到的索引用于定位`buckets`数组中的`dictEntry`。`dictEntry`包含键值对和一个`next`指针，用于处理哈希冲突时形成链表。查询操作可能需要遍历链表，因此时间复杂度为O(N)，而插入操作由于总是插入链表头部，其时间复杂度为O(1)。 哈希表的`used`字段记录了已插入键的总数，即`dictEntry`的数量。当键不断增加，如果不改变`buckets`大小，每个桶的链表会变长，查找和删除的效率会降低。为了解决这个问题，Redis定义了一个阈值`dict_force_resize_ratio`（默认为5），当`used/size`超过这个比例时，系统会触发`expand`和`rehash`操作，扩大哈希表的大小，以保持良好的性能。 在rehash过程中，Redis会逐步将旧哈希表中的键值对转移到新哈希表，这样可以在不影响正常服务的情况下完成数据迁移。随着Redis的发展，源代码分析有助于深入理解其内部机制，提升优化和调试能力。