Constant time immutable hash map?


Scala claims to have “effectively constant” lookup, add, and remove for their immutable HashMap and HashSet implementations -

Does anyone know how Scala’s implementation managed to get those characteristics? I’m trying to determine if it would be possible to implement a collection like that (assuming the caller specified the hashing function) in Elm.


The docs say it uses a hash trie, which I suspect is more specifically a hash array mapped trie. Clojure also uses a HAMT map and describes performance characteristics as “effectively constant-time”. I’ve seen some good Clojure talks on the topic, although it seems I didn’t save links to any of them.


:thinking: I thought HAMTs had logarithmic access times…maybe I’m mistaken?

cc @robin.heggelund


Hash array mapped tries usually have a bunch of “slots” per level. So where a binary tree has branching factor of 2, a HAMT will usually have many more. Array.Hamt uses 32, for example. So, with a good hashing function, the depth becomes log32(n), which means that even for an array of 1024 elements, you only need 2 levels in the tree.

In practice, that’s “close enough” to call it constant time.


Yeah, the key word here is “effectively” (constant time). Another thing to mention is that n is never greater than 7 (32^6.4 maxes out an int).

I’m already exploring something like this for Elm, just need to find the time. An implementation for Elm already exists ( but there are bunch of things that can be improved to increase the performance, like a proper hash function and applying lessons learned from Array.Hamt. Expect to read more about this soon.