How Redis Uses Hash Tables: Dictionary Implementation, Rehashing, and Iterators

Redis is an in‑memory key‑value store whose core data structure is a dictionary implemented with hash tables; the database itself, as well as the Hash and Sorted‑Set types, use this "dict" structure.

The server representation (redisServer) contains multiple redisDb objects, each of which holds a dict that stores key‑value pairs, illustrating the relationship between redisServer, redisDb, and the underlying hash table.

Redis objects are not stored directly as raw structures; a hash object can be backed by either a ziplist or a dict. The choice depends on two thresholds: a maximum of 512 entries and key/value strings shorter than 64 bytes. When either condition is exceeded, the object switches to the dict implementation.

The dictionary is defined in dict.h by the dict struct, which contains a pointer to a dictType (defining type‑specific functions) and a privdata field for custom arguments. The actual hash table is a dictht structure holding an array of dictEntry buckets.

Each dictEntry represents a node in a bucket’s linked list and stores a key (usually a stringObject ) and a v union that may hold integers, floats, or pointers to other objects. Collisions are resolved with chaining: multiple entries that hash to the same index are linked via the next pointer.

Redis performs rehashing to resize hash tables when the load factor becomes too high or too low. Two tables, ht[0] (old) and ht[1] (new), are used. The process allocates a new table, moves entries bucket by bucket, updates rehashidx , and finally swaps the tables, resetting rehashidx to –1. To avoid blocking the server, Redis uses a progressive rehash: each add, delete, lookup, or update operation moves a small number of buckets, and idle time can trigger additional steps.

Dictionary traversal is performed with iterators. A non‑safe iterator allows only dictNext() calls and permits a single rehash step during iteration. A safe iterator increments the dictionary’s iterators count, forbidding any rehash step while the iterator is active to prevent duplicate visits caused by bucket migration.

Overall, the article shows how Redis’s hash‑table‑based dictionary underpins its storage engine, handles key collisions, dynamically resizes through progressive rehash, and provides both safe and unsafe iterators for reliable data traversal.