A brief analysis of the sizemask understanding of redis hashtable

In Redis's hash table implementation,index = hash & dict->ht[0].sizemaskIt is the core operation of calculating the storage location corresponding to the key value. This operation looks simple, but it involves the memory layout and performance optimization strategy of the hash table. We gradually analyze its principle through the following steps:

1. The design objectives of hash table

• Quick positioning bucket (Bucket): The corresponding storage location is directly found through the hash value of the key, and the time complexity is close to O(1).
• Evenly distributed key-value pairs: Reduce hash conflicts and avoid performance degradation caused by too long linked lists.
• Efficient calculation: Avoid using time-consuming modulus operations (%）。

2. The special nature of hash table size (size)

Redis hash table sizesizeAlwaysPower of 2(e.g. 4, 8, 16, 32, etc.). This design has two key advantages:

• Quickly calculate indexes: Use bit operation (&) replaces modulus operation (%）。
• Evenly distributed hash value: Reduce the probability of hash conflict.

3. The role of sizemask

• definition：sizemask = size - 1
• Binary features:whensizeWhen it is a power of 2,sizemaskThe binary form of 1 is all 1.
For example:
• size = 8 → sizemask = 7→ Binary0111
• size = 16 → sizemask = 15→ Binary1111

4. Index calculation principle

1. Alternative solution to modulo operation

Traditional hash index calculation uses modulus operation:

index = hash % size; // For example hash=10, size=8 → index=2

However, modulus operation is less efficient in computers (involving division operations).

2. Bit operation optimization

whensizeWhen it is a power of 2, bit operations can be replaced by:

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

Why is this equivalent to taking a model?
• becausesizeis a power of 2,size - 1The binary form is all 1 (e.g.size=8correspondsizemask=7, binary0111）。
• hash & sizemaskThe equivalent of a low reserved hash valuenBit(n = log2(size)), the result range is0 ≤ index < size,andhash % sizeequivalence.

V. Specific examples

Assume hash table sizesize = 8(Right nowsizemask = 7), hash valuehash = 10：

Results and10 % 8 = 2It is exactly consistent, but the bit operation is much faster than the modulus operation.

6. The behavior of hash table expansion

When the hash table needs to be expanded (for example, fromsize=8Expand tosize=16）：

newsizemask = 15(Binary1111). Keys with the same hash value will be spread into more buckets:
• For example, the original hash value10(Binary1010)existsize=8When the index is2。
• After expansionsize=16, the index becomes10 & 15 = 10。

7. Why must size be guaranteed to be a power of 2?

ifsizeNot a power of 2,sizemaskThe binary form of 0 will contain 0, causing partial indexes to never be mapped to.
For example:
• size = 7 → sizemask = 6(Binary0110）
• Hash value5(Binary0101）→ 0101 & 0110 = 0100(Index 4)
• Hash value3(Binary0011）→ 0011 & 0110 = 0010(Index 2)
• Index 1, 3, 5, 7 can never be accessed, resulting in uneven hash distribution.

8. Performance comparison

In high-performance scenarios like Redis, the advantages of bit operations are significant.

9. Summary

• sizemask = size - 1:whensizeThis formula holds when it is a power of 2.
• hash & sizemask: Quickly calculate the storage location of the key to avoid modulus calculation.
• Design advantages: memory alignment, uniform hashing, and efficient calculation.

This design is the core guarantee of the high performance of Redis hash tables. Combined with the progressive rehash mechanism, Redis can efficiently handle large-scale key-value pair storage.

This is the article about the sizemask understanding of redis hashtable. For more related redis hashtable sizemask content, please search for my previous articles or continue browsing the related articles below. I hope everyone will support me in the future!