Просто о HashMap

Хешкод - целочисленное представление объекта (преобразование проводится на основе хешфункции. В Java это метод hashcode(), возвращает int).

Коллизия хешкодов - ситуация, когда хешфункция для разных объектов возвращается одинаковый хеш.

Поскольку тип данных int ограничен, функция не сможет выдавать вечно разные хешкоды, рано или поздно даже хорошая хешфункция будет "причиной" коллизии, но это, практически, сводится к минимуму.

Эта структура данных представляет из себя массив нод:

Node<K,V>[] table;

В свою очередь, Node состоит из:

final int hash;    // хеш
final K key;       // ключ
V value;           // значение
Node<K,V> next;    // ссылка на следующий элемент связного списка

Получается, что каждая ячейка массива хранит связный список, так как каждая нода имеет ссылку на след. элемент (если он есть).

(Ячейку хешмапы еще называют бакитом(bucket))

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

hashMap.put("Олег", "Сантехник");

1. Вычисляется хешкод для ключа
   "Олег".hashcode() = 32474939
2. На основе хешкода вычисляется позиция в массиве, куда должен быть добавлен элемент
   32474939 % 16 = 11
   (Индекс = остатку от деления хешкода на текущий размер массива)
   
3. Добавление

Добавим еще парочку элементов:

hashMap.put("Лиза", "Преподаватель");

hashMap.put("Сергей", "Программист");

хеш ключа: 1224353803
индекс: 1224353803 % 16 = 11

Поскольку под 11 индексом уже есть элемент, сравниваются хешкоды - они разные, значит по дефолту эти ключи не одинаковые. Новая нода добавляется в конец связного списка.

Коллизия хешкодов

hashMap.put("Слава", "Музыкант");

(У класса String метод hashcode переопределен хорошо, по этому коллизии хешкодов маловероятны, тогда, сделаем вид что хешкод строки "Слава" такой же как и у "Олег")

хеш ключа: 32474939
индекс: 32474939% 16 = 11

Произошла коллизия - хешкоды "Слава" и "Олег" совпали.

Естественно, данный элемент будет помещен по 11 индексу, но, сначала идет проверка с другими элементами связного списка.

1. Хешкоды "Слава" и "Олег" равны, если они равны, ключи проверяются на равенство методом equals(), false.
2. Следующий элемент - хешкоды равны? Нет, по этому и с помощью equals() проверять нет смысла, кладем ноду в конец списка.

Добавление элемента с ключем, который уже присутствует в мапе

hashMap.put("Лиза", "Блогер");

// вычисляем хешкод и позицию. index = 6

Сравниваем хешкоды - равны. Сравниваем методом equals() - "Лиза".equals("Лиза") вернет true. Тогда нода перезаписывается.

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

hashMap.get("Сергей"); // Вернет значение "Программист"

Получаем значение мы с помощью ключа.

Те же манипуляции, вычисляем хешкод = 1224353803, индекс = 11.

Находим связной список, и сравниваем сначала хешкоды, если они не равны - переходим к след. элементу, если хешкоды равны, сравниваем с пом. equals(), true. Мы нашли искомый элемент.

Важные детали

Load factor - это коэффициент, который показывает когда увеличивать емкость HashMap, чтобы поддерживать сложность операций get() и put() на уровне O (1). Коэффициент загрузки HashMap по умолчанию составляет 0,75f (75% от размера карты).

То есть, если у нас размер массива равен 16, коэффициент равен 0.75, тогда когда размер будет равен 12, массив увеличится вдвое (size * load factor).

"чтобы поддерживать сложность операций get() и put() на уровне O (1)"

Доступ к элементу осуществляется за O(1), поскольку вычисляется хешкод, индекс, и нужный элемент у нас.

Но если хешфункция реализована плохо, будут возникать частые коллизии, собственно, вместо равномерного распредления нод по всему массиву, будут создаватся длинные связные списки, поиск элементов которых занимает O(n).

Получается, что если в списке 250 элементом, и наш элемент 150, нам нужно пройтись по каждому элементу чтобы дойти до нужного нам O(150). Отсюда и O(n).

По этому очень важно иметь хорошо реализованную хешфункцию, чтобы не возникало коллизий и элементы равномерно распределялись по всему массиву и доступ производился за константное время.