Почему операции get и put в HashMap имеют константную сложность O(1) при отсутствии коллизий?

Константное время O(1) для get() и put() в HashMap обеспечивается за счет прямого доступа к элементу по индексу в массиве, который вычисляется за фиксированное время.

Механизм работы:

1. Хеш-функция: Ключ преобразуется в целочисленный хеш-код с помощью метода hashCode().
2. Определение индекса: На основе этого хеш-кода вычисляется индекс ячейки (бакета) во внутреннем массиве Node<K,V>[] table. Вычисление индекса — это быстрая битовая операция, например, (n - 1) & hash, где n — размер массива.
3. Прямой доступ: При отсутствии коллизий в этой ячейке находится ровно одна пара ключ-значение. Операция сводится к доступу по индексу в массиве (O(1)) и одному сравнению ключей.

Упрощенная иллюстрация:

HashMap<String, Integer> map = new HashMap<>();
// Внутренний массив (упрощенно): table = new Node[16];

map.put("apple", 10);
// 1. hash = "apple".hashCode() // Допустим, 123456
// 2. index = (16 - 1) & 123456 // Допустим, вычисляется 5
// 3. table[5] = new Node<>("apple", 10); // Прямая запись по индексу 5

Integer value = map.get("apple");
// 1. hash = "apple".hashCode() // Снова 123456
// 2. index = (16 - 1) & 123456 // Снова 5
// 3. return table[5].value; // Прямое чтение по индексу 5

Важные условия для O(1):

• Хорошая хеш-функция должна равномерно распределять ключи по бакетам.
• Отсутствие коллизий – когда разные ключи дают разный индекс. При коллизиях элементы хранятся в виде цепочек (списков) или деревьев внутри бакета, и сложность может деградировать до O(n) или O(log n).
• Низкий коэффициент загрузки (load factor) – по умолчанию 0.75. При его превышении массив увеличивается (rehashing), что является операцией O(n), но амортизированно сохраняет среднюю производительность O(1).