multimap provides fast, compact multimaps for Go.
A multimap is a data structure that allows multiple values to be associated with a single key, unlike a regular map where each key has exactly one value.
| Constructor | Backed by | Range queries | Iteration order | Concurrency |
|---|---|---|---|---|
New[T]() |
adaptive radix tree | visit only the keys in range | ascending key order | safe (read/write lock) |
NewOrdered[T]() |
adaptive radix tree | visit only the keys in range | ascending key order | not synchronized |
NewHashed[T]() |
Go map | scan all keys | unspecified | not synchronized |
Synchronized[T](m) |
wraps any of the above | as the wrapped map | as the wrapped map | safe (read/write lock) |
Choose Ordered (the default behind New) when range queries or ordered
iteration matter, or when keys are integers: there it is about as fast as
Hashed for point operations. Choose Hashed for string keys when range
queries are rare: point operations are one and a half to two times as fast
there, but every range query scans all keys, and like every Go map it keeps
its table after deletions. Both need about half the memory of a Go map or
B-tree of Go sets. If every key holds exactly one value, a plain B-tree map
answers range queries faster and needs about half the memory of Ordered,
which remains faster for lookups and changes. The benchmarks behind these statements are in bench/README.md.
Both keep the values of a key in a compact container: up to three values inline, then a plain array, then a hash set.
Ordered and Hashed are not synchronized. Any number of goroutines may read
at the same time, but a write must not run concurrently with any other
access; provide that exclusion yourself, or wrap the multimap with
Synchronized, which guards every method with a sync.RWMutex (reads run in
parallel, writes are exclusive). New returns a synchronized Ordered
multimap.
Every read method exists twice:
- The plain form (
ValuesFor,ValuesBetweenInclusive,AllKeys, ...) returns an independent copy (*set3.Set3[T]or[]Key). It allocates, but you may keep and modify the result, and on a synchronized multimap no lock is held once it returns. - The
Seqform (ValuesForSeq,ValuesBetweenInclusiveSeq,AllKeysSeq, ...) returns aniter.Seqover the stored data without copying. It yields the values key by key, so a value stored under several keys is yielded once per key. Keys yielded byAllKeysSeqmust not be modified or retained, and the loop body must not modify the multimap it iterates over.
On a synchronized multimap, a Seq iterator holds the read lock for the whole
loop. The loop body must not call any method of the same multimap (this can
deadlock), and a long loop delays writers. Use the plain form when the loop
body needs the multimap or runs long.
- One-to-many mapping: Each key can have zero, one, or multiple values
- Duplicate values: The same value can only be stored once per key but it can be stored multiple times for different keys
- Key uniqueness: Keys themselves are still unique - there's only one entry per key
- Indexing: Group items by category (e.g., products by brand)
- Graph representations: Store adjacency lists where each node maps to multiple connected nodes
- HTTP headers: Multiple values for the same header name
- Database indexes: Multiple records sharing the same indexed value
The multimap uses Key objects for indexing, which are internally represented as []byte arrays. This allows for efficient storage and comparison regardless of the original data type used to create the key.
- Mixed types: A single multimap can contain keys created from different data types (strings, integers, custom byte arrays) without any issues.
- Lexicographic ordering: All keys are compared using byte-wise lexicographic ordering of their internal
[]byterepresentation. - Custom keys: You can create keys from any
[]bytearray using the generic constructor for your own implementations.
Important: When mixing different key types in range queries, the lexicographic ordering may be counter-intuitive. For example:
// These keys will NOT be ordered numerically when mixed with strings:
key1 := FromString("100") // UTF-8 bytes: [0x31, 0x30, 0x30]
key2 := FromInt64(50) // Encoded as: [0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x32]
key3 := FromString("25") // UTF-8 bytes: [0x32, 0x35]
// Lexicographic order: key1 ("100") < key3 ("25") < key2 (50)
// This differs from intuitive numeric/alphabetic ordering!For predictable range query behavior, use consistent key types within logical ranges. See the type-specific encoding details below.
- Use
FromString(s)to convert a string to aKey.FromStringnormalizes the input string using Unicode NFC so canonically equivalent strings map to the same key. Keyordering (LessThan) is a byte-wise lexicographic comparison of the UTF-8 bytes — it is neither locale-aware nor rune-aware.
- Use
FromInt*/FromUint*helpers to build integer keys. - All integer keys are encoded as fixed-width 8-byte big-endian sequences (MSB first).
- To ensure consistent ordering across signed/unsigned types and across widths, all
integer constructors add an offset of
1<<63before encoding. Signed values are converted toint64first; unsigned values are treated asuint64and the same offset is added. This maps signed and unsigned values into a single uint64 namespace so that lexicographic comparison matches numeric ordering.
Examples / consequences:
FromInt64(0)equalsFromUint64(0)because both are encoded as0 + (1<<63).- The smallest
int64(-2^63) maps to[00,00,00,00,00,00,00,00]after encoding; negative signed values compare before zero/positive values as expected for numeric order. - Values encoded from different widths are comparable — for example
FromInt32(x)is identical toFromInt64(x)for the same numericx.
AddValue(key, v)cloneskeybefore inserting; mutating the caller'sKeyafter callingAddValuewill not affect the stored key.ValuesFor(key)and the other set-returning methods return copies; modifying a returned set does not affect theMultiMap's contents.- Removing the last value of a key removes the key.
- Range queries: Keys are ordered in lexicographic order, allowing efficient range queries between two key boundaries. Range operations return a set of all values of all keys where the key falls within the specified range (inclusive or exclusive based on the method). The ordering follows the byte-wise comparison rules described above for string and numeric keys.
See the example_test.go in this package for runnable examples that also appear
in generated GoDoc.
multimap stands on the shoulders of others. Thank you!
- The tree behind
Orderedfollows the Adaptive Radix Tree by Viktor Leis, Alfons Kemper and Thomas Neumann: The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases (ICDE 2013). Nodes that grow and shrink with their number of children, path compression and lazy expansion come from there; the node sizes, the child search and the value sets in the leaves are this project's own. - The child search in the small nodes uses the "has zero byte" SWAR trick collected in Sean Eron Anderson's Bit Twiddling Hacks (after Alan Mycroft).
- plar/go-adaptive-radix-tree,
plar/go-hot-trie and
tidwall/btree served as yardsticks while
the design took shape (see
bench/_archive). No code of theirs is included. - The benchmark measures real keys thanks to the OpenStreetMap
contributors, whose German street names reach it through the
OpenPLZ API project's data extract (© OpenStreetMap
contributors, ODbL 1.0), and
to the Debian project, whose package contents lists supply its file
paths. Both corpora and their licenses are described in
bench/keys/testdata.