在 Redis 的哈希表實(shí)現(xiàn)中，index = hash & dict->ht[0].sizemask 是計(jì)算鍵值對(duì)應(yīng)存儲(chǔ)位置的核心操作。這個(gè)操作看起來簡單，但背后涉及哈希表的內(nèi)存布局和性能優(yōu)化策略。我們通過以下步驟逐步解析其原理：

一、哈希表的設(shè)計(jì)目標(biāo)

• 快速定位桶（Bucket）：通過鍵的哈希值直接找到對(duì)應(yīng)的存儲(chǔ)位置，時(shí)間復(fù)雜度接近 O(1)。
• 均勻分布鍵值對(duì)：減少哈希沖突，避免鏈表過長導(dǎo)致性能下降。
• 高效計(jì)算：避免使用耗時(shí)的取模運(yùn)算（%）。

二、哈希表大?。╯ize）的特殊性

Redis 的哈希表大小 size 始終是 2 的冪（如 4, 8, 16, 32 等）。這種設(shè)計(jì)有兩個(gè)關(guān)鍵優(yōu)勢(shì)：

• 快速計(jì)算索引：用位運(yùn)算（&）替代取模運(yùn)算（%）。
• 均勻分布哈希值：減少哈希沖突的概率。

三、sizemask 的作用

• 定義：sizemask = size - 1
• 二進(jìn)制特征：當(dāng) size 是 2 的冪時(shí)，sizemask 的二進(jìn)制形式為全 1。
例如：
• size = 8 → sizemask = 7 → 二進(jìn)制 0111
• size = 16 → sizemask = 15 → 二進(jìn)制 1111

四、索引計(jì)算原理

1. 取模運(yùn)算的替代方案

傳統(tǒng)哈希索引計(jì)算使用取模運(yùn)算：

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

但取模運(yùn)算在計(jì)算機(jī)中效率較低（涉及除法操作）。

2. 位運(yùn)算優(yōu)化

當(dāng) size 是 2 的冪時(shí)，可以用位運(yùn)算替代：

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

為什么這等價(jià)于取模？
• 因?yàn)?size 是 2 的冪，size - 1 的二進(jìn)制形式為全 1（例如 size=8 對(duì)應(yīng) sizemask=7，二進(jìn)制 0111）。
• hash & sizemask 相當(dāng)于保留哈希值的低 n 位（n = log2(size)），結(jié)果范圍是 0 ≤ index < size，與 hash % size 等價(jià)。

五、具體示例

假設(shè)哈希表大小 size = 8（即 sizemask = 7），哈希值 hash = 10：

結(jié)果與 10 % 8 = 2 完全一致，但位運(yùn)算比取模運(yùn)算快得多。

六、哈希表擴(kuò)容時(shí)的行為

當(dāng)哈希表需要擴(kuò)容（例如從 size=8 擴(kuò)容到 size=16）：

新 sizemask = 15（二進(jìn)制 1111）。哈希值相同的鍵會(huì)分散到更多桶中：
• 例如原哈希值 10（二進(jìn)制 1010）在 size=8 時(shí)索引為 2。
• 擴(kuò)容后 size=16，索引變?yōu)?10 & 15 = 10。

七、為什么必須保證 size 是 2 的冪？

如果 size 不是 2 的冪，sizemask 的二進(jìn)制形式將包含 0，導(dǎo)致部分索引永遠(yuǎn)無法被映射到。
例如：
• size = 7 → sizemask = 6（二進(jìn)制 0110）
• 哈希值 5（二進(jìn)制 0101）→ 0101 & 0110 = 0100（索引 4）
• 哈希值 3（二進(jìn)制 0011）→ 0011 & 0110 = 0010（索引 2）
• 索引 1、3、5、7 永遠(yuǎn)無法被訪問，導(dǎo)致哈希分布不均。

八、性能對(duì)比

在 Redis 這種高性能場(chǎng)景下，位運(yùn)算的優(yōu)勢(shì)顯著。

九、總結(jié)

• sizemask = size - 1：當(dāng) size 是 2 的冪時(shí)，此公式成立。
• hash & sizemask：快速計(jì)算鍵的存儲(chǔ)位置，避免取模運(yùn)算。
• 設(shè)計(jì)優(yōu)勢(shì)：內(nèi)存對(duì)齊、哈希均勻、計(jì)算高效。

這種設(shè)計(jì)是 Redis 哈希表高性能的核心保障，結(jié)合漸進(jìn)式 rehash 機(jī)制，使得 Redis 能夠高效處理大規(guī)模鍵值對(duì)存儲(chǔ)。

到此這篇關(guān)于redis hashtable 的sizemask理解的文章就介紹到這了,更多相關(guān)redis hashtable 的sizemask內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論