Kotlin mapOf and mutableMapOf Performance Trade-off

Recently, when doing a small coding challenge in Kotlin I was faced with the choice of mutableMapOf() vs. HashMap()

Photo by Marc Sendra Martorell on Unsplash

Being a Java old-timer, I first went with HashMap() or hashMapOf()

But then all the Kotlin tutorials start with mapOf() and mutableMapOf() ?

Afterwards, I had some interesting discovery to share here:

Behind the scene, both mapOf and mutableMapOf use Java’s LinkedHashMap data structure

Utimately, the comparison between mapOf, mutableMapOf() and HashMap() is down to LinkedHashMap vs. HashMap in Java.

These are the 2 most popular implementations of Map (or Dictionary or Hashtable if you will) data structure in Java. Here you can find a very detailed comparison between the too.

Difference between HashMap and LinkedHashMap in Java

The theory is that writing to a HashMap should be faster than a LinkedHashMap (as the former doesn’t care about maintaining insertion order). Also, the difference should be constant, not even linear.

Let’s measure them for fun anyway :)

Write performance showdown mutableMapOf() vs HashMap()

We’ll be using the following function to initialize 2 maps, one with HashMap() and the other with mutableMapOf()

Function we use to initialize Maps

One time run

fun main() {
    compareMapInits(1, 10)
    compareMapInits(1, 100)
    compareMapInits(1, 10_000)
    compareMapInits(1, 1_000_000)
}

Results in

>>> compareMapInits for 10 elements (repeated 1 times)
- mutableMapOf: time taken: 3ms
- HashMap: time taken: 0ms
<<<
>>> compareMapInits for 100 elements (repeated 1 times)
- mutableMapOf: time taken: 0ms
- HashMap: time taken: 0ms
<<<
>>> compareMapInits for 10000 elements (repeated 1 times)
- mutableMapOf: time taken: 2ms
- HashMap: time taken: 1ms
<<<
>>> compareMapInits for 1000000 elements (repeated 1 times)
- mutableMapOf: time taken: 107ms
- HashMap: time taken: 119ms
<<<

What stands out here are:

• For a small number of entries (10), mutableMapOf() takes more than 3 times to write compare to HashMap() ! But the difference is only 3ms in absolute terms. Let’s repeat the operation a number of times later as we might see a substantial difference.
• For a large number of entries (1mil): mutableMapOf only takes longer by a few milliseconds compared to HashMap() most of the time. Interestingly, it’s sometimes faster than HashMap() . Let’s measure the probability below as well.

Repetitive runs

1k times:

fun main() {
    compareMapInits(1000, 10)
    compareMapInits(1000, 100)
    compareMapInits(1000, 10_000)
    compareMapInits(1000, 1_000_000)
}

outputs

>>> compareMapInits for 10 elements (repeated 1000 times)
mutableMapOf() total time taken: 5 ms
HashMap() total time taken: 2 ms
How often is HashMap() slower? 2/1000
<<<
>>> compareMapInits for 100 elements (repeated 1000 times)
mutableMapOf() total time taken: 8 ms
HashMap() total time taken: 10 ms
How often is HashMap() slower? 10/1000
<<<
>>> compareMapInits for 10000 elements (repeated 1000 times)
mutableMapOf() total time taken: 335 ms
HashMap() total time taken: 225 ms
How often is HashMap() slower? 206/1000
<<<
>>> compareMapInits for 1000000 elements (repeated 1000 times)
mutableMapOf() total time taken: 81266 ms
HashMap() total time taken: 69712 ms
How often is HashMap() slower? 180/1000
<<<

• HashMap()write performance win increase significantly, in absolute terms when you repeat the operation many times.
• Interestingly, when writing thousands of entries or more, there’s a ~20% chance HashMap() will be slower! I do not yet know why. Happy to hear it from you in the comments

Why is HashMap() sometimes slower than LinkedHashMap()? TBC

Conclusion

HashMap() write is faster than mutableMapOf() a.k.a. Java’s LinkedHashMap

The difference is constant and insignificant when writing millions of elements.

Unless you repeatedly write to maps many times, it’s probably not worth it using HashMap() over mutableMapOf() in production. since a wrong-order bug might be disastrous.

“Premature optimization is the root of all evil” — Donald Ervin Knuth

On the other hand though, one should be careful about using ordered Map in production, IMHO. While it’s useful during a prototyping phase, over-reliance on Map data structure can be fragile and harmful for your production system in the long run. You never know what you’ll get from the API in a Map for example. Properly designed data classes should be preferred. For simple usage, List<KeyValuePair> can be a great choice IMO, as it explicitly states the importance of ordering here.

What do you guys think?

P.S. I wonder if mentioning the performance win for HashMap() vs. mutableMapOf() will gain you some bonus points in a data structure and algorithm interview though.

Further reading

They are not the only implementation of Map of course. TreeHashMap is useful in certain scenarios for example.

Difference between HashMap, LinkedHashMap and TreeMap