HashMap

Ассоциативный массив для хранения пар «ключ-значение». Работает на основе хэширования, быстро добавляет, удаляет и ищет данные. Не синхронизирован, поэтому не потокобезопасен.

• Использует хэш-таблицу для хранения данных. В случае коллизий элементы группируются в связные списки или деревья (с Java 8).

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

• Ключи могут быть null (только один null) и любыми объектами. Примитивы используются через классы-обертки (Integer, Double).

• Не реализует интерфейс Collection, но является частью Map.

• Не потокобезопасен. Одновременный доступ из нескольких потоков может привести к исключению ConcurrentModificationException. Используй ConcurrentHashMap или синхронизацию.

HashMap<String, Integer> map = new 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) // вернуться к прежнему размеру.

Внутренний класс 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 обычно имеют среднюю временную сложность O(1). Однако, в случае множества коллизий, сложность может возрасти до O(n), где n — количество элементов в корзине.

Потокобезопасная версия HashMap. синхронизирует доступ к методам мапы, позволяя безопасно работать с ней в многопоточной среде.

Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());

Класс в Java, который наследует HashMap, но дополнительно сохраняет порядок вставки или порядок доступа к элементам. Это делает его удобным для задач, где важно сохранять последовательность элементов.

LinkedHashMap<String, Integer> map = new LinkedHashMap<>(/*initialCapacity*/ 16, /*loadFactor*/ 0.75F, /*accessOrder*/ false);

Потокобезопасная реализация интерфейса Map, которая используется для управления коллекциями ключ-значение в многопоточных средах. В отличие от обычного HashMap, который не является потокобезопасным, ConcurrentHashMap обеспечивает синхронизацию и управление доступом к данным, что позволяет нескольким потокам одновременно безопасно читать и изменять содержимое мапы.

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

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

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

val map = ConcurrentHashMap<String, Int>()

map.putIfAbsent("three", 3)

map.computeIfPresent("three") { _, value -> value + 1 }

val map = ConcurrentHashMap<String, Int>()
map["count"] = 5

val previousValue = map.replace("count", 10)

val map = ConcurrentHashMap<String, Int>()
map["value"] = 20
 
val isReplaced = map.replace("value", 20, 30)

• Key (5)

  1. Какие условия у ключа в HashMap?

     Ключи в HashMap должны правильно переопределять методы equals и hashCode для корректной работы.

  2. Если ключ null - где хранится значение? В какой бакет попадает?

     Первый бакет. Позиция с индексом 0.

  3. Что происходит при добавлении элемента с существующим ключом в HashMap?

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

  4. Хотим использовать Java-класс как ключ в HashMap, что нужно переопределить у класса?

     Методы equals() и hashCode().

  5. data-class может быть ключом?

     Да. При объявлении data-класса автоматически генерируются методы equals() и hashCode(), которые необходимы для корректной работы с ключами в HashMap.

• Bucket (3)

  1. Как определяется Bucket?

     По hashCode, через операцию взятия остатка от деления (модуль).

  2. Как объекты хранятся внутри бакета?

     Внутри бакета объекты хранятся в виде цепочки (связанного списка) или сбалансированного дерева (если количество объектов в бакете превышает порог). Каждый элемент в бакете представлен в виде пары ключ-значение, где ключ используется для поиска соответствующего значения.

  3. Для чего нужен связный список в бакете?

     Связный список используется для обработки коллизий. Когда несколько элементов имеют одинаковый хэш-код и попадают в один и тот же бакет, они сохраняются в виде связного списка, что позволяет эффективно хранить и извлекать элементы, обеспечивая при этом доступ к ним за O(n) в случае коллизий, где n — количество элементов в этом бакете.

