Новые коллекции в Android
В 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()
// переопределённые операторы 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
например. Перегрузка операторов += и -= для более лаконичного кода, также классы коллекций помечены ключевым словом sealed, поэтому за пределами androidx.collection библиотеки не удастся создать новых наследников и нарушить четко определённую логику.
Сводка классов, если захотите залезть в исходники:
ObjectList / MutableObjectList для обобщенных списков
IntList / MutableIntList для примитивного типа Int
FloatList / MutableFloatList для примитивного типа Float
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
Во всех вышеперечисленных реализациях пар значений есть переопределение операторов 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 = mutableScatterMapOf()
// реализации хэш-таблиц для примитивных типов, аналогичные варианты есть для Long и Float
intIntMapOf()
intFloatMapOf()
intLongMapOf()
intObjectMapOf()
// варианты для случаев, когда в качестве ключа один из примитивных типов: Int, Long или Float
intObjectMapOf()
longObjectMapOf()
floatObjectMapOf()
/* P.S. похожие штуки на intIntMapOf(), intLongMapOf() и intObjectMapOf()
есть в android.util пакете - SparseIntArray, SparseLongArray
и SparseArray соответственно */ Полагаю вы уже догадались, что все эти реализации были созданы, также как и ранее рассмотренные списки, под копирку на основе обобщённой версии:
sealed class ScatterMap {
// меняются буквально только типы для массивов ключей и значений
var keys: Array = EMPTY_OBJECTS
var values: Array = EMPTY_OBJECTS
// остальная логика остаётся неизменной
}
sealed class IntIntMap {
// типы были изменены на примитивные
var keys: IntArray = EmptyIntArray
var values: IntArray = EmptyIntArray
// логика абсолютно не поменялась и была скопирована из ScatterMap
}
sealed class IntObjectMap {
// такая же история...
var keys: IntArray = EmptyIntArray
var values: Array = 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 рассмотрим основной метод для поиска индекса:
/* метод возвращает индекс ключа, по которому также можно получить значение,
так как массивы 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 мог быть узлом связанного списка или дерева.
Итоговые замечания:
Все остальные операции: вставка и удаление работают практически также, как и метод поиска индекса ключа с небольшой лишь разницей: происходит не только чтение массивов metadata, keys и values, но и запись нового значения либо его зануление + при превышении размера хэш-таблицы размеры массивов увеличиваются.
ScatterMap не сохраняет порядок добавления новых значений, как это делает LinkedHashMap например.
forEach, forEachIndexed также как и в предыдущих коллекциях являются inline функциями и работают без создания итераторов.
Множества
Реализация практически такая же как у хэш-таблиц, только вместо двух массивов keys и values под капотом лежит один:
sealed class ScatterSet {
// вся битовая арифметика состояний (слотов) абсолютна такая же как у ScatterMap
var metadata: LongArray = EmptyGroup
// меняется только количество массивов, так как множеству не нужны ключи
var elements: Array = EMPTY_OBJECTS
} Данная реализация также как и ScatterMap не сохраняет порядка при добавлении новых значений.
Придерживаясь канону построения структур данных для примитивных типов получаем следующие реализации:
// обобщённая реализация
scatterSetOf()
mutableScatterSetOf()
/* аналогично спискам и хэш-таблицам реализации
для примитивных типов сделаны под копирку */
intSetOf()
mutableIntSetOf()
longSetOf()
mutableLongSetOf()
floatSetOf()
mutableFloatSetOf() Другие коллекции
Кратко пробегусь по оставшимся коллекциям из androidx.collection библиотеки:
SparseArrayCompat, LongSparseArray, SimpleArrayMap, ArraySet и LruCache — переписанные версии из android.util пакета на Kotlin возможно с некоторыми оптимизациями.
CircularArray и CircularIntArray — динамические массивы с возможностью добавить значение в начало и в конец за O (1) время, реализация основана на двух индексах head и tail, которые перемещаются по массиву в противоположных направлениях: первый уменьшается, а второй увеличивается, при совпадении индексов массив удваивается.
Заключение
Надеюсь статья была полезна для вас и мне удалось насколько возможно описать механизмы работы новых структур данных из библиотеки androidx.collection, пишите своё мнение в комментариях и всем хорошего кода!
Полезные ссылки:
Мой телеграм канал
Мой Github репозиторий по алгоритмам и структурам данных
Описание и история релизов библиотеки
Inline value classes
Inline functions
Autoboxing / unboxing механизм
Kotlin Multiplatform
Динамический массив
Хэш-таблица
Алгоритм quadratic probing
Алгоритм MurmurHash
