В 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