Новые коллекции в Android

В 2018 году в androidx появился новый пакет collection, который содержал несколько специфичных структур данных, переписанных на Kotlin, таких как LongSparseArray, SimpleArrayMap и SparseArrayCompat.

На тот период Kotlin только начинал набирать обороты в Android разработке и добавление новых более эффективных коллекций, полностью написанных на нём было одним из шагов по внедрению языка.

С тех пор прошло более 6 лет и в январе текущего года был выпущен новый релиз с мощной заменой HashMap, о которой я расскажу чуть позже:

dependencies {     implementation("androidx.collection:collection:1.4.0") }

Список релизов и изменений можете глянуть на официальном сайте.

Зачем вообще нужно было строгать новые коллекции и переписывать старые?

На это есть как минимум три причины:

1. Эффективный расход памяти — думаю не секрет что даже при наличии 8Gb ОЗУ на вашем телефоне память не бесконечна, поэтому новые коллекции были написаны, придерживаясь принципа «минимум объектов».

2. Эффективная реализация алгоритмов — старые реализации могут содержать не очень эффективные алгоритмы и устаревшие решения, требующие рефакторинга.

3. Kotlin Multiplatform — при написании общего кода на Kotlin под разные платформы требуется минимальное количество зависимостей от платформенных структур данных, например таких как android.util.SparseArray.

А теперь перейдём к самой вкусной части статьи, разберёмся что за магические штуки наколдовали Google кодеры и самое главное как они работают под капотом.

Полетели!

Списки или динамические массивы

Было добавлено несколько реализаций:

// обобщённая реализация val games = objectListOf("Atomic Heart", "BioShock", "Mafia II") val movies = objectListOf("Dune: Part Two", "1 + 1")  val moviesAndGames = mutableObjectListOf<String>() // переопределённые операторы plusAsssign moviesAndGames += movies moviesAndGames += games moviesAndGames += "Far Cry 3" moviesAndGames += "The Shawshank Redemption"  // изменяемая версия mutableIntListOf() val fibonacciIntegerNumbers = intListOf(1, 1, 2, 3, 5)  // изменяемая версия mutableLongListOf() val fibonacciLongNumbers = longListOf(1, 1, 2, 3, 5)  // изменяемая версия mutableFloatListOf() val fibonacciFloatingNumbers = floatListOf(1f, 1f, 2f, 3f, 5f)  /* P.S. реализации для примитивных типов были созданы под копирку  на основе обобщённой objectListOf() */

Под капотом обычный массив, который увеличивается в полтора раза при превышении размера, а при удалении значений из середины происходит сдвиг массива, можно сказать что это аналогия ArrayList из Java мира.

Основные преимущества:

1. Методы forEach, forEachIndexed и аналогичные реализованы без использования итераторов + они помечены ключевым словом inline для уменьшения загрузки стэка вызовов.

2. Есть отдельные реализации для примитивных типов Int, Long и Float без autoboxing / unboxing механизма, который характерен для ArrayList<Integer> например.

3. Перегрузка операторов += и -= для более лаконичного кода, также классы коллекций помечены ключевым словом sealed, поэтому за пределами androidx.collection библиотеки не удастся создать новых наследников и нарушить четко определённую логику.

Сводка классов, если захотите залезть в исходники:

1. ObjectList / MutableObjectList для обобщенных списков

2. IntList / MutableIntList для примитивного типа Int

3. FloatList / MutableFloatList для примитивного типа Float

4. LongList / MutableLongList для примитивного типа Long

Пары значений

Библиотека androidx.collection включает три реализации пар значений для примитивных типов, возможно на момент чтения этой статьи что-то изменилось, но базовые идеи реализации редко меняются.

1. IntIntPair хранит два значения типа Int в виде одного числа Long благодаря простейшей битовой математики: первое число хранится в старших 32 битах Long, а второе в младших:

