HashMap

На собеседовании это вопрос может звучать так:

1) Как работает HashMap в Java?

2) Как устроен HashMap в Java?

3) Какая временная сложность операций с HashMap и почему?

HashMap позволяет хранить key-value соответствия(mappings). Временная сложность операций put(K key, V value), get(K key), containsKey(K key) константное O(1) и не зависит от числа элементов в HashMap (при хорошей функции hashCode()). 

Для сравнения, многие операции в LinkedList и ArrayList линейные O(n). Смотрите мою статью про ArrayList vs LinkedList: https://telegra.ph/ArrayList-vs-LinkedList-05-03.

Также посмотрите мои статьи про иерархию коллекций в Java:

https://telegra.ph/Ierarhiya-kollekcij-v-Java-05-08

https://telegra.ph/Ierarhiya-kollekcij-v-Java-chast-2-05-08

В худшем случае временная сложность может стать O(log(n)). Это происходит при коллизиях hashCode().

Почему так происходит?

Для этого давайте рассмотрим внутреннее устройство HashMap.

HashMap внутри содержит массив бакетов (buckets). Размер массива по умолчанию равен 16. Начальное число бакетов можно задать в конструкторе параметров initialCapacity. Число buckets всегда является степенью двойки: 2^k

Например, 16, 32, 64, 128, 256 и т.д. Если некоторая часть buckets уже заполнена элементами, то число buckets будет увеличена в два раза. Это регулируется параметров loadFactor. Его можно задать в конструкторе. По умолчанию это 0.75. Если buckets заполнены на более чем 75% (или вашим значением loadFactor) - то размер массива будет увеличен в два раза и произойдет перераспределение всех элементов HashMap в другие buckets. Произойдет перерасчет hashCode всех элементов и перераспределение элементов в другие бакеты.

Как происходит добавление элемента в HashMap?

Вначале вычисляется hashCode(Key) ключа переданного элемента (каждый объект в Java наследует метод hashCode() от класса Object). На основе вычисленного hashCode(Key) вычисляется номер бакета, в который будет помещена Key-Value пара (Entry<K, V>). Например это можно сделать взяв остаток от деления на число бакетов: index bucket = hashCode(Key) % buckets.length. Дисклеймер: в реальности индекс бакета вычисляется по-другому. Там используются битовые операции с размером массива бакетов и hashCode(Key) (hash = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16) -> i = (buckets.length - 1) & hash). Но это знать не обязательно. Можно просто сказать, что это можно например, сделать так, через остаток от деления.

Если полученный бакет пустой - просто помещаем пару key-value туда.

Что если он не пустой?

Далее будет произведена проверка ключей по equals() (Этот метод также есть у всех объектов в Java, он также наследуется от Object). Если они равны по equals() - то этот элемент будет перезаписан.

Если они не равны по equals() - значит произошла коллизия. Т.е. ключи равны по hashCode(), но отличаются по equals(). В этом случае в один и тот же бакет будут помещены оба элемента. Вначале они будут формировать список, но после некоторого количества элементов в одном и том же бакете - они будут помещены в красно-черное дерево. Операции с деревом имеют сложность O(log(n)). Поэтому в худшем случае сложность добавления, поиска и получения элемента могут быть не O(1), a O(log(n)). Это возможно, если слишком много коллизий по hashCode и все элементы просто помещаются в один и тот же бакет, в котором элементы будут храниться в дереве.

Как работает операция get(Key k)?

Также вычисляется k.hashCode(). Далее вычисляется индекс бакета, в котором может храниться элемент, например так: k.hashCode() % buckets.length. Если в данном бакете ничего нет - значит такого элемента нет в таблице. Если там есть элемент или элементы - будет использован метод equals(), чтобы найти совпадающий по equals() ключ. Эта операция работает за O(1), в худшем случает также за O(log(n)), если все элементы попали в один и тот же бакет (например, k.hashCode()  всегда возвращает одно и тоже число для всех ключей).

Еще один связанный с этой темой вопрос: какой контракт между equals() и hashCode() в Java?

Ответ: Если у объектов одинаковый hashCode(), то они могут быть не равны по equals(). Если объекты равны по equals(), то у них обязан быть одинаковый hashCode(). Это необходимо для корректной работы HashMap.