HashMap

HashMap

Ассоциативный массив. Его элементами являются структуры LinkedList. Данные структуры LinkedList заполняются элементами которые мы добавляем в HashMap.

• работает по принципам хэширования (преобразование любого объекта в Int с помощью метода hashCode)

• не является коллекцией т.к. не реализует интерфейс Collection.

• не является потокобезопасным. юзать ConcurrentHashMap.

• добавление/получение/удаление выполняется за константное время O(1). за единичку.

• key может быть любого типа даже null (если не установлено NotNull). Для примитивов используются классы-обертки (пример: Integer).

• не синхронизирован. HashMap одновременно доступен только одному потоку. если попытаться получить доступ из другого потока выбросится ConcurrentModificationException. лечится блоком synchronized или использованием ConcurrentHashMap.

Создание HashMap

Создается массив элементов (backet, корзина). Каждый элемент содержит LinkedList.

• initialCapacity - начальное количество сегментов в таблице (по умолчанию 16). является степенью 2. максимальный размер: Int / 2.

• loadFactor - коэффициент загрузки таблицы. используется для увеличения емкости.

• когда table[] заполняется до предельного значения - его размер увеличивается вдвое и просиходит перераспределение элементов.

val map = HashMap<String, String>(
    initialCapacity = 16,
    loadFactor = 0.75F
)

Добавление элемента

• в первую очередь key проверяется на null. Если key = null то элемент помешается в 0 корзину. Его хеш = 0.

• для key вычисляется хешкод.

• для хешкода вычисляется индекс корзины куда будет помещен элемент (0 - 15 для размера таблицы 16). если хешкоды равны то и индексы равны.

• создается объект Node. он добавляется в корзину и становится первым элементом.

• если при добавлении совпали индексы то элемент добавляется в корзину в конец LinkedList а существующий элемент начинает на него ссылаться.

• если при добавлении совпали хешкоды то случается коллизия. новый элемент сравнивается поочередно со всеми элементами в корзине. если хешкоды одинаковые - элементы проверяются на равенство с помощью метода equals. Если false - элемент добавляется в конец LinkedList.

• если при добавлении элемента совпали хешкоды и метод equals то элемент перезапишется в корзине.

data class Student(
    val name: String
)

val map = HashMap<Student, String>()
map.put(Student("John"), "5.0")

Получение элемента

• сначала вычисляется хешкод для объекта key.

• находится индекс корзины для хешкода ключа.

• все элементы в LinkedList поочередно сравниваются по хешкоду с текущим. если хешкоды совпали - элементы сравниваются методом equals. Если true - элемент найден.

• порядок элементов не гарантируется.

• если у элемента который используется в качестве key в HashMap изменится поле, которое участвует в определении hashCode, то при обращении по key объект будет потерян.

• если переопределить equals без hashCode или оба метода неправильно и эти объекты использовать в качестве key в HashMap (используя один объект как ключ, положить значение, используя другой – искать его), то значение найдено не будет.

val map = HashMap<Student, String>()
val value: String? = map.get(Student("John"))

Удаление элемента

• при удалении элементов размер table[] остается прежним. размер HashMap уменьшается но не до предыдущего.

val map = HashMap<Student, String>()
map.remove(Student("John"))

val newMap = HashMap<Student, String>(map) // вернуться к прежнему размеру.

Node

Внутренний класс HashMap. Его также называют Entry (имплементирует интерфейс Map.Entry).

• hash - хеш ключа.

• key - ключ.

• value - значение.

• next - ссылка на следующий элемент в LinkedList. Если нет - равен null.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Преимущества HashMap

• быстрая реализация. вместо перебора всех элементов HashMap точно значет где искать.

Сложность операций

Вставка, удаление и поиск элементов в HashMap обычно имеют среднюю временную сложность O(1). Однако, в случае множества коллизий, сложность может возрасти до O(n), где n — количество элементов в корзине.

synchronized HashMap

Синхронизация на уровне объекта (дает доступ только 1 потоку и блокирует для остальных).

val map = Collections.synchronizedMap(HashMap<String, String>())

LinkedHashMap

Является наследником HashMap. Хранит информацию о порядке добавления элементов или порядке их использования.

• accessOrder - если true элементы будут выводиться в порядке последнего использования (get put) иначе в порядке добавления

• производительность методов немного ниже чем у HashMap.

• элементы содержат ссылки ана предыдущий и следующий добавленный элементы.

val map = LinkedHashMap<String, String>(
    initialCapacity = 16,
    loadFactor = 0.75F,
    accessOrder = false
)

ConcurrentHashMap

Несколько потоков могут одновременно изменять информацию в разных сегментах table[].

• в ConcurrentHashMap любое количество потоков может читать элементы не блокируя его.

• благодаря сегментированию при изменении элемента блокируется только сегмент в котором он находится.

• key и value не могут быть null.

• под капотом все поля объявлены как volatile.

val map = ConcurrentHashMap<Student, String>()