Wasn’t Clojure the first language to make use of immutable array mapped tries? I’d say that’s a pretty significant contribution to the realm of immutable data structures.
HAMTs by themselves are interesting, but not game-changing. In both wall clock time and asymptotic time analysis Clojure's immutable data structures are plenty fast, but not ahead of the pack of other immutable data structures when disallowing transients. I'm not sure, but I think that's the main reason that even though Bagwell came out with HAMTs in 2000, it wasn't until Clojure 7 (or 8?) years later that they were finally picked up.
Transients on top of HAMTs are a major step forward.
HAMT's probably weren't all that interesting because their main benefit over other mutable hashmaps was reduced worst-case scaling (no need to re-hash all keys to fit a larger underlying array), and reduced memory use at the cost of slower access times. I believe Clojure was the first language to use them as an _immutable_ hash map, and HAMT was picked specifically for performance. Transients didn't come until later (1.1.0?), and transients doesn't draw any specific benefit from a HAMT, it would have the same effect on any other datastructure.
Clojure also made use of the underlying HAMT data structure for vectors (skip hashing and use the index as a key).
I believe red-black trees was the state of the art immutable datastructure at the time, and HAMTs are much faster. Using two levels of a HAMT you can store 1024 elements, the similar number of levels required for a red-black tree is 10 if I'm not mistaken. HAMT also doesn't require rebalancing.
Not quite, there were a bunch of other persistent data structures. Finger trees, PATRICIA tries, etc. And the perf was competitive. See http://blog.ezyang.com/2010/03/the-case-of-the-hash-array-ma... for example. In there Haskell's IntMap (powered by a PATRICIA trie) just beats out Clojure's HAMT without transients. In practice they're probably more or less equal, because in order to make IntMap usable for arbitrary keys and not just ints, you need to have a hashing step first that generates an int from an arbitrary key, so you have the overhead of a single hash.
Ah you're totally right RE transients. I don't know why I had the notion they were tied to HAMTs... Nonetheless I view it as one of the big improvements that Clojure brought to the scene.
Thanks for the link. Interesting. I have implemented finger trees in Elm, and for the purposes of working as a hash map, it’s performance did not get near the performance of a HAMT. Works great as a deque though.
I also believe I looked into a Patricia impl, but I could be wrong. Will definetly take a new look :)
