Хеш-таблицы против бинарных деревьев

30

При реализации словаря («Я хочу просмотреть данные клиентов по их идентификаторам»), типичными структурами данных являются хеш-таблицы и двоичные деревья поиска. Я знаю, например, что библиотека C ++ STL реализует словари (они называют их картами), используя (сбалансированные) деревья двоичного поиска, а .NET Framework использует хеш-таблицы.

Каковы преимущества и недостатки этих структур данных? Есть ли какой-то другой вариант, который является разумным в определенных ситуациях?

Обратите внимание, что меня не особенно интересуют случаи, когда ключи имеют сильную базовую структуру, скажем, все они являются целыми числами от 1 до n или что-то еще.

Алекс тен Бринк
источник
1
Я буду раздражать вас, но вы не можете просто сказать «целые числа от 1 до n», так как в этом случае массив превзойдет все остальные структуры данных :-). «Струны» кажутся справедливыми и охватывают большинство ситуаций.
Джмад
@jmad он сказал, что не заинтересован в этом деле.
Джо
@ Джо Я думал, это было ясно, я принял это во внимание. В любом случае, это не повод приводить наихудший возможный пример ключа.
Джмад
1
На самом деле .NET имеет как словари, реализованные с использованием деревьев, так и словари, реализованные с использованием хеш-таблиц (как и C ++, начиная со стандарта 2011 года).
sepp2k
То же самое можно сделать и на SO: stackoverflow.com/questions/371136/…
Сиро Сантилли 事件 改造 中心 法轮功 六四 事件

Ответы:

26

n - количество ключей в словаре.

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

O(lg(n))log2(n)

2nO(1) времени с довольно маленькой константой (один расчет хеша плюс один поиск указателя). Это делает хеш-таблицы очень быстрыми во многих типичных случаях.

O(1)

  • O(n) . Это может привести к «резкому» поведению, когда добавлено много элементов.
  • O(1)

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

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

k1k2h(k1)=h(k2)

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

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

Когда ключи являются строками (или целыми числами), trie может быть другой опцией. Дерево - это дерево, но оно индексируется не так, как дерево поиска: вы записываете ключ в двоичном виде и идете влево на 0 и вправо на 1. Таким образом, стоимость доступа пропорциональна длине ключа. Попытки могут быть сжаты для удаления промежуточных узлов; это известно как дерево патриция или основание дерева . Радикальные деревья могут превзойти сбалансированные деревья, особенно когда многие ключи имеют общий префикс.

Жиль "ТАК - перестань быть злым"
источник
2
У BST также нет плохой локализации данных?
svick
@svick Они могут или не могут, в зависимости от того, как распределены узлы. Увеличение арности дерева может помочь без ущерба для времени выполнения (стоимость больше и сложнее кода).
Жиль "ТАК - перестань быть злым"
2
На BST легко получить элементы «по порядку», для хеш-таблицы об этом не может быть и речи.
vonbrand
Кроме как по соображениям безопасности, почему имеет значение, если хеш-таблицы имеют плохое время наихудшего случая, если их средний регистр лучше, чем у двоичных деревьев? Я полагаю, что удобство утилиты / пользователя имеет примерно линейную зависимость от того, сколько времени требуется дереву, чтобы закончить, поэтому ожидаемое (среднее) значение должно быть всем, что имеет значение.
Кельмикра
@ Kyth'Py1k Что вы подразумеваете под «деревом, чтобы закончить»? Смысл хеш-таблиц в том, чтобы обращаться к одному значению за раз, а не ко всему дереву, иначе список или массив будут работать лучше. Даже в ситуациях, когда среднее значение имеет значение (что не всегда так, например, когда у вас есть ограничения в реальном времени), это среднее значение по запросам, сделанным в данной ситуации, которые часто не одинаковы по всей таблице. - например, смещение к определенному префиксу.
Жиль "ТАК - перестань быть злым"