在 Redis 的哈希表实现中，

1. index = hash & dict->ht[0].sizemask

复制代码

是计算键值对应存储位置的核心操作。这个操作看起来简单，但背后涉及哈希表的内存布局和性能优化策略。我们通过以下步骤逐步解析其原理：

一、哈希表的设计目标

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

  复制代码
  ）。
  

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

Redis 的哈希表大小

1. size

复制代码

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

• 快速计算索引：用位运算（
  1. &

  复制代码
  ）替代取模运算（
  1. %

  复制代码
  ）。
  
• 均匀分布哈希值：减少哈希冲突的概率。
  

三、sizemask 的作用

• 定义：

1. sizemask = size - 1

复制代码

• 二进制特征：当

1. size

复制代码

是 2 的幂时，

1. sizemask

复制代码

的二进制形式为全 1。
例如：
•

1. size = 8

复制代码

→

1. sizemask = 7

复制代码

→ 二进制

1. 0111

复制代码

•

1. size = 16

复制代码

→

1. sizemask = 15

复制代码

→ 二进制

1. 1111

复制代码

四、索引计算原理


1. 取模运算的替代方案

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

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

复制代码

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

2. 位运算优化

当

1. size

复制代码

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

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

复制代码

为什么这等价于取模？
• 因为

1. size

复制代码

是 2 的幂，

1. size - 1

复制代码

的二进制形式为全 1（例如

1. size=8

复制代码

对应

1. sizemask=7

复制代码

，二进制

1. 0111

复制代码

）。
•

1. hash & sizemask

复制代码

相当于保留哈希值的低

1. n

复制代码

位（

1. n = log2(size)

复制代码

），结果范围是

1. 0 &amp;le; index < size

复制代码

，与

1. hash % size

复制代码

等价。

五、具体示例

假设哈希表大小

1. size = 8

复制代码

（即

1. sizemask = 7

复制代码

），哈希值

1. hash = 10

复制代码

：
步骤二进制表示结果

1. hash = 10

复制代码

1. 1010

复制代码

10

1. sizemask = 7

复制代码

1. 0111

复制代码

7

1. hash &amp; sizemask

复制代码

1. 1010 &amp; 0111 = 0010

复制代码

2结果与

1. 10 % 8 = 2

复制代码

完全一致，但位运算比取模运算快得多。

六、哈希表扩容时的行为

当哈希表需要扩容（例如从

1. size=8

复制代码

扩容到

1. size=16

复制代码

）：
新

1. sizemask = 15

复制代码

（二进制

1. 1111

复制代码

）。哈希值相同的键会分散到更多桶中：
&amp;bull; 例如原哈希值

1. 10

复制代码

（二进制

1. 1010

复制代码

）在

1. size=8

复制代码

时索引为

1. 2

复制代码

。
&amp;bull; 扩容后

1. size=16

复制代码

，索引变为

1. 10 &amp; 15 = 10

复制代码

。

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

如果

1. size

复制代码

不是 2 的幂，

1. sizemask

复制代码

的二进制形式将包含 0，导致部分索引永远无法被映射到。
例如：
&amp;bull;

1. size = 7

复制代码

&amp;rarr;

1. sizemask = 6

复制代码

（二进制

1. 0110

复制代码

）
&amp;bull; 哈希值

1. 5

复制代码

（二进制

1. 0101

复制代码

）&amp;rarr;

1. 0101 &amp; 0110 = 0100

复制代码

（索引 4）
&amp;bull; 哈希值

1. 3

复制代码

（二进制

1. 0011

复制代码

）&amp;rarr;

1. 0011 &amp; 0110 = 0010

复制代码

（索引 2）
&amp;bull; 索引 1、3、5、7 永远无法被访问，导致哈希分布不均。

八、性能对比

操作类型指令周期（近似）适用场景位运算（

1. &amp;

复制代码

）1 cycle快速计算取模运算（

1. %

复制代码

）10-20 cycles通用计算在 Redis 这种高性能场景下，位运算的优势显著。

九、总结

&amp;bull;

1. sizemask = size - 1

复制代码

：当

1. size

复制代码

是 2 的幂时，此公式成立。
&amp;bull;

1. hash &amp; sizemask

复制代码

：快速计算键的存储位置，避免取模运算。
&amp;bull; 设计优势：内存对齐、哈希均匀、计算高效。
这种设计是 Redis 哈希表高性能的核心保障，结合渐进式 rehash 机制，使得 Redis 能够高效处理大规模键值对存储。
到此这篇关于redis hashtable 的sizemask理解的文章就介绍到这了,更多相关redis hashtable 的sizemask内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！

来源：https://www.jb51.net/database/338712ken.htm
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！