Массив (или список): Основная структура данных, в которой хранятся элементы. Иногда называют "корзинами" (buckets) или "слотами".
Хеш-функция: Функция, которая принимает ключ в качестве входных данных и возвращает индекс (целое число) в массиве. Хорошая хеш-функция обеспечивает равномерное распределение ключей по массиву, минимизируя коллизии.
Механизм обработки коллизий: Способ разрешения ситуации, когда хеш-функция генерирует одинаковый индекс для разных ключей. Два основных метода:
Метод цепочек (Separate Chaining): Каждый элемент массива хранит указатель на список (связный список, дерево Б-дерево и т.д.) элементов, которые хешировались в этот индекс.
Метод открытой адресации (Open Addressing): При коллизии ищется другое свободное место в самом массиве для размещения элемента. Различные стратегии поиска:
Линейное пробирование (Linear Probing)
Квадратичное пробирование (Quadratic Probing)
Двойное хеширование (Double Hashing)
Операции: Реализация основных операций: вставка (insert), поиск (search), удаление (delete). Эти операции используют хеш-функцию для определения местоположения элементов в массиве и механизм обработки коллизий при необходимости.