Higher-Order » Blog Archive » Understanding Clojure’s Pe...     One of the unique features of Clojure is that the core data structures are persistent (immutable with efficient structural sharing). This includes data structures Vector and Map that are mutable in most other languages. To be useful, operations on persistent data structures need to have performance characteristics that are similar to their mutating counterparts; e.g., the cost of random access on a persistent vector (put/get) needs to be comparable to random access to a mutable vector. Clojure manages to achieve this. Here we focus on understanding the Clojure implementation of Vector: PersistentVector. The basics. PersistentVector stores its elements in arrays, each array having at most size 32. One can think of the arrays as forming a wide balanced tree with each node having at most 32 children.     http://blog.higher-order.net/2009/02/01/understanding-clojur...     tags: vector clojure Higher-Order » Blog Archive » Understanding Clojure’s Pe...     PersistentHashMap is a persistent version of the classical hash table data structure. Persistent means that the data structure is immutable, yet has efficient non-destructive operations that correspond to the operations on the classical hash table. E.g., put(K,V) in hash table corresponds to a side-effect free function assoc(P, K, V) which computes from P a new PersistentHashMap P’ which is like P except that it maps key K to value V. The word “efficient” means “on par” with their mutating counterparts. For Clojure data structures, Rich tries to make them within 1-4 of the Java data structure operations; and read-only operations can even be faster than Java’s. Later I will cover ‘transients’ which are a new optimization that make “batch” operations faster.     http://blog.higher-order.net/2009/09/08/understanding-clojur...     tags: hash clojure