1 байт вместо 32: анатомия ScatterMap

HashMap — привычный выбор для ассоциативных массивов на JVM, но его реализация не всегда оптимальна для Android-среды: избыточное потребление памяти, проблемы с cache locality, GC pressure и autoboxing примитивов.

Разберем, как эти проблемы привели к появлению ArrayMap, а затем ScatterMap из androidx.collection.

ScatterMap основан на архитектуре Swiss Table — том же подходе, который сейчас используют стандартные библиотеки Rust, Go и C++. Разберем его внутреннее устройство: open addressing с группировкой метаданных, split хэша, эмуляцию SIMD на JVM. Рассмотрим бенчмарки и примеры использования.

Целевая аудитория: Android- и Java/Kotlin-разработчики любого уровня, заинтересованные в internals современных коллекций.