hashtriemap#

A generic concurrent hash trie map for Go, extracted and extended from internal/sync.HashTrieMap in the Go standard library.

go get dario.cat/x/hashtriemap

Requires Go 1.23 or later (uses range-over-func iterators).

Overview#

HashTrieMap[K, V comparable] is a concurrent map with the same surface API as sync.Map but with full generics, lock-free reads, and a producer/consumer pattern that batches writes per goroutine.

The trie is a 16-way (4 bits of hash per level) tree of indirect (branch) nodes with entry (leaf) nodes at the tips. Keys are routed by maphash.Comparable. True hash collisions are chained via an overflow linked list on the leaf. The trie structure is never shrunk during normal operation — deletions set an atomic tombstone and Compact prunes lazily at cycle boundaries.

Quick start#

var m hashtriemap.HashTrieMap[string, int]

m.Store("hits", 1)

v, ok := m.Load("hits")   // v=1, ok=true
m.Delete("hits")

The zero value is ready to use. The map must not be copied after first use.

API#

Reads#

Method	Description
`Load(key) (V, bool)`	Lock-free. Returns the value and whether the key exists.
`LoadOrStore(key, value) (V, bool)`	Returns the existing value if present; otherwise stores and returns the new value.

Writes#

Method	Description
`Store(key, value)`	Store a value. Overwrites existing entries in-place (atomic pointer swap, no allocation).
`Swap(key, new) (V, bool)`	Store and return the previous value. Fast path is lock-free for existing keys.
`CompareAndSwap(key, old, new) bool`	Swap only if the current value equals `old`.

Deletes#

Deletes mark entries as tombstoned (atomic flag). The entry node stays in the trie until Compact is called. Load, Range, and All skip tombstoned entries transparently.

Method	Description
`Delete(key)`	Mark key as deleted. No-op if absent.
`LoadAndDelete(key) (V, bool)`	Delete and return the previous value.
`CompareAndDelete(key, old) bool`	Delete only if the current value equals `old`.

Iteration#

Method	Description
`Range(func(K, V) bool)`	Call `f` for each live entry. Stop early by returning `false`.
`All() func(yield func(K, V) bool)`	Returns a range iterator for use in `for k, v := range m.All()`.
`Snapshot() map[K]V`	Copy all live entries into a plain `map[K]V`. Use only when random access is needed; prefer `Range`/`All` for pure iteration.

Lifecycle#

Method	Description
`Clear()`	Replace the root, effectively emptying the map.
`Compact()`	Prune tombstoned entries and collapse empty branch nodes. Call at cycle boundaries (see below).

Producer pattern#

Producer is a per-goroutine write buffer. Multiple writes to the same key within a single cycle are coalesced — only the last value is flushed to the shared map. This reduces hash computations, trie traversals, mutex acquisitions, and allocations proportional to the key reuse rate.

var m hashtriemap.HashTrieMap[string, int]

var wg sync.WaitGroup
for g := range numProducers {
    wg.Add(1)
    go func() {
        defer wg.Done()
        p := m.NewProducer()
        defer p.Flush()           // commit buffered writes on exit
        for _, event := range work {
            p.Store(event.Key, event.Value)
        }
    }()
}
wg.Wait()

// Producers are done — trie is stable. Iterate with no copy.
m.Range(func(k string, v int) bool {
    process(k, v)
    return true
})

// Prune tombstones before the next cycle.
m.Compact()

Producer.Delete tombstones the key in the shared map immediately. A subsequent Store to the same key in the same producer will re-create the entry on Flush.

Implementation notes#

In-place value update — entry.value is an atomic.Pointer[V]. Overwriting an existing key swaps the pointer without allocating a new node or acquiring the parent mutex.

Tombstone deletion — Delete/LoadAndDelete set an atomic.Bool on the entry. The trie structure is unchanged; Compact prunes lazily.

Per-node mutexes — structural changes (inserting a new key, expanding a leaf into a subtree) acquire only the parent indirect node's mutex. Reads and in-place updates are lock-free.

Pointer tagging — the child type (entry vs. indirect) is encoded in the low bit of the stored pointer rather than in a separate header struct, saving 8 bytes per entry.

sync.Pool — entry and indirect nodes are pooled per generic instantiation. Compact returns pruned nodes to the pool.

When to use this#

Scenario	Recommendation
Read-heavy, stable key set	`sync.Map` or this map both work; this map has full generics.
Cycle-based producer/consumer (batch writes, then scan)	This map — use `Producer` + `Compact`.
Frequent deletes with bounded memory	Call `Compact` between cycles; otherwise tombstones accumulate.
Low-cardinality key set with high write contention	`map` + `sync.RWMutex` is simpler and often faster.
Need ordered iteration	Neither this map nor `sync.Map`; use a sorted structure.

Configure Feed