A Better Hash Map — 1

Hash maps are extremely common data structures, and Jetpack Compose unsurprisingly takes advantage of them for various tasks. Kotlin makes it easy to create a new mutable hash map by calling the mutableMapOf() function. Most developer will — and should — stop there, and use the map however they need to. Things are however a bit different when working on a toolkit like Jetpack Compose as we need to ensure the toolkit’s behavior is as unintrusive as possible for the app.

So let’s peek at the implementation of mutableMapOf():

1public inline fun <K, V> mutableMapOf(): MutableMap<K, V> = LinkedHashMap()

LinkedHashMap is an expect class that on Android defers to the API of the same name:

1public actual typealias LinkedHashMap<K, V> = java.util.LinkedHashMap<K, V>

Since this API is battle-tested and offers good performance characteristics, it is a good choice as a standard hash map in Kotlin¹. Unfortunately the implementation of LinkedHashMap is not memory-friendly, as each entry inserted into the map creates a new LinkedHashMapEntry instance (this is also true with the base HashMap class and its HashMap.Node). For our use case, this has several negative consequences:

• Each entry uses more memory than necessary. Storing an Int in a LinkedHashMap requires 3 extra pointers, and a copy of the hash, on top of the overhead of an Object.
• Memory accesses, especially iterations, are not cache friendly, especially over time as the heap gets scrambled.
• It puts pressure on the garbage collector, which can be painful especially on older devices and/or older versions of the Android Runtime (ART).

To work around these issues, we created a new hash map called ScatterMap designed to be much more memory-efficient. This new API is part of the androidx.collection library as of version 1.4, which recently reached Release Candidate status.

Some of the characteristics of ScatterMap are:

• The overhead per entry is 1 byte.
• Insertion is allocation-free unless the map needs to grow its internal storage.
• Iteration is allocation-free.
• Allocation-free versions of common APIs (removeIf() for instance is inline to avoid allocating the predicate lambda).
• Keys and values are stored linearly, offering a good memory cache behavior when iterating over the map, with no indirections required.
• Performance on insertion/removal/retrieval/iteration that’s better than or on par with LinkedHashMap.
• API consistent with Kotlin’s maps (factory functions, ScatterMap vs MutableScatterMap, etc.).
• Offers specialized variants to store primitives (IntIntMap or ObjectFloatMap for instance) with no auto-boxing.

Here are benchmark numbers² on a Pixel 6 running Android 13:

Note that in the context of this benchmark, the iteration test is likely the best number LinkedHashMap can produce since all elements are created immediately one after the other, giving them good memory locality. ScatterMap’s performance will remain the same over time.

The main drawback of ScatterMap is that it does not implement the standard Map interface, which forces memory-unfriendly behaviors. It is possible to get a Map (or MutableMap) interface out of a ScatterMap by calling asMap(), but the default API tries to provide the most common features found in Kotlin with regular maps, such as forEach(), removeIf(), any(), count(), etc.

So is ScatterMap a better hash map? Yes… if memory allocations, memory usage, and memory access are something you need to optimize for. I believe it is a great tool to be aware of, but which data structure to use is ultimately your choice and responsibility.

In future installments, I’ll explain where ScatterMap came from, how it works internally, how it was optimized to produce efficient ARM 64 assembly⁵, and how it could be even better with SIMD instructions.