Hash tables in caching (Redis, Memcached) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a hash table in the context of caching systems like Redis and Memcached?

A hash table is a data structure that stores data in key-value pairs, allowing fast data retrieval by computing a hash code from the key to find the data quickly.

beginner

How do Redis and Memcached use hash tables to improve performance?

They use hash tables to quickly find cached data by keys, reducing the time to access data compared to searching through all stored items.

intermediate

What happens when two different keys produce the same hash in a hash table?

This is called a collision. Caching systems handle collisions using methods like chaining (linking items) or open addressing (finding another spot).

intermediate

Why is hashing important for cache eviction policies in Redis and Memcached?

Hashing helps quickly locate keys to decide which cached items to remove when the cache is full, supporting efficient eviction policies like LRU (Least Recently Used).

intermediate

Explain the difference between Redis and Memcached in terms of data structures used for caching.

Redis supports multiple data structures including hash tables, lists, and sets, allowing more complex caching. Memcached mainly uses a simple hash table for key-value storage.

What is the main purpose of using a hash table in caching systems?

A To store data in key-value pairs for fast access

B To sort data alphabetically

C To compress data for storage

D To encrypt cached data

Hash tables store data as key-value pairs and use hashing to quickly find data, improving access speed.

Which method is commonly used to handle hash collisions in caching systems?

A Chaining

B Sorting

C Encryption

D Compression

Chaining links multiple items at the same hash index to handle collisions.

Which caching system supports multiple data structures beyond hash tables?

A Memcached

B Neither Redis nor Memcached

C Both Redis and Memcached

D Redis

Redis supports various data structures like lists and sets, while Memcached mainly uses hash tables.

What does LRU stand for in cache eviction policies?

A Latest Resource Usage

B Least Recently Used

C Longest Running User

D Last Random Update

LRU means Least Recently Used, a policy that removes the oldest accessed items first.

Why is hashing faster than searching all cached items?

A Because it compresses the data

B Because it sorts all data first

C Because it directly computes the location of data using the key

D Because it encrypts the data

Hashing computes a hash code from the key to directly find the data location, avoiding full searches.

Describe how hash tables help caching systems like Redis and Memcached retrieve data quickly.

Think about how a key is transformed to find data without searching everything.

Explain the difference between Redis and Memcached in terms of their use of hash tables and data structures.

Consider the variety of data types each system can store.

Practice

1. What is the main purpose of using hash tables in caching systems like Redis or Memcached?

easy

A. To compress data to save space

B. To sort data alphabetically

C. To encrypt data for security

D. To store data with keys for fast retrieval

Solution

1. Step 1: Understand the role of hash tables

   Hash tables store data in key-value pairs allowing quick access by key.

2. Step 2: Identify caching system goals

   Caching systems aim to speed up data retrieval, which hash tables support by fast key lookup.

3. Final Answer:

   To store data with keys for fast retrieval -> Option D

4. Quick Check:

   Hash tables = fast key-based access [OK]

Hint: Hash tables = fast key lookup in cache [OK]

Common Mistakes:

• Confusing caching with data compression
• Thinking hash tables sort data
• Assuming hash tables encrypt data

2. Which of the following is the correct way to describe a hash table's structure?

easy

A. A key-value store where keys map to values

B. A list of values sorted by size

C. A queue where elements are processed FIFO

D. A stack where elements are processed LIFO

Solution

1. Step 1: Recall hash table definition

   A hash table stores data as key-value pairs for quick access.

2. Step 2: Compare options to definition

   Only the key-value store where keys map to values correctly describes a key-value mapping structure.

3. Final Answer:

   A key-value store where keys map to values -> Option A

4. Quick Check:

   Hash table = key-value pairs [OK]

Hint: Hash tables always map keys to values [OK]

Common Mistakes:

• Confusing hash tables with lists or queues
• Mixing up FIFO and LIFO with hash tables
• Thinking hash tables sort data automatically

3. Consider a caching system using a hash table. If two different keys produce the same hash index, what is this situation called?

medium

A. Underflow

B. Overflow

C. Collision

D. Timeout

Solution

1. Step 1: Understand hash function behavior

   Hash functions map keys to indexes; sometimes different keys map to the same index.

2. Step 2: Identify the term for same index mapping

   This event is called a collision in hash tables.

3. Final Answer:

   Collision -> Option C

4. Quick Check:

   Same index for keys = Collision [OK]

Hint: Same index for keys means collision [OK]

Common Mistakes:

• Confusing collision with overflow or underflow
• Thinking timeout relates to hash indexing
• Assuming collisions never happen

4. A Redis cache uses a hash table but sometimes returns incorrect data for a key. Which of the following is the most likely cause?

medium

A. Keys are sorted incorrectly

B. Hash collision not handled properly

C. Cache size is too large

D. Data is encrypted

Solution

1. Step 1: Analyze incorrect data retrieval

   Incorrect data usually means the wrong value is returned for a key.

2. Step 2: Identify common hash table issue

   If collisions are not handled properly, keys may overwrite or mix values causing errors.

3. Final Answer:

   Hash collision not handled properly -> Option B

4. Quick Check:

   Collision handling error = wrong data [OK]

Hint: Check collision handling if cache returns wrong data [OK]

Common Mistakes:

• Blaming cache size for wrong data
• Thinking sorting keys affects hash retrieval
• Assuming encryption causes wrong values

5. You want to design a caching system using a hash table that minimizes collisions. Which approach is best to achieve this?

hard

A. Use a good hash function and increase table size

B. Store data in a linked list instead of a hash table

C. Sort keys before inserting into the hash table

D. Encrypt keys before hashing

Solution

1. Step 1: Understand collision causes

   Collisions happen when different keys map to the same index due to poor hashing or small table size.

2. Step 2: Identify best practices to reduce collisions

   Using a strong hash function and a larger table reduces collisions effectively.

3. Step 3: Evaluate other options

   Linked lists do not reduce collisions; sorting keys or encrypting keys does not prevent collisions.

4. Final Answer:

   Use a good hash function and increase table size -> Option A

5. Quick Check:

   Good hash + big table = fewer collisions [OK]

Hint: Better hash + bigger table = fewer collisions [OK]

Common Mistakes:

• Thinking sorting keys prevents collisions
• Assuming encryption affects collision rate
• Replacing hash table with linked list to avoid collisions