A hash array mapped trie (HAMT) is a shallow, bit-mapped tree used in variants of Clojure maps, sets, and vectors. It supports efficient lookup and updates in persistent collections. Its height grows slowly as a collection grows, so operations described as O(log₃₂ N) often feel constant-time in practice. section 11.3.1 section 8.2.3
The implementation matters when choosing or timing a collection:
- Hash maps scale to larger key counts with good average performance, but do not retain insertion order. Small maps may start as array-maps and be promoted to hash-maps as they grow. section 11.0
- Sorted maps use red-black trees instead of HAMTs. Their operations are also logarithmic, with a different growth profile: O(log₂ N) rather than O(log₃₂ N). section 11.3.1
- For a vector, `contains?` checks whether an index is in range; it does not search the vector for a value. section 8.2.3
Updating without changing the original map
(def m {:a "1" :b "2" :c "3"}) (assoc m :b "changed") ; => {:a "1" :b "changed" :c "3"} m ; => {:a "1" :b "2" :c "3"} `assoc` returns an updated map while `m` remains unchanged. This is the practical benefit of efficient persistent updates; ordinary map use does not require manipulating trie nodes. section 11.3.1 section 11.0
Keep the operation’s contract separate from the underlying structure. `(contains? {:a nil} :a)` checks that a key exists even though its value is `nil`; `(contains? [:a :b] 1)` checks a valid index, not whether `1` appears in the vector. A nested `assoc-in` update also depends on how many keys are in its path, beyond the cost of an individual associative update. section 8.2.3 section 11.3.1
