Compressed Hash-Array Mapped Prefix-tree

Aliases: CHAMP

An iteration- and memory-optimized HAMT variant.

Category: persistent-map
Immutable: true
Persistent: true
Status: established
Introduced: 2015

Use cases

immutable maps
immutable sets
language runtimes

Real-world use

Scala 2.13: Immutable collection implementation (source)

Implementations

champ-trie (Rust) — repository/documentation

Sources

CHAMP: Compressed Hash-Array Mapped Prefix-tree [paper]

Confidence: high · Last reviewed: 2026-07-11