javascript-algorithms

Хэш таблица

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

Хеш-таблица

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

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

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

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

Ссылки