在 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 永遠無法被訪問，導致哈希分布不均。
八、性能對比
| 操作類型 | 指令周期（近似） | 適用場景 |
|---|---|---|
位運算（&） | 1 cycle | 快速計算 |
取模運算（%） | 10-20 cycles | 通用計算 |
在 Redis 這種高性能場景下，位運算的優勢顯著。
九、總結
? sizemask = size - 1：當 size 是 2 的冪時，此公式成立。
? hash & sizemask：快速計算鍵的存儲位置，避免取模運算。
? 設計優勢：內存對齊、哈希均勻、計算高效。
這種設計是 Redis 哈希表高性能的核心保障，結合漸進式 rehash 機制，使得 Redis 能夠高效處理大規模鍵值對存儲。
（C++/Java題解）)
