Skip to content

Latest commit

 

History

History
29 lines (18 loc) · 2.5 KB

File metadata and controls

29 lines (18 loc) · 2.5 KB

Хэш таблица

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

Hash Table

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

Существует два варианта решения коллизий - хеш-таблица с цепочками и с открытой адресацией.

Метод цепочек подразумевает хранение значений, соответствующих одному и тому же индексу в виде связного списка(цепочки).

Hash Collision

Made with okso.app

Метод открытой адресации помещает значение, для которого получен дублирующий индекс, в первую свободную ячейку.

Хеш открытая адресация

Ссылки