Understanding Redis Dictionary: Structure, Element Insertion, and Rehashing Compared to Java HashMap

Dictionary Data Structure

Redis stores key‑value pairs using an internal dictionary that, by default, creates a hash table array containing two hash tables. When a Hash key is created, it initially uses a ZIPLIST to save memory; however, if the key or value length exceeds server.hash_max_ziplist_value (default 64) or the number of entries exceeds server.hash_max_ziplist_entries (default 512), the structure switches to a full dictionary.

The dictionary contains two hash tables: ht[0] and ht[1] . ht[0] is allocated on the first insertion, while ht[1] is allocated only during rehash (resize) operations.

Each hash table stores an array called table , whose elements are dictEntry structures similar to Java HashMap's Entry . A dictEntry holds a key‑value pair and a next pointer to resolve hash collisions via linked lists.

Element Addition Process

When a new element is added, memory is allocated for ht[0] . By default the hash table array size is 4 (defined by DICT_HT_INITIAL_SIZE ). The key is hashed to determine its slot, and the entry is placed there.

If two different keys hash to the same slot, a collision occurs. Redis resolves collisions by chaining entries in a linked list, inserting the newest entry at the head to improve access speed for recently added items. This behavior mirrors the pre‑JDK 8 HashMap implementation.

As more elements are added, collisions become more frequent, potentially degrading O(1) lookups to O(N). Therefore, the dictionary must resize.

Resizing (Rehash)

During a resize, Redis allocates a larger ht[1] whose size is the smallest power of two greater than or equal to ht[0].used * 2 . All entries from ht[0] are then gradually moved to ht[1] .

During rehash, the index rehashidx (initially -1) is set to 0 and increments as buckets are migrated. Each subsequent command (add, delete, lookup, update) also moves the bucket at rehashidx from ht[0] to ht[1] , making the operation incremental and non‑blocking.

When rehash completes, ht[0] is freed and ht[1] becomes the new ht[0] , with rehashidx reset to -1. This progressive approach avoids long pauses but adds complexity because lookups may need to check both hash tables.

In contrast, Java HashMap performs a one‑time resize, moving all entries to a new array at once, which can be costly for large maps.

Summary

Redis dictionaries use two hash tables as the underlying implementation, closely resembling Java HashMap's array‑plus‑linked‑list structure. Resizing is performed via incremental rehashing to minimize service disruption, whereas Java HashMap resizes in a single step.

Helpful Resources

https://redisbook.readthedocs.io/en/latest/internal-datastruct/dict.html