Sparse sets: constant-time membership for bounded integer IDs

Last updated: 5 Oct 20269 min read

tutorial

A sparse set stores active integer IDs in a dense array and maps each possible ID to a candidate dense index through a sparse array. Membership checks both that the candidate index falls inside the current dense length and that the dense value at that index matches the queried ID. That second comparison makes stale sparse entries harmless after clearing or swap deletion. Insert, membership, deletion, and clear are O(1) under a fixed bounded universe. Memory is O(U + n), where U is the possible ID range and n the active count, so this choice is poor when U is enormous and few IDs are active.

Operational case

A gateway has device slots numbered 0 through 127. Slots 47, 61, and 52 are active. Removing 61 moves the last dense member, 52, into its place and changes 52's sparse position. The dense array is now 47, 52; an old sparse position for 61 may still exist, but the membership check rejects it because that position no longer points to 61. The operation changes iteration order. If users need chronological order, store it separately rather than claiming this set preserves the order of activation.

Working Python program

slot_limit = 128
sparse_position = [-1] * slot_limit
active_slots = []

def contains(slot_id):
    position = sparse_position[slot_id]
    return 0 <= position < len(active_slots) and active_slots[position] == slot_id

def activate(slot_id):
    if not contains(slot_id):
        sparse_position[slot_id] = len(active_slots)
        active_slots.append(slot_id)

def deactivate(slot_id):
    if not contains(slot_id):
        return
    position = sparse_position[slot_id]
    last_slot = active_slots.pop()
    if position < len(active_slots):
        active_slots[position] = last_slot
        sparse_position[last_slot] = position

for slot_id in (47, 61, 52):
    activate(slot_id)
deactivate(61)
print(active_slots, contains(61), contains(52))

Output

[47, 52] False True

Time, space, and tradeoff

Each demonstrated operation touches a bounded number of array positions and takes O(1) time. Initializing sparse positions takes O(U) time and space, while active storage uses O(n). A clear operation can discard only the dense members in O(1) time if the membership check continues to compare dense values; old candidate positions must never be trusted alone. Public methods must reject negative or out-of-range IDs, since Python negative indices would otherwise address the wrong slot. The structure trades a fixed universe allocation for predictable membership operations.

Common Mistakes

Do not trust a sparse index without checking the dense value.
Do not claim swap deletion preserves iteration order.
Do not accept Python negative indices as valid device IDs.

Connected lessons

Apply it: Project: design a versioned warehouse index and Advanced structure contracts.

Generational slots: reject stale handles after reuse adds a related lifecycle choice.

Free spans: first-fit allocation and adjacent coalescing extends the storage ownership comparison.

Slab slots: reuse fixed-size pages with generation checks extends the storage ownership comparison.

data structures

range-query-structures