浅析对redis hashtable 的sizemask理解_Redis

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

一、哈希表的设计目标

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

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

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

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

三、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：

步骤	二进制表示	结果
`hash = 10`	`1010`	10
`sizemask = 7`	`0111`	7
`hash & sizemask`	`1010 & 0111 = 0010`	2

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

六、哈希表扩容时的行为

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

新 sizemask = 15（二进制 1111）。哈希值相同的键会分散到更多桶中：
• 例如原哈希值 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 永远无法被访问，导致哈希分布不均。