Чтобы объявить переменную типа Map, необходимо передать два дженерик-типа, первый из которых соответствует типу ключа, а второй – типу значения.
Для примера представим ситуацию, что есть класс с фамилиями учеников, которые уникальны, т.е. в классе нет учеников с одинаковой фамилией, и необходимо получить оценку ученика по его фамилии. В таком случае, мы бы могли хранить Map в такой переменной:
val map: Map<String, Int>
Map в Kotlin – это неизменяемый тип данных. Мы можем найти значение с помощью ключа, используя интерфейс Map, но не можем добавить новую пару ключа и значения или удалить существующие. Для изменяемого Map есть отдельный интерфейс – MutableMap.Догнать и перегнать: Российские ВКС прирастают новыми функциями 
Допустим, у нас есть некий ученик Петров. Если мы хотим получить его оценку, мы можем сделать это следующим образом:
map["Петров"]
Добавить оценку 5 для Иванова в map типа MutableMap мы можем следующим образом:
map["Иванов"] = 5
Или так:
map += "Иванов" to 5
Удалить элемент можно следущим способом:
map.remove("Иванов")
Или так:
map -= "Иванов"
У Map есть несколько реализаций, от которых зависит сложность выполнения основных операций: поиск, добавление/удаление элемента, а также порядок элементов при итерации.
HashMap – это реализация Map на основе хэш-таблицы. В основе хэш-таблицы лежит массив, определенного размера (по умолчанию 16, но можно изменить с помощью параметра конструктора initialCapacity).
При поиске значения по ключу в HashMap, сначала вычисляется хэш-код (метод hashCode, объявленный в классе Any). Этот метод возвращает значение типа Int. Цель хэш-функции вернуть разный хэш-код для разных ключей. Но полностью реализовать эту цель невозможно, т.к. в типе Int можно уместить только 232 вариантов. А ключей может быть сколько угодно. Следовательно, возникает проблема коллизий, когда для разных ключей хэш-функция вычисляет одинаковый хэш-код. При этом создавать для каждого HashMap массив из 232 элементов тоже было бы неэффективно, ведь при создании массива требуется выделение памяти. Поэтому хэш-код делится с остатком на текущий размер массива в HashMap. И остаток от этого деления будет соответствовать индексу массива, где должен находиться элемент.
Что же тогда делать, если у двух разных объектов эти индексы совпали? Решается эта проблема тем, что элементом массива будет являться корень двусвязного списка или красно-черного дерева, в случае если количество элементов в списке дошло до определенного порога, что позволяет сократить время поиска элемента в худшем случае от O(n) до O(log n). Следовательно, при поиске элемента в HashMap, после вычисления индекса массива происходит поиск пары ключ-значение в двусвязном списке или красно-черном дереве.
В двусвязном списке проверяется равенство хэш-кодов, и если они равны дополнительно применяется функция equals для самих ключей, чтобы исключить коллизии.
Красно-черное дерево – это самобалансирующееся бинарное дерево поиска, и оно использует сравнение. Сначала сравниваются хэш-коды. Когда хэш-коды совпали, а equals вернул false, и ключ реализует интерфейс Comparable, продолжается бинарный поиск с помощью compareTo. Если же ключ не реализовывает Comparable, то происходит обход с помощью equals.
Когда количество элементов в HashMap достигает определенного процента от размера массива (по умолчанию 75%), то создается новый массив, размер которого в два раза больше старого, а элементы перераспределяются в новый массив. Этот процент можно изменить с помощью параметра конструктора loadFactor.
В среднем операции поиска/добавления/удаления элемента в HashMap выполняются за константное время O(1).
Для использования класса в качестве ключа в HashMap необходима правильная работа методов hashCode и equals. Эти методы для одних и тех же объектов всегда должны возвращать один и тот же результат, иначе вы можете не найти данные, которые вы положили в HashMap. Если hashCode будет возвращать константное число, то HashMap станет неэффективным и его средняя сложность будет эквивалентна сложности в худшем случае.
По умолчанию метод hashCode из класса Any вычисляет одинаковый хэш-код только для одного и того же объекта в памяти. То же самое происходит с equals, по умолчанию он вернет true, только если обе ссылки указывают на один и тот же объект в памяти.
class Pupil(val name: String)
fun main() {
val pupil1 = Pupil("Иванов")
val pupil2 = Pupil("Иванов")
val map = HashMap<Pupil, Int>()
map[pupil1] = 5
map[pupil2] = 5
println(map)
}
Вывод этого кода будет следующим:
{Pupil@506e6d5e=5, Pupil@96532d6=5}
Мы видим, что в HashMap были добавлены два разных объекта для ученика с одной и той же фамилией. Но мы условились выше, что для примера мы будем считать, что у нас не может быть двух учеников с одинаковой фамилией. Поэтому pupil1 и pupil2 – это по сути один и тот же ученик Иванов. И нам хотелось бы, чтобы в HashMap добавлялась только 1 пара ключ-значение. Для этого нам придется переопределить hashCode и equals, чтобы они возвращали одинаковый хэш-код и true, когда содержимое двух объектов совпадает. В Kotlin достаточно объявить класс Pupil как data class. Перепишем пример:
data class Pupil(val name: String)
fun main() {
val pupil1 = Pupil("Иванов")
val pupil2 = Pupil("Иванов")
val map = HashMap<Pupil, Int>()
map[pupil1] = 5
map[pupil2] = 5
println(map)
}
Вывод:
{Pupil(name=Иванов)=5}
Порядок элементов при итерации в HashMap непредсказуем и нет гарантии, что он будет совпадать с порядком добавления элементов. Если вам необходимо сохранить порядок, используйте LinkedHashMap. Для этой цели в нем хранится дополнительный список.
HashMap не является потокобезопасным. Выполнение операций над ним из разных потоков может привести к непредсказуемым результатам. Вы можете обернуть HashMap с помощью метода Collections.synchronizedMap. Тогда операции, проведенные над полученными объектами, будут синхронизированы, что даст вам гарантию потокобезопасности. Но это может оказаться недостаточно эффективным. Ведь в таком случае если даже два разных потока всего лишь попытаются прочитать значение из Map, одному из них придется ждать, пока второй не завершит операцию. Поэтому более эффективная синхронизация реализована в ConcurrentHashMap. Он позволяет параллельно считывать из разных потоков и даже записывать, за исключением, когда запись происходит в один и тот же сегмент хэш-таблицы.
TreeMap – это реализация Map на основе красно-черного дерева. Ключи в нем хранятся в отсортированном виде. После добавления элементов, сортировка сохраняется. Операции добавления/удаления/поиска в таком Map имеют сложность O(log n). Но для использования класса в качестве ключа в TreeMap, он должен реализовать интерфейс Comparable, либо вы должны передать Comporator в конструктор TreeMap. Иначе будет выброшено исключение. При итерации элементы TreeMap будут идти в отсортированном порядке.
Автор: Магомед-Хусейн Закриев, Android-разработчик
