redis hashtable 的sizemask理解

在 Redis 的哈希表实现中，index = hash & dict->ht[0].sizemask 是计算键值对应存储位置的核心操作。这个操作看起来简单，但背后涉及哈希表的内存布局和性能优化策略。我们通过以下步骤逐步解析其原理：

一、哈希表的设计目标

1. 快速定位桶（Bucket）：通过键的哈希值直接找到对应的存储位置，时间复杂度接近 O(1)。
2. 均匀分布键值对：减少哈希冲突，避免链表过长导致性能下降。
3. 高效计算：避免使用耗时的取模运算（%）。

二、哈希表大小（size）的特殊性

Redis 的哈希表大小 size 始终是 2 的幂（如 4, 8, 16, 32 等）。这种设计有两个关键优势：

1. 快速计算索引：用位运算（&）替代取模运算（%）。
2. 均匀分布哈希值：减少哈希冲突的概率。

三、sizemask 的作用

• 定义：sizemask = size - 1
• 二进制特征：当 size 是 2 的幂时，sizemask 的二进制形式为全 1。
例如：
• size = 8 → sizemask = 7 → 二进制 0111
• size = 16 → sizemask = 15 → 二进制 1111

四、索引计算原理

1. 取模运算的替代方案

传统哈希索引计算使用取模运算：

index = hash % size; // 例如 hash=10, size=8 → index=2

但取模运算在计算机中效率较低（涉及除法操作）。

2. 位运算优化

当 size 是 2 的幂时，可以用位运算替代：

index = hash & (size - 1); // 即 hash & sizemask

为什么这等价于取模？
• 因为 size 是 2 的幂，size - 1 的二进制形式为全 1（例如 size=8 对应 sizemask=7，二进制 0111）。
• hash & sizemask 相当于保留哈希值的低 n 位（n = log2(size)），结果范围是 0 ≤ index < size，与 hash % size 等价。

五、具体示例

假设哈希表大小 size = 8（即 sizemask = 7），哈希值 hash = 10：

结果与 10 % 8 = 2 完全一致，但位运算比取模运算快得多。

六、哈希表扩容时的行为

当哈希表需要扩容（例如从 size=8 扩容到 size=16）：

1. 新 sizemask = 15（二进制 1111）。
2. 哈希值相同的键会分散到更多桶中：
   • 例如原哈希值 10（二进制 1010）在 size=8 时索引为 2。
   • 扩容后 size=16，索引变为 10 & 15 = 10。

七、为什么必须保证 size 是 2 的幂？

如果 size 不是 2 的幂，sizemask 的二进制形式将包含 0，导致部分索引永远无法被映射到。
例如：
• size = 7 → sizemask = 6（二进制 0110）
• 哈希值 5（二进制 0101）→ 0101 & 0110 = 0100（索引 4）
• 哈希值 3（二进制 0011）→ 0011 & 0110 = 0010（索引 2）
• 索引 1、3、5、7 永远无法被访问，导致哈希分布不均。

八、性能对比

在 Redis 这种高性能场景下，位运算的优势显著。

九、总结

• sizemask = size - 1：当 size 是 2 的幂时，此公式成立。
• hash & sizemask：快速计算键的存储位置，避免取模运算。
• 设计优势：内存对齐、哈希均匀、计算高效。

这种设计是 Redis 哈希表高性能的核心保障，结合渐进式 rehash 机制，使得 Redis 能够高效处理大规模键值对存储。