Основы хеш-таблиц

От ключа к корзине

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

static int bucketIndex(int key, int capacity) {
    int hash = Integer.hashCode(key);
    return Math.floorMod(hash, capacity);
}

Если ёмкость таблицы равна capacity, индекс должен лежать в диапазоне от 0 до capacity - 1. Хеш сам по себе не является индексом: он может быть отрицательным и обычно имеет гораздо больший диапазон значений.

Что хранится внутри

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

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

Почему говорят «в среднем O(1)»

При удачном распределении ключей хеш сразу приводит к корзине с небольшим количеством записей. Тогда поиск, добавление и удаление требуют примерно постоянного числа действий и имеют ожидаемую сложность O(1).

Это не абсолютная гарантия. Разные ключи могут попадать в одну корзину, а неудачное распределение увеличивает объём работы. В худшем случае операция может деградировать до O(n). Почему возникают такие совпадения и как с ними работают, разберём на странице о коллизиях.