Hash slots distribution in Redis - Time & Space Complexity

Time Complexity: Hash slots distribution

O(n)

Understanding Time Complexity

When using Redis clusters, data is split into parts called hash slots. Understanding how time grows when distributing keys into these slots helps us see how fast Redis can find or store data.

We want to know how the work changes as we add more keys to the cluster.

Scenario Under Consideration

Analyze the time complexity of the following Redis commands for distributing keys into hash slots.

# Calculate hash slot for each key
for key in KEYS {
  slot = CRC16(key) % 16384
  assign key to slot
}
    

This code calculates which of the 16384 hash slots each key belongs to using a hash function, then assigns the key to that slot.

Identify Repeating Operations

Look for repeated steps in the process.

• Primary operation: Calculating the hash slot for each key using CRC16 and modulo.
• How many times: Once for every key in the input list.

How Execution Grows With Input

As you add more keys, the number of hash calculations grows directly with the number of keys.

Input Size (n)	Approx. Operations
10	10 hash calculations
100	100 hash calculations
1000	1000 hash calculations

Pattern observation: The work grows evenly as you add more keys; doubling keys doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to assign keys to hash slots grows in direct proportion to the number of keys.

Common Mistake

[X] Wrong: "Calculating hash slots is constant time no matter how many keys there are."

[OK] Correct: Each key needs its own hash calculation, so more keys mean more work, not the same amount.

Interview Connect

Understanding how Redis distributes keys helps you explain how data is balanced and accessed quickly in real systems. This skill shows you can think about how systems handle growing data smoothly.

Self-Check

"What if we used a more complex hash function that takes longer to compute? How would the time complexity change?"