HashMap is the go-to choice for dictionaries on the JVM, but its implementation is not always optimal for use in the Android environment: excessive memory consumption, poor cache locality, GC pressure, and autoboxing of primitives. In this talk, we'll explore how these problems led to the creation of ArrayMap, and, subsequently, ScatterMap from androidx.collection.
ScatterMap is based on the Swiss Table architecture—the same approach now used by the standard libraries of Rust, Go, and C++. We'll examine its internals: open addressing with metadata grouping, hash splitting, and SIMD emulation on the JVM. We'll also look at benchmarks and usage examples.
Target audience: Android/Kotlin developers of any level interested in the internals of modern collections.