Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Efficient Immutable Map Implementation?

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?

like image 760
Phil Avatar asked Aug 20 '09 04:08

Phil


People also ask

Is HashMap immutable?

The answer is NO. Making keys in any hashing data structure will cause memory leak. If we make the keys mutable then the hashcode() of the key will no more be consistent over time which will cause lookup failure for that object from the data structure. Let's analyze this example.

How can we convert mutable Map to immutable in Java?

You can simply create a new HashMap from the existing Map using the copy constructor. HashMap<String, Object> = new HashMap<>(immutableMap);


1 Answers

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

like image 83
Vijay Mathew Avatar answered Sep 30 '22 04:09

Vijay Mathew