Ваше понимание хеш-таблиц (и кто их использует) неверно.
Проблема в том, что хеш-таблица является довольно расплывчатым термином.Под капотом есть много реализаций ... но сначала давайте поговорим об использовании BST (деревьев двоичного поиска).
Почему C ++ использует дерево двоичного поиска?
C ++ разработан комитетом, существует много возможных реализаций хеш-таблиц, приводящих к очень различным характеристикам, в то время как наиболее популярные реализации BST (Red-Black Tree и AVL Tree) имеют почти идентичные характеристики.Поэтому они не отклонили хеш-таблицы напрямую, они просто не могли определиться с характеристиками, которые нужно выбрать, и деталями, которые будут представлены пользователю.
См. Комментарий Джеймса Канзе, предложение поступило слишком поздно, и Джеймсзадает интересный вопрос о том, почему Степанов не предложил его первым.Я все еще подозреваю, что виноват ряд вариантов.
Почему базы данных используют деревья поиска?
Прежде всего, давайте остановимся на программном обеспечении базы данных.Я выберу Oracle, потому что он широко документирован и типичен для баз данных SQL.Oracle предлагает два типа индексов: растровые и поисковые деревья.
Примечание: они не используют деревья поиска BINARY, а вместо этого используют деревья B +, которые намного более удобны для ввода-вывода и кеша
Существует принципиальная разница между хэш-таблицей и деревом поиска: последняя сортируется.Многие операции с базами данных подразумевают сортировку:
- получить n-й элемент
- получить верхние n элементов
- получить элементы в [a, b]
Во всех этих случаях хэш-таблица бесполезна.
Кроме того, базы данных должны манипулировать огромными наборами данных (в общем), что означает, что им необходимо организовать свои данные для минимизации ввода-вывода (чтение / запись диска).Здесь сортированная природа дерева поиска означает, что (в индексе) элементы, к которым, вероятно, будет доступ вместе (потому что они имеют много общего), также будут сгруппированы вместе, а не разбросаны по четырем углам диска.
Наконец, внутренне Oracle может использовать хеш-таблицы в своем плане выполнения.Когда вы выполняете операцию, которая требует пересечения двух наборов строк, механизм оптимизации может решить, что хранение (временных) наборов в хэш-таблицах - это самый быстрый способ.
Теперь, что касается производительности.
Действительно, производительность деревьев поиска, как правило, хорошо известна и понятна. O (журнал N) хорош и опрятен.
С другой стороны, как я уже сказал, естьвозможно множество различных реализаций хеш-таблиц, а также стратегии для управления ростом и сжатием ... определенно более сложный.
Простой пример структуры, которую может использовать хеш-таблица:
- Открытая адресация: хеш-таблица представляет собой массив элементов, хеш-код указывает слот массива, в который следует поместить элемент, если слот заполнен, существует стратегия для определения другого слота.Та же стратегия используется для поиска.
- Buckets: хеш-таблица представляет собой массив указателей на сегменты, хеш-код указывает слот сегмента, в который помещаются элементы.Предполагается, что сегмент может расти бесконечно.
Эти две стратегии имеют чрезвычайно разные характеристики, и последние характеристики также зависят от реализаций сегментов (простая реализация заключается в использовании простого связанного списка).
Но даже если вы выберете реализацию, ее производительность зависит от распределения хеш-функций, которое зависит от самой последовательности ввода!
Мой личный совет?Чтобы выбрать между unordered_map и map в C ++, я просто спрашиваю себя, нужны ли мне отсортированные элементы или нет.Если мне нужно, чтобы они были отсортированы, я использую map, в противном случае я использую unordered_map.В большинстве случаев производительность так же хороша, так что это просто семантика .