Why Does Redis Use Dual Data Structures for Sets? Inside intset and Hashtable

Set internal representation

Redis stores a set as either an intset (compact integer set) or a hashtable . The object’s encoding field indicates which representation is active.

intset encoding

An intset holds only integer elements. The element size is chosen from three fixed widths and can grow when a larger integer is inserted.

typedef struct intset {
    uint32_t encoding;   // current integer width (INTSET_ENC_INT16/INT32/INT64)
    uint32_t length;     // number of elements
    int8_t  contents[];   // actual elements, stored using the width indicated by encoding
} intset;

INTSET_ENC_INT16 : 16‑bit signed integers (‑32768 to 32767)

INTSET_ENC_INT32 : 32‑bit signed integers (‑2147483648 to 2147483647)

INTSET_ENC_INT64 : 64‑bit signed integers (‑9223372036854775808 to 9223372036854775807)

Integer‑set upgrade process

When a new integer cannot be represented by the current width, Redis upgrades the intset:

Allocate a new contents array sized for the larger integer type.

Copy existing elements from back to front, converting each to the new width.

Insert the new element at the appropriate end (the new value is either smaller than all existing elements or larger than all of them).

Update encoding and length fields.

The upgrade is irreversible; an intset never downgrades.

Encoding selection

Redis chooses intset only when all members are integers and the set size does not exceed the configurable limit set-max-intset-entries (default 512). If either condition fails, the representation switches to a hashtable.

Set commands

sadd key member [member ...]

– add one or more members. sismember key member – test membership. srem key member [member ...] – remove members. smove src dst member – move a member between sets. smembers key – return all members.

Sorted‑set internal representation

A sorted set (zset) stores each member together with a double‑precision score. Internally Redis can encode a sorted set as a skiplist or a ziplist , selected by size and entry‑length thresholds.

skiplist encoding

The skiplist provides O(log N) ordered traversal, while a hash table gives O(1) score lookup. Redis combines both in a zset structure.

typedef struct zskiplistNode {
    sds               ele;      // member string (SDS)
    double            score;    // double‑precision score
    struct zskiplistNode *backward; // backward pointer (single)
    struct zskiplistLevel {
        struct zskiplistNode *forward; // forward pointer for this level
        unsigned long        span;    // number of nodes skipped by forward
    } level[]; // variable‑length array of levels
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; // head and tail of the list
    unsigned long length;                // total number of nodes
    int           level;                // current maximum level
} zskiplist;

typedef struct zset {
    dict       *dict; // member → score hash table
    zskiplist  *zsl;  // ordered skiplist of the same members
} zset;

Each node’s level[] array holds forward pointers for up to 32 levels (chosen randomly per node). The span field records how many elements are skipped by that forward pointer, enabling fast rank calculations.

ziplist encoding

A ziplist is a compact sequential encoding used when the sorted set is small. The default thresholds are:

Maximum number of elements: zset-max-ziplist-entries (default 128).

Maximum total entry size: zset-max-ziplist-value (default 64 bytes).

If either threshold is exceeded, Redis converts the ziplist to a skiplist.

Encoding conversion conditions

Number of elements ≥ zset-max-ziplist-entries (configurable).

Total size of all entries ≥ zset-max-ziplist-value (configurable).

Sorted‑set commands

zadd key score member [score member ...]

– add members with scores. zscore key member – retrieve a member’s score. zincrby key increment member – increment a member’s score (increment may be negative). zcount key min max – count members with scores in the inclusive range [min, max]. zrange key start stop – return members ordered by increasing score. zrevrange key start stop – return members ordered by decreasing score. zrangebyscore key min max – range query by score (default inclusive; use ( or [ to control bounds). zrevrangebyscore key max min – reverse range query by score. zrank key member – zero‑based rank of member in ascending order. zrevrank key member – zero‑based rank in descending order. zlexcount key min max – count members by lexical range (bounds must be prefixed with ( or [; - and + represent negative/positive infinity).

Conclusion

Redis employs dual encodings for both sets and sorted sets to balance memory efficiency and operation speed. Integer‑only, small sets use the compact intset, while larger or mixed‑type sets fall back to a hashtable. Sorted sets use a ziplist for tiny collections and switch to a combined hash‑table + skiplist representation when size or entry‑length thresholds are crossed. This design provides O(1) member lookup via the hash table and O(log N) ordered range queries via the skiplist without duplicating data.