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 современных коллекций.