multimap

README

multimap for Go

multimap provides a compact, thread-safe multimap implementation 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.

Key Characteristics

• 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

Common Use Cases

• 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

Indexing

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.

Key behavior

• 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 []byte representation.
• Custom keys: You can create keys from any []byte array 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.

String keys

• Use FromString(s) to convert a string to a Key. FromString normalizes the input string using Unicode NFC so canonically equivalent strings map to the same key.
• Key ordering (LessThan) is a byte-wise lexicographic comparison of the UTF-8 bytes — it is neither locale-aware nor rune-aware.

Numeric keys

• 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<<63 before encoding. Signed values are converted to int64 first; unsigned values are treated as uint64 and 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) equals FromUint64(0) because both are encoded as 0 + (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 to FromInt64(x) for the same numeric x.

Behavior and semantics

• PutValue(key, v) clones key before inserting; mutating the caller's Key after calling PutValue will not affect the stored key.
• GetValuesFor(key) and other retrieval mehods return clones of stored Set3 instances; modifying the returned set does not affect the MultiMap's contents.
• 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.

Examples

See the example_test.go in this package for runnable examples that also appear in generated GoDoc.

Documentation

Overview

Package multimap provides a simple, thread-safe multi-map keyed by Key objects. The default implementation is array-based. This file defines the generic MultiMap interface and constructors allowing future alternative implementations.

Keys are compared using `Key.LessThan`, which performs a byte-wise lexicographic comparison of the underlying `[]byte` representation. Range queries and ordering semantics follow that byte-wise comparison; mixing different key encodings (for example UTF-8 strings and encoded integers) may yield ordering that is counter-intuitive for numeric or locale-aware comparisons.

Concurrency: all methods of any MultiMap implementation are safe for concurrent use by multiple goroutines.

Example (BasicUsage)

mm := New[int]()
// Use FromString to obtain normalized keys from user strings
mm.AddValue(FromString("Alice"), 1)
mm.AddValue(FromString("Bob"), 2)

fmt.Println(mm.NumberOfKeys())

Output:

2

Example (RangeQuery)

mm := New[int]()
mm.AddValue(FromString("a"), 1)
mm.AddValue(FromString("b"), 2)
mm.AddValue(FromString("c"), 3)

set := mm.ValuesBetweenInclusive(FromString("a"), FromString("b"))
// set is a *set3.Set3[int]; for documentation we print whether it contains 1 and 2
fmt.Println(set.Equals(set3.From(1, 2)))

Output:

true

Index

• Constants
• func LongestCommonPrefix(a, b Key) uint
• type Key
  • func FromByte(b byte) Key
  • func FromBytes(b []byte) Key
  • func FromInt(i int) Key
  • func FromInt16(i int16) Key
  • func FromInt32(i int32) Key
  • func FromInt64(i int64) Key
  • func FromInt8(i int8) Key
  • func FromRune(r rune) Key
  • func FromString(s string) Key
  • func FromUint(u uint) Key
  • func FromUint16(u uint16) Key
  • func FromUint32(u uint32) Key
  • func FromUint64(u uint64) Key
  • func FromUint8(u uint8) Key
  • func (k Key) Bytes() []byte
  • func (k Key) Clone() Key
  • func (k Key) Equal(other Key) bool
  • func (k Key) IsEmpty() bool
  • func (k Key) LessThan(other Key) bool
  • func (k Key) String() string
• type MultiMap
  • func New[T comparable]() MultiMap[T]
  • func NewArrayBased[T comparable]() MultiMap[T]

Examples

• Package (BasicUsage)
• Package (RangeQuery)

Constants

const (
	Leaf    nodeType = 0
	Node5   nodeType = 1
	Node51  nodeType = 2
	Node256 nodeType = 3
)

Functions

func LongestCommonPrefix

func LongestCommonPrefix(a, b Key) uint

LongestCommonPrefix returns the length of the longest common prefix of a and b. If either a or b is nil, one of both is empty or they have no common prefix, 0 is returned. The returned length is in bytes. The value is always between 0 and min(len(a), len(b)).

Types

type Key

type Key []byte

Key is an alias for a byte slice used as a map key representation. Use the provided constructors to build Keys from primitive types or normalized strings.

Integer encoding policy ----------------------- All integer constructors produce an 8-byte big-endian representation (most-significant byte first). To ensure consistent, order-preserving comparisons across signed and unsigned types and across different integer widths, every integer constructor adds an offset of `1<<63` before encoding the numeric value. For signed constructors the value is first converted to `int64`, for unsigned constructors it is treated as `uint64`; in both cases the offset is added and the resulting unsigned 64-bit value is written big-endian into the Key.

This mapping has two useful properties:

• Lexicographic byte-wise comparison of Keys corresponds to numeric ordering of the original values (taking signedness into account).
• Values produced from different source widths are comparable (for example `FromInt32(x)` equals `FromInt64(x)` for the same numeric x).

Note: Because both signed and unsigned constructors add the same offset, `FromInt64(0)` equals `FromUint64(0)`. The smallest `int64` value (`math.MinInt64`) maps to `0` and negative signed values compare before zero/positive values as expected for numeric ordering.

func FromByte

func FromByte(b byte) Key

FromByte is an alias for FromUint8 and produces an 8-byte representation.

func FromBytes

func FromBytes(b []byte) Key

FromBytes returns a copy of the provided byte slice as a Key. If b is nil this returns an empty (zero-length) Key (not nil).

func FromInt

func FromInt(i int) Key

FromInt converts an `int` to an 8-byte big-endian Key. The signed integer range is shifted by adding 1<<63 so that negative values compare before positive values when Keys are compared lexicographically.

func FromInt16

func FromInt16(i int16) Key

FromInt16 converts an int16 to an 8-byte big-endian Key (value is encoded into 64 bits). The signed value is shifted by 1<<63 for order-preserving behavior across widths.

func FromInt32

func FromInt32(i int32) Key

FromInt32 converts an int32 to an 8-byte big-endian Key (value is encoded into 64 bits). The signed value is shifted by 1<<63 for order-preserving behavior across widths.

func FromInt64

func FromInt64(i int64) Key

FromInt64 converts an int64 to an 8-byte big-endian Key. The value is shifted by 1<<63 so that lexicographic key order matches numeric order.

func FromInt8

func FromInt8(i int8) Key

FromInt8 converts an int8 to an 8-byte big-endian Key (value is encoded into 64 bits). The signed value is shifted by 1<<63 for order-preserving behavior across widths.

func FromRune

func FromRune(r rune) Key

FromRune converts a rune to its UTF-8 encoding as a Key.

func FromString

func FromString(s string) Key

FromString returns a Key produced from the provided string after normalizing it to Unicode NFC. The resulting Key contains the UTF-8 encoding of the normalized string. (FromString does not alter case or trim spaces.)

func FromUint

func FromUint(u uint) Key

FromUint converts a uint to an 8-byte big-endian Key (MSB first).

func FromUint16

func FromUint16(u uint16) Key

FromUint16 converts a uint16 to an 8-byte big-endian Key (value encoded into 64 bits).

func FromUint32

func FromUint32(u uint32) Key

FromUint32 converts a uint32 to an 8-byte big-endian Key (value encoded into 64 bits).

func FromUint64

func FromUint64(u uint64) Key

FromUint64 converts a uint64 to an 8-byte big-endian Key (MSB first).

func FromUint8

func FromUint8(u uint8) Key

FromUint8 converts a uint8 to an 8-byte big-endian Key (value encoded into 64 bits).

func (Key) Bytes

func (k Key) Bytes() []byte

Bytes returns a copy of the Key as a byte slice.

func (Key) Clone

func (k Key) Clone() Key

Clone returns an independent copy of the Key. If k is nil, Clone returns nil.

func (Key) Equal

func (k Key) Equal(other Key) bool

Equal reports whether k and other have the same contents.

func (Key) IsEmpty

func (k Key) IsEmpty() bool

IsEmpty returns whether the Key is empty or nil.

func (Key) LessThan

func (k Key) LessThan(other Key) bool

LessThan reports whether k is lexicographically less than other.

func (Key) String

func (k Key) String() string

String returns the Key as a string consisting of uppercase hex tuples per byte, separated by commas and surrounded by `[]` (e.g. `[01,AB,00]`).

type MultiMap

type MultiMap[T comparable] interface {

	// AddValue adds value to the set at key. If the key does not exist in the MultiMap it will be
	// added and the according set will be created. The provided Key is cloned before insertion;
	// changes to the caller's Key after calling AddValue will not affect the stored key.
	AddValue(key Key, value T)

	// ContainsKey checks whether the MultiMap contains the specified key.
	ContainsKey(key Key) bool

	// ValuesFor returns the set of values associated with key. If the key does not exist
	// or if it exists but no values are stored for this key, it returns an empty set.
	// This function always returns a non-nil set. The result set is an independent
	// copy and can thus be safely mutated by the caller without affecting the MultiMap.
	ValuesFor(key Key) *set3.Set3[T]

	// ValuesBetweenInclusive returns a set with all values whose keys are between from and to,
	// including values stored for from and to. Comparisons use `Key.LessThan` (byte-wise
	// lexicographic). It is irrelevant whether the from and to keys exist in the MultiMap.
	// If `from` is greater than `to` according to `Key.LessThan`, the result is an empty set.
	// If no key exists between from and to or if no values are stored for these keys, this function
	// returns an empty set. This function always returns a non-nil set. The result set is an
	// independent copy and can thus be safely mutated by the caller.
	ValuesBetweenInclusive(from, to Key) *set3.Set3[T]

	// ValuesBetweenExclusive returns a set with all values whose keys are between from and to,
	// excluding values stored for from and to. Comparisons use `Key.LessThan` (byte-wise
	// lexicographic). It is irrelevant whether the from and to keys exist in the MultiMap.
	// If `from` is greater than `to` the result is an empty set. If no key exists between from
	// and to or if no values are stored for these keys, this function returns an empty set.
	// This function always returns a non-nil set. The result set is an independent copy and
	// can thus be safely mutated by the caller.
	ValuesBetweenExclusive(from, to Key) *set3.Set3[T]

	// ValuesFromInclusive returns a set with all values whose keys are greater than or equal to from.
	// Comparisons use `Key.LessThan`. It is irrelevant whether the from key exists in the MultiMap.
	// If no key exists after from or if no values are stored for these keys, this function returns
	// an empty set. This function always returns a non-nil set. The result set is an independent
	// copy and can thus be safely mutated by the caller.
	ValuesFromInclusive(from Key) *set3.Set3[T]

	// ValuesFromExclusive returns a set with all values whose keys are strictly greater than from.
	// Comparisons use `Key.LessThan`. It is irrelevant whether the from key exists in the MultiMap.
	// If no key exists after from or if no values are stored for these keys, this function returns
	// an empty set. This function always returns a non-nil set. The result set is an independent
	// copy and can thus be safely mutated by the caller.
	ValuesFromExclusive(from Key) *set3.Set3[T]

	// ValuesToInclusive returns a set with all values whose keys are less than or equal to to.
	// Comparisons use `Key.LessThan`. It is irrelevant whether the to key exists in the MultiMap.
	// If no key exists before to or if no values are stored for these keys, this function returns
	// an empty set. This function always returns a non-nil set. The result set is an independent
	// copy and can thus be safely mutated by the caller.
	ValuesToInclusive(to Key) *set3.Set3[T]

	// ValuesToExclusive returns a set with all values whose keys are strictly less than to.
	// Comparisons use `Key.LessThan`. It is irrelevant whether the to key exists in the MultiMap.
	// If no key exists before to or if no values are stored for these keys, this function returns
	// an empty set. This function always returns a non-nil set. The result set is an independent
	// copy and can thus be safely mutated by the caller.
	ValuesToExclusive(to Key) *set3.Set3[T]

	// AllValues returns a set with all values currently stored in the multi-map.
	// If no values are stored, this function returns an empty set. This function always returns a non-nil set.
	// The result set is an independent copy and can thus be safely mutated by the caller.
	AllValues() *set3.Set3[T]

	// NumberOfKeys returns the number of keys currently stored in the map.
	NumberOfKeys() uint64

	// AllKeys returns a slice with all keys currently stored in the map. Returned
	// keys are clones and can be safely mutated by the caller. The order of keys is
	// implementation-defined and should not be relied upon.
	AllKeys() []Key

	// RemoveValue removes value v from the set of values at key. Removing a non-existent
	// key or value is a no-op. If the set becomes empty the key may be removed.
	RemoveValue(key Key, v T)

	// RemoveKey removes the key and its associated set of values from the MultiMap.
	// Removing a non-existent key is a no-op.
	RemoveKey(key Key)

	// Clear removes all keys and values from the MultiMap.
	Clear()
}

MultiMap defines the behavior of a multi-map from Keys to a set of values. Implementations must clone Keys on insertion and return cloned value sets so callers cannot mutate internal state. Implementations must be safe for concurrent use by multiple goroutines.

func New

func New[T comparable]() MultiMap[T]

New returns a new MultiMap using the default array-based implementation.

func NewArrayBased

func NewArrayBased[T comparable]() MultiMap[T]

NewArrayBased explicitly constructs a MultiMap backed by the array-based implementation.