Associative Structures

Read this page when the problem is lookup, uniqueness, key order, prefix search, or membership testing. The first question is not which structure is fastest in theory. The first question is what kind of answer you need back: one value, one yes or no, values in key order, words under a prefix, or a probabilistic prefilter.

Choose by Result Shape

For key to value lookup by hashing, read Maps. Constructor family: create_map(...).

For uniqueness only, read Sets. Constructor family: create_set(...).

For ordered keys, predecessor, successor, or range query, read Trees. Constructor family: create_tree(...).

For exact word lookup and prefix expansion, read Trie. Constructor family: create_trie().

For fast negative membership checks with false positives allowed, read Bloom Filter. Constructor family: create_bloom_filter(...).

Selection Diagram

flowchart TD
    A[Need lookup or membership] --> B{Need key-value pairs?}
    B -->|yes| M[Maps]
    B -->|no| C{Need key order?}
    C -->|yes| T[Trees]
    C -->|no| D{Need prefix search on words?}
    D -->|yes| TR[Trie]
    D -->|no| E{Need exact uniqueness or probabilistic prefilter?}
    E -->|exact uniqueness| S[Sets]
    E -->|prefilter| BF[Bloom Filter]

Decision Rules

Use a map when the stored object is a key-value pair and the caller wants to retrieve the value later by key.

Use a set when the payload itself is the key and uniqueness is the point.

Use a tree when key order is part of the problem, not a by-product.

Use a trie when the query is over prefixes of byte strings.

Use a bloom filter when you want a cheap prefilter before a more expensive exact lookup.

The Common Boundaries

Hash-based structures depend on the comparator and hash function agreeing on equality.

Tree-based structures depend on the comparator alone.

The bloom filter never stores payload pointers. The other structures do.

Move next to Maps, Sets, Trees, Trie, or Bloom-Filter.