Inspiration from Clojure

http://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

This presentation shows on what basis did Rich Hickey design the language Clojure which is similar to LISP but run on the JVM platform. It reveals one thing that is very interesting to our Java world:
How to implement immutable collections with which you can change at merely CONSTANT time.

Clojure implements immutable collections using ideal hash trees. First, we need to see how to locate an entry in an ideal hash tree.



Given a hash code (32-bit) for a map or index for a list, it's divided to 7 blocks, of which 6 blocks have 5-bit length and one block has 2-bit length. First we would search the first (right most) block which has 5 bits. The value of this block ranges from 0 to 31. It implies that each layer of this tree could have at most 32 nodes. So we directly place our attention to the calculated node. If the value of the first block is 7, we place our attention to the 8th node. If we find a leaf node, then that's it. It must be the one we are looking for. If not, we locate our attention on the second layer using the value of the second block. This way, we can find the desired entry in merely constant time, because the depth of the tree must be small. A tree with only 3 layers can contain 1,116,224 entries. It's large enough.

So how does it play the trick of changing this immutable tree in constant time?



Say we want to change the purple one to a new value. We create a new instance of the purple node with the new value object inside. Now, we know we can't change this purple one without changing his parent, the orange one. Also, we can't change the orange one without changing the green one. So, we end up with creating 3 new objects to substitute the green, orange and purple node. This way, we can change this tree in merely constant time!

With this new type of immutable collection implementation, we can substitute the traditional mutable ones in most cases except those have extremely strict performance restriction. What can we gain from using immutable collections in the field of enterprise application development? Due to the complexity of manipulating collections, we often want to define a domain object that carries some type of collection to an entity instead of a value object. Once the mutable entities loose control, the whole application is going to lose control. Google Collections 1.0 contains some immutable versions of the JDK collections but not enough. They just throw exceptions when you invoke the modification methods instead of returning a new, changed instance. That's because of the interface restrictions of the JDK Collections API. What about the brand new language, like Scala? It has the complete support for immutable collections. Unfortunately, the implementation is linear most of the time except for some special ones (like head and tail methods of the List class), which means every time you change the collection, it's copied entirely! This kind of performance cost is sometimes unacceptable to some criticial applications. Now here comes the savior. Although the implementation hasn't been migrated to Java, we can do this easily because Clojure is written in Java.