В 2018 году в androidx появился новый пакет collection, который содержал несколько специфичных структур данных, переписанных на Kotlin, таких как LongSparseArray, SimpleArrayMap и SparseArrayCompat.
На тот период Kotlin только начинал набирать обороты в Android разработке и добавление новых более эффективных коллекций, полностью написанных на нём было одним из шагов по внедрению языка.
С тех пор прошло более 6 лет и в январе текущего года был выпущен новый релиз с мощной заменой HashMap, о которой я расскажу чуть позже:
dependencies {
implementation("androidx.collection:collection:1.4.0")
}
Список релизов и изменений можете глянуть на официальном сайте.
Зачем вообще нужно было строгать новые коллекции и переписывать старые?
На это есть как минимум три причины:
- Эффективный расход памяти - думаю не секрет что даже при наличии 8Gb ОЗУ на вашем телефоне память не бесконечна, поэтому новые коллекции были написаны, придерживаясь принципа "минимум объектов".
- Эффективная реализация алгоритмов - старые реализации могут содержать не очень эффективные алгоритмы и устаревшие решения, требующие рефакторинга.
- 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 мира.
Основные преимущества:
- Методы forEach, forEachIndexed и аналогичные реализованы без использования итераторов + они помечены ключевым словом inline для уменьшения загрузки стэка вызовов.
- Есть отдельные реализации для примитивных типов Int, Long и Float без autoboxing / unboxing механизма, который характерен для ArrayList<Integer> например.
- Перегрузка операторов += и -= для более лаконичного кода, также классы коллекций помечены ключевым словом sealed, поэтому за пределами androidx.collection библиотеки не удастся создать новых наследников и нарушить четко определённую логику.
Сводка классов, если захотите залезть в исходники:
Пары значений
Библиотека androidx.collection включает три реализации пар значений для примитивных типов, возможно на момент чтения этой статьи что-то изменилось, но базовые идеи реализации редко меняются.
1. IntIntPair хранит два значения типа Int в виде одного числа Long благодаря простейшей битовой математики: первое число хранится в старших 32 битах Long, а второе в младших:
// ссылка на код https://pastebin.com/s2P4Ac9w
@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:
// ссылка на код https://pastebin.com/M9SV4RqN
// сначала извлекается битовое представление типа 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 соответственно
Полагаю вы уже догадались, что все эти реализации были созданы, также как и ранее рассмотренные списки, под копирку на основе обобщённой версии:
// ссылка на код https://pastebin.com/imeu9sRr
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-ми битовая последовательность:
- Пустое значение - 10000000
- Конец таблицы - 11111111, используется при итерации по таблице, чтобы остановиться на последней записи
- Удалённое значение - 11111110
- Заполненное значение - хранит младшие 7 бит хэша ключа, вернёмся к этому чуть позже
Думаю не секрет, что Long является 64 битным числом и было бы печально хранить в нём только 8 бит, поэтому была введена концепция группы:
Группа - набор из 8-ми битных состояний или слотов, как это принято в терминологии ScatterMap, в данном случае это число Long, которое может хранить 8 слотов, а это значит что размер группы равен 8.
Есть интересный момент насчет групп в исходном коде ScatterMap:
// размер группы, который мы уже вычислили
const val GroupWidth = 8
// при чтении кода сложно было абстрагироваться от числа Long из-за битовой арифметики, поэтому этот typealias ни раз меня сбивал с толку
typealias Group = Long
При последовательном проходе по массиву метаданных за одну итерацию обычно извлекается одна группа, то есть число типа Long, которое не всегда может быть получено по единому индексу из-за некоторого смещения, о котором речь пойдёт ниже.
Метод поиска индекса ключа
Для более глубокого понимания как работает ScatterMap рассмотрим основной метод для поиска индекса:
// ссылка на код https://pastebin.com/QSuY7RCB
// метод возвращает индекс ключа, по которому также можно получить значение, так как массивы 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, основанный на вычислении следующего свободного индекса в массиве.
Хэш-функция и итоги
Теперь рассмотрим хэш-функцию:
// ссылка на код https://pastebin.com/TcFJwedM
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 мог быть узлом связанного списка или дерева.
Итоговые замечания:
- Все остальные операции: вставка и удаление работают практически также, как и метод поиска индекса ключа с небольшой лишь разницей: происходит не только чтение массивов metadata, keys и values но и запись нового значения либо его зануление + при превышении размера хэш-таблицы размеры массивов увеличиваются.
- forEach, forEachIndexed также как и в предыдущих коллекциях являются inline функциями и работают без создания итераторов.
Множества
Реализация практически такая же как у хэш-таблиц, только вместо двух массивов keys и values под капотом лежит один:
// ссылка на код https://pastebin.com/DW7RgGe3
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 библиотеки:
- SparseArrayCompat, LongSparseArray, SimpleArrayMap, ArraySet и LruCache - переписанные версии из android.util пакета на Kotlin возможно с некоторыми оптимизациями.
- CircularArray и CircularIntArray - динамические массивы с возможностью добавить значение в начало и в конец за O(1) время, реализация основана на двух индексах head и tail, которые перемещаются по массиву в противоположных направлениях: первый уменьшается, а второй увеличивается, при совпадении индексов массив удваивается.
Заключение
Надеюсь статья была полезна для вас и мне удалось насколько возможно описать механизмы работы новых структур данных из библиотеки androidx.collection, пишите своё мнение в комментариях и всем хорошего кода!
Полезные ссылки: