Hash tables in caching (Redis, Memcached) in Data Structures Theory - Time & Space Complexity

Time Complexity: Hash tables in caching (Redis, Memcached)

O(1)

Understanding Time Complexity

When using hash tables in caching systems like Redis or Memcached, it is important to understand how fast data can be stored and retrieved.

We want to know how the time to find or save data changes as the amount of cached data grows.

Scenario Under Consideration

Analyze the time complexity of these basic hash table operations.

function cacheSet(key, value) {
  index = hashFunction(key)
  bucket = table[index]
  for (item of bucket) {
    if (item.key == key) {
      item.value = value
      return
    }
  }
  bucket.push({key: key, value: value})
}

function cacheGet(key) {
  index = hashFunction(key)
  bucket = table[index]
  for (item of bucket) {
    if (item.key == key) return item.value
  }
  return null
}
    

This code shows how caching systems use a hash function to find where data is stored and then search a small list (bucket) for the exact key.

Identify Repeating Operations

• Primary operation: Looping through the bucket (a small list) to find the key.
• How many times: Depends on the number of items in the bucket, usually very few if the hash function spreads keys well.

How Execution Grows With Input

As more items are cached, the table grows, but each bucket stays small if the hash spreads keys evenly.

Input Size (n)	Approx. Operations
10	About 1 to 2 checks per lookup
100	Still about 1 to 2 checks per lookup
1000	Still about 1 to 2 checks per lookup

Pattern observation: The number of checks stays roughly the same because the hash table spreads data evenly, keeping lookups fast.

Final Time Complexity

Time Complexity: O(1)

This means that storing or retrieving data takes about the same short time no matter how much data is cached.

Common Mistake

[X] Wrong: "Hash table lookups always take the same time no matter what."

[OK] Correct: If many keys end up in the same bucket (called collisions), the lookup time can grow because it must check more items in that bucket.

Interview Connect

Understanding how hash tables keep cache lookups fast helps you explain why systems like Redis are so efficient and how to reason about performance in real applications.

Self-Check

"What if the hash function is poor and many keys collide into the same bucket? How would the time complexity change?"