Hash Array Mapped Trie

Aliases: HAMT

A hash-partitioned trie supporting efficient structurally shared maps and sets.

Category

persistent-map

Immutable

true

Persistent

true

Status

established

Introduced

2001

Use cases

• functional maps
• immutable sets
• compiler environments

Real-world use

• Clojure: Core persistent map and set implementation (source)
• Scala collections: Immutable hash maps and sets (source)

Implementations

• Immutable.js (JavaScript) — repository/documentation
• rpds (Rust) — repository/documentation

Sources

1. Ideal Hash Trees [paper]

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