Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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?

like image 938
Harsh Shah Avatar asked Sep 26 '14 01:09

Harsh Shah


2 Answers

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
like image 137
DanLebrero Avatar answered Sep 28 '22 02:09

DanLebrero


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.

like image 26
tom Avatar answered Sep 28 '22 01:09

tom