What is the difference between the hash-map and array-map in clojure?

Question

Clojure has an array-map and hash-map, I couldn't figure out the difference between the two. Could anyone explain if possible with an example as to when either of them would be used?

Antihalation

Answer 1

array-maps keep the insertion order but you shouldn't rely on that behaviour except for very simple cases where you know the map is not going to be modified. Use an ordered collection if you really need this behaviour.

array-maps should be used for very small maps (8 keys currently) as the lookup and "modification" performance is better than a hash-map of the same size:

(def arraymap (array-map :f 1 :g 2 :h 4 :y 5 :w 4))     
(def hashmap (hash-map :f 1 :g 2 :h 4 :y 5 :w 4))
 
(defn add-2-keys [m]
  (assoc m :new 2 :w 4))

(defn access-all-keys [m]
  (mapv m [:f :g :h :y :w :not-there]))

(use 'criterium.core)

; Modification 
(bench (add-2-keys array map))
Execution time mean : 125.640082 ns    
(bench (add-2-keys hashmap))
Execution time mean : 150.918197 ns

; Access
(bench (access-all-keys arraymap))
Execution time mean : 260.547035 ns
(bench (access-all-keys hashmap))
Execution time mean : 305.350156 ns

Find

It's actually 8 keys. The internal array is 16, but it holds both keys and values. I think it's also worth pointing out that the ordered behaviour is basically a side-effect of its implementation and its existence is explained as an optimization alternative for hash-map with small sets. It's not an ordered map implementation although it behaves so with smaller sets. Equally there's nothing wrong with using it as a map for smaller or larger sets as it revers to hash-map when assoc'ing past 8 keys. – Synchronize

Answer 2

Array maps and hash maps have the same interface, but array maps have O(N) lookup complexity (i.e. it is implemented as an simple array of entries), while hash maps have O(1) lookup complexity.

Array maps have the advantage (which you don't need most of the time) that they maintain insertion order, so when you perform any operation that iterates over the map (say, map or reduce), you can process the entries in the same order as when you inserted them.

Note that if you "modify" (in the persistent-collection sense) an array map repeatedly, at some point it will become a hash map. e.g.

user=> (type (apply assoc (array-map) (zipmap (range 10) (range 10))))
clojure.lang.PersistentArrayMap
user=> (type (apply assoc (array-map) (zipmap (range 100) (range 100))))
clojure.lang.PersistentHashMap

Basically, always prefer hash maps if you don't care about key order. Also, if you do use array maps, keep in mind the lookup performance tradeoff.

Monjan