• ConcurrentHashMap (2)

  1. Для чего используется ConcurrentHashMap?

     ConcurrentHashMap используется для потокобезопасного хранения и управления коллекцией ключ-значение в многопоточной среде, позволяя нескольким потокам одновременно читать и изменять данные без полной блокировки всей мапы. Он обеспечивает высокую производительность благодаря частичной блокировке и атомарным операциям.

  2. Как ConcurrentHashMap устроена под капотом?

     ConcurrentHashMap разбивает данные на сегменты, что позволяет нескольким потокам одновременно модифицировать разные части мапы, минимизируя блокировки и повышая производительность. Она использует CAS (Compare-And-Swap) и частичные блокировки для атомарного выполнения операций и управления конкурентным доступом.

• Другие (13)

  1. Как устроен HashMap?

     HashMap хранит данные в виде пар ключ-значение, используя хэширование для быстрого поиска. Ключи хэшируются для определения бакета, в котором хранится пара, а при коллизии ключей используется связанный список или дерево (в зависимости от количества элементов в бакете). Это обеспечивает быстрый доступ к элементам, обычно с временной сложностью O(1), но может ухудшиться до O(n) при частых коллизиях.

  2. Какой контракт между equals и hashCode в HashMap?

     • Равные объекты имели одинаковый hashCode: если два объекта a и b равны (a.equals(b) == true), то их хэш-коды должны быть одинаковыми (a.hashCode() == b.hashCode()). Это позволяет HashMap находить правильную ячейку для хранения и поиска объекта.

     • Неравные объекты могут иметь разные или одинаковые hashCode: если a.equals(b) == false, их hashCode может быть разным или одинаковым. Одинаковый хэш-код для неравных объектов возможен, но это приведёт к так называемым коллизиям в HashMap. В случае коллизий HashMap будет использовать метод equals для точного сравнения объектов в одном бакете.

  3. Если у 2 объектов одинаковые хэш-коды значит ли это что их equals = true?

     Нет, два объекта могут иметь одинаковый hashCode, но при этом быть неравными с точки зрения equals. Это называется коллизией хэш-кодов.

  4. Почему время доступа к HashMap падает при большом количестве коллизий, но не становится O(n)?

     При значительном увеличении числа коллизий, HashMap преобразует списки в бакетах в сбалансированные деревья. Это улучшает время доступа до O(log n) в случае коллизий, что предотвращает ухудшение производительности до O(n).

  5. Для чего нужен loadFactor в HashMap?

     Используется для определения, когда нужно увеличить размер массива бакетов, чтобы сохранить эффективность поиска и уменьшить количество коллизий. Он представляет собой отношение количества элементов в HashMap к числу бакетов, при превышении которого происходит увеличение ёмкости HashMap.

  6. Для чего нужен initial capacity в HashMap?

     Определяет начальный размер массива для хранения элементов и уменьшает количество перераспределений.

  7. Что такое коллизия в HashMap?

     Если в HashMap добавить два элемента с одинаковым хэш-кодом, они попадут в один и тот же бакет. Однако, если ключи при этом разные (неравны по методу equals), оба элемента будут храниться в этом бакете в виде цепочки. Если ключи одинаковы, второй элемент заменит первый.

  8. Может ли элемент в HashMap потеряться?

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

  9. Как специально потерять объект в HashMap?

     Изменить его hashCode.

  10. Что произойдет при добавлении в HashMap 2 разных объектов c одинаковым хэш-кодом?

      Если объекты равны по equals - они будут размещены в одном бакете, иначе один объект перезапишет второй. HashMap разрешит коллизию, добавив второй объект в список (или дерево, если элементов много) в этом бакете, и при поиске будет использовать equals для точного соответствия.

  11. Какой пошаговый алгоритм добавления объекта в HashMap?

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

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

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

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

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

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

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

  12. Какой пошаговый алгоритм получения объекта из HashMap?

      • Вычисление хэш-кода: Вызывается hashCode() для ключа.

      • Определение индекса: Хэш-код преобразуется в индекс массива бакетов.

      • Поиск в бакете: Если бакет пустой, возвращается null. Если нет, перебираются элементы.

      • Сравнение ключей: Сравниваются хэш-коды и ключи с помощью equals().

      • Возврат значения: Возвращается соответствующее значение или null, если ключ не найден.

  13. Какова скорость базовых операций у HashMap?

      O(1). При коллизиях O(n).