🤔 Как работает хеш таблица?

Это структура данных, которая позволяет эффективно хранить и извлекать пары "ключ-значение". Она использует хеш-функцию для преобразования ключа в индекс массива, где хранится соответствующее значение.

🚩Основные концепции

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

🟠Коллизии
Это ситуации, когда два разных ключа хешируются в один и тот же индекс. Существуют различные методы разрешения коллизий:
Метод цепочек (chaining): В каждой ячейке массива хранится список (или другая структура данных), содержащий все значения, соответствующие этому индексу.
Открытая адресация (open addressing): При коллизии ищется другая свободная ячейка по определённому алгоритму (например, линейное пробирование, квадратичное пробирование или двойное хеширование).

🟠Размер хеш-таблицы
Количество ячеек (бакетов) в массиве. Оптимальный размер зависит от количества ключей и используемой хеш-функции. Обычно размер выбирается простым числом для уменьшения вероятности коллизий.

🚩Как работает хеш-таблица

🟠Вставка элемента
Хеш-функция вычисляет индекс для ключа.
Если ячейка пуста, значение записывается в неё.
Если ячейка занята (коллизия), применяется выбранный метод разрешения коллизий.

🟠Поиск элемента
Хеш-функция вычисляет индекс для ключа.
Проверяется ячейка по этому индексу.
Если ключи совпадают, возвращается значение.
Если ключи не совпадают (коллизия), применяется метод разрешения коллизий до нахождения нужного ключа или пустой ячейки (что означает отсутствие ключа).

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

Ставь 👍 и забирай 📚 Базу знаний