Сопоставление хэш-таблицы и map в С++

Сопоставьте хэш-таблицу и mар из стандартной библиотеки шаблонов (STL). Как организована хэш-таблица? Какая структура данных будет оптимальной для небольших объемов данных?

В хэш-таблицу значение попадает при вызове хэш-функции с ключом. Сами значения хранятся в неотсортированном порядке. Так как хэш-таблица использует ключ для индексации элементов, вставка или поиск данных занимает O(1) времени (с учетом минимального количества коллизий в хэш-таблицах). В хэш-таблице также нужно обрабатывать потенциальные коллизии. Для этого используется цепочка — связный список всех значений, ключи которых отображаются в конкретный индекс.

map(STL) вставляет пары ключ/значение в дерево двоичного поиска, основанное на ключах. При этом не требуется обрабатывать коллизии, а так как дерево сбалансировано, время вставки и поиска составляет O(log N).

Как реализована хэш-таблица?

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

Нельзя сказать, что элементы связного списка с определенным индексом массива имеют один и тот же ключ. Скорее, функция hashFunction(key) для этих значений совпадает. Поэтому, чтобы получить значение, соответствующее ключу, мы должны хранить в каждом узле и ключ и значение.

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

1. Нужно использовать хорошую хеш-функцию, чтобы гарантировать, что ключи были правильно распределены. Если ключи будут плохо распределены, то возникнет множество коллизий и скорость нахождения элемента снизится.
2. Независимо от того, насколько хороша наша хеш-функция, коллизии будут возникать, и мы будем нуждаться в их обработке. Это подразумевает использование цепочек связных списков (или другой метод решения проблемы).
3. Можно реализовать методы динамического увеличения или уменьшения размера хэш-таблицы. Например, когда отношение количества элементов к размеру таблицы превышает определенное значение, следует увеличить размер хэш-таблицы. Это означает, что нам потребуется создать новую хэш-таблицу и передать в нее записи из старой. Поскольку это очень трудоемкий процесс, нужно сделать все возможное, чтобы размер таблицы не менялся слишком часто.

Что может заменить хэш-таблицу при работе с небольшими объемами данных?

Можно использовать mар (из STL) или бинарное дерево. Хотя это потребует O(log(n)) времени, объем данных не велик, поэтому временные затраты будут незначительными.

В чём преимущество map?

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

Разбор основан на переводе книги Г. Лакман Макдауэлл и предназначен исключительно для ознакомления.Если он вам понравился, то рекомендуем купить книгу «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию».