Efficient Immutable Map Implementation?

Question

I'm wondering if there is an implementation of a map which is:

• Immutable, so that I can use it in functional programming, and effortlessly ensure transactions and concurrency.
• Fast. I've checked out Binary Search Trees (RB, AVL) and Tries, but none of them seemed to be as fast as Hash Tables. Is there a map implementation that supports constant time for updates and retrievals? (or at least very fast logarithmic time)

In short, is there a functional data structure that can compare with Hash Maps in performance?

Answer 1

I haven't read it, but I think some people consider Purely Functional Data Structures as the bible for this kind of thing.

Answer 2

Anyway just to share with people, these are two interesting blog entries about Persistent Vectors implementation in Scala using Tries. They also mention Clojure's implementation, as well as the new IntMap in recent Scala releases.

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

For these data structures, I have tested with key as integers, but not yet strings. Because my real application is gonna use strings as keys, I'm not sure if the implementation will be more efficient than a Hash Map. What if I use the HashCode of the String as a key, then use a Persistent Vector to support the map? I will use a 32-way trie to implement the Persistent Vector. I guess collision would be very rare, and memory would only be spent accordingly. But I'm not sure about the actual amount needed copying on updates.

I'm gonna post my results soon.

Answer 3

Scala also has immutable maps, but they are slower than hash tables. I suspect the answer to your question is no, you won't find an immutable map implementation with O(1) expected time insert/query operations.

Answer 4

Clojure has immutable maps. (link). Not sure what underlying data structure it is using. Clojure source code will give you more information!