Dict

The Redis hash table. Used for the keyspace, for HT-encoded sets and hashes, for the cluster node table, for the script cache, and many internal indices.

Source layout

File	Role
src/dict.c	Implementation (~86 KB). Insert, lookup, delete, resize, rehash, iteration, scanning.
src/dict.h	Public API and types.

Key features

• Open addressing? No — chained. Buckets hold a singly-linked list of entries. Collisions append to the chain.
• Incremental rehashing. When the load factor exceeds 1, the table allocates a second internal table at twice the size. Subsequent operations (lookups, inserts) move one bucket at a time from the old table to the new. No request ever pays for a full rehash.
• SipHash-2-4 as the default hash. The seed is randomised at startup (dictSetHashFunctionSeed) to make collision attacks harder.
• Per-bucket pointer-bit reuse. The least-significant bit of the next-pointer can flag "this bucket has more than the listed entries"; this saves memory in some encodings.
• Custom value types. The dict accepts a dictType describing how to hash, compare, copy, free keys and values. Different dicts use different types — dbDictType for the keyspace, setDictType for sets, zsetDictType for sorted sets, hashDictType for hashes, commandTableDictType for the command table, …

API

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];               /* Two tables — old and new during rehash */
    long rehashidx;             /* -1 means not currently rehashing */
    int16_t pauserehash;        /* If > 0, rehashing is paused */
} dict;

dict *dictCreate(dictType *type, void *privDataPtr);
int   dictAdd(dict *d, void *key, void *val);
int   dictReplace(dict *d, void *key, void *val);
void *dictFetchValue(dict *d, const void *key);
int   dictDelete(dict *d, const void *key);
dictEntry *dictFind(dict *d, const void *key);
unsigned long dictSize(const dict *d);
dictIterator *dictGetIterator(dict *d);
unsigned long dictScan(dict *d, unsigned long v, dictScanFunction *fn, void *privdata);

dictReplace returns 1 on insert and 0 on update. dictAdd fails if the key is present. There is also a dictGenericDelete flavour that takes a "free" flag — useful in eviction to detach an entry without freeing it.

Resize policy

A dict has two thresholds:

• Load factor 1 (dict_force_resize_ratio) — the rehash kicks in.
• Load factor 5 — anything over this triggers a forced rehash even if rehashing was previously suspended.

Rehash is suspended (pauserehash > 0) during BGSAVE and BGREWRITEAOF to keep memory pages COW-friendly. The pause is set/cleared in src/server.c.

When the table shrinks (load factor drops far below 1), it can be resized down. The dictResize API does this; the dbResizeIfNeeded cron checks the keyspace dicts.

Iteration

dictGetIterator returns a sequential iterator. Two flavours:

• Safe iterator — pauses rehashing while iterating. Safe against modifications during iteration. Use dictGetSafeIterator.
• Unsafe iterator — does not pause. Faster but the dict must not be modified.

For workloads where you want to walk a large dict without blocking, dictScan is the right tool — it implements a reverse-binary cursor that lets you visit every key with O(1) per call and tolerate concurrent insertions/deletions.

SCAN cursor algorithm

The SCAN command uses dictScan to iterate the keyspace. The cursor is the reverse-bit hash-table index, which makes the cursor stable across resizes. The full algorithm is documented in a long comment block at the top of dictScan in src/dict.c.

Embedded tests

#ifdef REDIS_TEST in src/dict.c defines an extensive test suite covering insertion, deletion, iteration, scanning, resize correctness, and stress with random operations. Run with ./redis-server test dict --accurate.

Where to start modifying

• Add a dictType — declare an instance in your subsystem (src/yourcode.c) with the relevant hash/compare/copy/free callbacks.
• Tune resize thresholds — dict_force_resize_ratio in src/dict.c.
• Add a metric — dictGetStats returns histogram-style stats; surface in INFO if useful.

Related pages

• kvstore — wraps a vector of dicts for slot-aware access.
• robj — HT-encoded values use a dict.