Коллизии в хеш-таблицах и методы решения

Коллизия — это когда разные ключи попадают в одну и ту же ячейку массива. Нужно уметь с этим работать, чтобы таблица оставалась быстрой.

Популярные способы обработки коллизий

Метод цепочек — в каждой ячейке массива хранится список (цепочка) всех элементов, попавших в этот индекс;
Открытая адресация — если место занято, ищем другую свободную ячейку по какому-то правилу (линейное/квадратичное зондирование).

Сложность при хорошей хеш-функции:

O(1) в среднем для вставки и поиска;
В худшем случае — O(n), если много коллизий.

Плюсы хорошей хеш-таблицы

Очень быстрый доступ к данным по ключу;
Удобна для хранения словарей, кэшей, счётчиков;
Поддерживает большое количество операций за амортизированное O(1).

Подводные камни

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

Примеры использования хеш-таблиц

// Подсчёт количества вхождений символов
function countChars(str) {
  const freq = {};
  for (const ch of str) {
    freq[ch] = (freq[ch] ?? 0) + 1;
  }
  return freq;
}

Попробуй самостоятельно написать алгоритм, а затем сравнить

НазадИдея хеш-таблицы

Полезные темы

Рекомендуем изучить эти темы для лучшего понимания