Search code examples
javatreemapimmutable.jsimmutable-collections

Immutable Tree Map for Java?

I am looking for an implementation of an immutable Tree Map in Java, that allows for copy-on-write style modifications with sharing of identical parts. So, in essence exactly what ImmutableJS does for JavaScript, just for Java.

If anyone happens to be unfamiliar with how ImmutableJS works, here is what I would like it to be in Java:

ImmutableTreeMap<String, String> map = new ImmutableTreeMap<>();
ImmutableTreeMap<String, String> map1 = map.put("hello", "world");
ImmutableTreeMap<String, String> map2 = map1.put("foo", "bar");
// the base maps should still remain the same
assertEquals(0, map.size());
assertEquals(1, map1.size());

In the above example, map2 would not copy the part of the tree that stores hello -> world, it would re-use that part.

Is there any such implementation available, or do I have to go ahead and create one from scratch?

Solution

  • your looking for a 'persistent' hash map, also called 'hash array mapped trie'.

    one should note that a 'tree' is not the same thing as a 'trie' data structure.

    you will find a few java HAMTs including ones from paguro, pcollections and javaslang projects, or you can use the canonical ones from clojure or scala compiled for the jvm