CODEWITHSUNDEEP
data-structuresclojure
Suvrat Apte
Suvrat Apte

Reputation: 171

Why does Clojure (1.8) create a HashMap if I manually create a map with > 8 keys, but an ArrayMap if I use zipmap to create map with > 8 keys?

I know that Clojure switches from PersistentArrayMap to PersistentHashMap when a map is greater than 8 in size (8 key-value pairs). This can be verified by:

(type {0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8})
=> clojure.lang.PersistentHashMap

But if I create the above map using zipmap:

(type (zipmap (range 9) (range 9)))
=> clojure.lang.PersistentArrayMap

I made sure that the construction is correct:

(= (zipmap (range 9) (range 9))
   {0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8})
=> true

If I use (range 10), it starts using PersistentHashMap. So for zipmap, the size has to be 9 or greater before it starts using PersistentHashMap.

I found this very weird. Why is there a difference in datastructure depending on whether I create a map manually or with zipmap?

I'm using Clojure 1.8.

Upvotes: 1

Views: 168

Answers (1)

Suvrat Apte
Suvrat Apte

Reputation: 171

This is because zipmap creates the map incrementally using assoc. Because of a bug, assoc switches from ArrayMap to HashMap for size > 9, not for 9. Look at this:

(type {0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7})  
=> clojure.lang.PersistentArrayMap       # size = 8

(type (assoc {0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7}
             8 8))
=> clojure.lang.PersistentArrayMap       # size = 9

(type (assoc {0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7}
             8 8 9 9))
=> clojure.lang.PersistentHashMap        # size = 10

The bug was fixed here: https://github.com/clojure/clojure/commit/ce9fbf61f113fdef1cbf8c1c0b4ea1a48831beef

Upvotes: 6

Related Questions