@JvmInline value class IntIntPair(val packedValue: Long) {        constructor(first: Int, second: Int) : this(packInts(first, second))          // первое значение хранится в старших битах числа Long     val first: Int         get() = (packedValue shr 32).toInt()      // второе значение хранится в младших битах числа Long     val second: Int         get() = (packedValue and 0xFFFFFFFF).toInt() }  inline fun packInts(val1: Int, val2: Int): Long {     /* чтобы положить два 32-битных числа в одно 64-битное      первое число преобразуем к 64-битному и делаем сдвиг влево на 32 бита,      второе также расширяем до 64 бит с занулением старших 32 бит,      если такие случайно там оказались, после этого совмещаем биты обеих чисел      с помощью логического OR */     return (val1.toLong() shl 32) or (val2.toLong() and 0xFFFFFFFF) }

Обратите внимание, что IntIntPair является inline value классом, а это значит что поле packedValue будет встраиваться в место вызова без создания объекта класса, что избавляет GC от ненужной работы.

2. FloatFloatPair аналогично IntIntPair хранит два значения типа Float в одном значении типа Long, отличие заключается только в дополнительной трансформации числа Float в битовое представление типа Int:

/* сначала извлекается битовое представление типа Int из старших 32 бит числа,  затем трансформируется во Float тип */ inline val first: Float     get() = floatFromBits((packedValue shr 32).toInt())  /* алгоритм аналогичен извлечению первого значения,  только битовое представление извлекается из младших 32 бит */ inline val second: Float     get() = floatFromBits((packedValue and 0xFFFFFFFF).toInt())  inline fun packFloats(val1: Float, val2: Float): Long {     /* превращаем каждое значение Float в битовое представление типа Int,      для дальнейших битовых операций переводим в Long */     val v1 = val1.toRawBits().toLong()     val v2 = val2.toRawBits().toLong()     // также как в IntIntPair запаковываем два числа типа Int в один Long     return (v1 shl 32) or (v2 and 0xFFFFFFFF) }  inline fun floatFromBits(bits: Int): Float = java.lang.Float.intBitsToFloat(bits) inline fun Float.toRawBits(): Int = java.lang.Float.floatToRawIntBits(this)

Более детальное описание алгоритма превращения числа Float в битовое представление Int и обратно содержится в документации по методам Float.intBitsToFloat и Float.floatToRawIntBits.

3. LongLongPair — простейшая реализация для двух чисел типа Long:

class LongLongPair(val first: Long, val second: Long) { ... }

Выигрывает перед Pair<Long, Long> в памяти, так как для всех обобщенных типов используются классы обертки, а не примитивные типы.

Во всех вышеперечисленных реализациях пар значений есть переопределение операторов component1 и component2 для конструкций деструктуризации:

val (firstInt, secondInt) = IntIntPair(3, 7) val (firstLong, secondLong) = LongLongPair(2021, 2023) val (firstFloat, secondFloat) = FloatFloatPair(0.33f, 0.45f)

Хэш-таблицы

Настал момент заглянуть в самую сложную алгоритмическую часть этой статьи, готов представить вам, новая реализация HashMap:

// обобщённый вариант хэш-таблицы val scatterMap: ScatterMap<String, String> = mutableScatterMapOf()  // реализации хэш-таблиц для примитивных типов, аналогичные варианты есть для Long и Float intIntMapOf() intFloatMapOf() intLongMapOf() intObjectMapOf<String>()  // варианты для случаев, когда в качестве ключа один из примитивных типов: Int, Long или Float intObjectMapOf<String>() longObjectMapOf<String>() floatObjectMapOf<String>()  /* P.S. похожие штуки на intIntMapOf(), intLongMapOf() и intObjectMapOf()  есть в android.util пакете - SparseIntArray, SparseLongArray  и SparseArray соответственно */

Полагаю вы уже догадались, что все эти реализации были созданы, также как и ранее рассмотренные списки, под копирку на основе обобщённой версии:

sealed class ScatterMap<K, V> {     // меняются буквально только типы для массивов ключей и значений     var keys: Array<Any?> = EMPTY_OBJECTS     var values: Array<Any?> = EMPTY_OBJECTS     // остальная логика остаётся неизменной }  sealed class IntIntMap {     // типы были изменены на примитивные     var keys: IntArray = EmptyIntArray     var values: IntArray = EmptyIntArray     // логика абсолютно не поменялась и была скопирована из ScatterMap }  sealed class IntObjectMap<V> {     // такая же история...     var keys: IntArray = EmptyIntArray     var values: Array<Any?> = EMPTY_OBJECTS }  /* P.S. Такой подход может показаться избыточным так как  одинаковая логика копируется прямо в лоб, на самом деле особого проигрыша  в этом нет и любые неиспользуемые классы легко выпиливаются  современными системами сборки. */

Следовательно мы можем взять реализацию ScatterMap / MutableScatterMap и рассмотреть её под капотом, логика остальных ничем не будет отличаться.

Приступим к изучению!

Как ScatterMap хранит информацию о парах ключ / значение

Механизм хранения информации о записях ключ / значение отличается от HashMap, где все лежит в одном массив

е Map.Entry объектов, в ScatterMap для этого используется отдельный массив метаданных:

internal var metadata: LongArray = EmptyGroup

где единицей хранимой информации является 8 бит, которыми можно сохранить одно состояние ровно для одной записи хэш-таблицы.

Список возможных состояний и их 8-ми битовая последовательность:

1. Пустое значение — 10000000

2. Конец таблицы — 11111111, используется при итерации по таблице, чтобы остановиться на последней записи

3. Удалённое значение — 11111110

4. Заполненное значение — хранит младшие 7 бит хэша ключа, вернёмся к этому чуть позже

Думаю не секрет, что Long является 64 битным числом и было бы печально хранить в нём только 8 бит, поэтому была введена концепция группы:

Группа — набор из 8-ми битных состояний или слотов, как это принято в терминологии ScatterMap, в данном случае это число Long, которое может хранить 8 слотов, а это значит что размер группы равен 8.

Есть интересный момент насчет групп в исходном коде ScatterMap:

// размер группы, который мы уже вычислили const val GroupWidth = 8  /* при чтении кода сложно было абстрагироваться от числа Long из-за  битовой арифметики, поэтому этот typealias ни раз меня сбивал с толку */ typealias Group = Long

При последовательном проходе по массиву метаданных за одну итерацию обычно извлекается одна группа, то есть число типа Long, которое не всегда может быть получено по единому индексу из-за некоторого смещения, о котором речь пойдёт ниже.

Метод поиска индекса ключа

Для более глубокого понимания как работает ScatterMap рассмотрим основной метод для поиска индекса:

/* метод возвращает индекс ключа, по которому также можно получить значение,  так как массивы keys и values сопоставимы по индексам */ inline fun findKeyIndex(key: K): Int {     // хэш-функция будет рассмотрена ниже     val hash = hash(key)     /* получаем младшие 7 бит хэша, которые используются      для поиска нужного слота в массиве метаданных */     val hash2 = h2(hash)      /* в качестве маски для вычисления смещения будет использоваться      размер хэш-таблицы */      val probeMask = _capacity     // берём старшие 25 бита хэша и рассчитываем смещение на основе маски     var probeOffset = h1(hash) and probeMask     var probeIndex = 0      while (true) {         /* получаем группу по смещению, это не совсем тривиальный алгоритм,          так как смещение не всегда кратно числу 8, в таком случае часть байтов берётся из одного числа Long,          другая из другого, например для массива metadata, который состоит из Long0 и Long1          группа по смещению 1 будет содержать 7 старших байтов из Long0 и 1 младший байт из Long1 */         val g = group(metadata, probeOffset)         /* ищем в группе нужный слот (состояние записи ключ / значение),          ранее я уже приводил 4 возможных состояния и там было указано          что в случае заполненного значения слот должен содержать младшие 7 бит хэша ключа */         var m = g.match(hash2)         // если нужный слот был найден прыгаем в цикл         while (m.hasNext()) {             /* в отличии от HashMap, где в случае совпадения хэшей              у нескольких ключей создаётся связанный список, в ScatterMap для этого              был введён специальный алгоритм (quadratic probing), суть которого состоит в том,              что при совпадении хэшей вычисляется новый индекс умножением текущего на степень двойки,              если там уже есть значение вычисление будет продолжаться до тех пор пока не найдется пустое местечко */             val index = (probeOffset + m.get()) and probeMask             // реальное совпадение ключа означает равенство двух методов hashCode() и equals(), никогда не забывайте об этом             if (keys[index] == key) {                 return index             }             m = m.next()         }         // если такого хэша нет в группе, значит ключ не был добавлен в хэш-таблицу         if (g.maskEmpty() != 0L) {             break         }          probeIndex += GroupWidth         probeOffset = (probeOffset + probeIndex) and probeMask     }      return -1 }

Обобщая всё вышесказанное можно сказать, что основной механизм работы ScatterMap основан на хранении состояния (слота) записи ключ / значение в отдельном массиве metadata типа Long, доступ к которому основан на битовой арифметике, а для решения коллизий используется алгоритм quadratic probing, основанный на вычислении следующего свободного индекса в массиве.

Хэш-функция и итоги

Теперь рассмотрим хэш-функцию:

inline fun hash(k: Any?): Int {     // константа MurmurHashC1 была добавлена для сокращения коллизий     val hash = k.hashCode() * MurmurHashC1     /* к старшим битам подмешиваются младшие для более      эффективной работы алгоритма quadratic probing */     return hash xor (hash shl 16) }  // константа была взята из MurmurHash алгоритма:  // https://en.wikipedia.org/wiki/MurmurHash#Algorithm const val MurmurHashC1: Int = 0xcc9e2d51.toInt()

Хочу добавить, если не проговорил это явно, все данные: ключи и значения лежат в двух массивах keys и values без какой-либо вложенности как это было в HashMap, где Map.Entry мог быть узлом связанного списка или дерева.

Итоговые замечания:

1. Все остальные операции: вставка и удаление работают практически также, как и метод поиска индекса ключа с небольшой лишь разницей: происходит не только чтение массивов metadata, keys и values но и запись нового значения либо его зануление + при превышении размера хэш-таблицы размеры массивов увеличиваются.

2. ScatterMap не сохраняет порядок добавления новых значений, как это делает LinkedHashMap например.

3. forEach, forEachIndexed также как и в предыдущих коллекциях являются inline функциями и работают без создания итераторов.

Множества

Реализация практически такая же как у хэш-таблиц, только вместо двух массивов keys и values под капотом лежит один:

sealed class ScatterSet<E> {      // вся битовая арифметика состояний (слотов) абсолютна такая же как у ScatterMap     var metadata: LongArray = EmptyGroup       // меняется только количество массивов, так как множеству не нужны ключи     var elements: Array<Any?> = EMPTY_OBJECTS  }

Данная реализация также как и ScatterMap не сохраняет порядка при добавлении новых значений.

Придерживаясь канону построения структур данных для примитивных типов получаем следующие реализации:

// обобщённая реализация scatterSetOf<String>() mutableScatterSetOf<String>()  /* аналогично спискам и хэш-таблицам реализации  для примитивных типов сделаны под копирку */ intSetOf() mutableIntSetOf()  longSetOf() mutableLongSetOf()  floatSetOf() mutableFloatSetOf()

Другие коллекции

Кратко пробегусь по оставшимся коллекциям из androidx.collection библиотеки:

1. SparseArrayCompat, LongSparseArray, SimpleArrayMap, ArraySet и LruCache — переписанные версии из android.util пакета на Kotlin возможно с некоторыми оптимизациями.

2. CircularArray и CircularIntArray — динамические массивы с возможностью добавить значение в начало и в конец за O(1) время, реализация основана на двух индексах head и tail, которые перемещаются по массиву в противоположных направлениях: первый уменьшается, а второй увеличивается, при совпадении индексов массив удваивается.

Замеры

Сравнение коллекций с аналогами из Java мира по объёму используемой памяти в байтах:

Несколько замечаний:

1. ObjectList имеет начальную ёмкость 16 в отличии от ArrayList, у которого она составляет 10, поэтому при каждом увеличении списка ObjectList может занимать немного больше места, но проигрыша в этом нет, так этот параметр можно изменить в конструкторе.

2. HashMap не так сильно проигрывает ScatterMap (в 1.2 — 1.3 раза) как я полагал, зато ScatterSet выигрывает HashSet практически в 1.5 раза!

3. Коллекции для примитивных типов в 2-7 раз превосходят обобщённые варианты, что позволяет сократить приличный кусок памяти.

Заключение

Надеюсь статья была полезна для вас и мне удалось насколько возможно описать механизмы работы новых структур данных из библиотеки androidx.collection, пишите своё мнение в комментариях и всем хорошего кода!

Полезные ссылки:

1. Мой телеграм канал

2. Мой Github репозиторий по алгоритмам и структурам данных

3. Описание и история релизов библиотеки

4. Inline value classes

5. Inline functions

6. Autoboxing / unboxing механизм

7. Kotlin Multiplatform

8. Динамический массив

9. Хэш-таблица

10. Алгоритм quadratic probing

11. Алгоритм MurmurHash