Хеш-таблица - структура данных, реализующая абстрактный тип данных ассоциативный массив, т.е. структура, которая связывает ключи со значениями. Хеш-таблица использует хеш-функцию для вычисления индекса в массиве, в котором может быть найдено желаемое значение. Ниже представлена хеш-таблица, в которой ключём выступает имя человека, а значениями являются телефонные номера. Хеш-функция преобразует ключ-имя в индекс массива с телефонными номерами.
В идеале хеш-функция будет присваивать элементу массива уникальный ключ. Однако большинство реальных хеш-таблиц используют несовершенные хеш-функции. Это может привести к ситуациям, когда хеш-функция генерирует одинаковый индекс для нескольких ключей. Данные ситуации называются коллизиями и должны быть как-то разрешены.
Существует два варианта решения коллизий - хеш-таблица с цепочками и с открытой адресацией.
Метод цепочек подразумевает хранение значений, соответствующих одному и тому же индексу в виде связного списка(цепочки).
Метод открытой адресации помещает значение, для которого получен дублирующий индекс, в первую свободную ячейку.
