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.