При реализации словаря («Я хочу просмотреть данные клиентов по их идентификаторам»), типичными структурами данных являются хеш-таблицы и двоичные деревья поиска. Я знаю, например, что библиотека C ++ STL реализует словари (они называют их картами), используя (сбалансированные) деревья двоичного поиска, а .NET Framework использует хеш-таблицы.
Каковы преимущества и недостатки этих структур данных? Есть ли какой-то другой вариант, который является разумным в определенных ситуациях?
Обратите внимание, что меня не особенно интересуют случаи, когда ключи имеют сильную базовую структуру, скажем, все они являются целыми числами от 1 до n или что-то еще.
algorithms
data-structures
binary-trees
hash-tables
Алекс тен Бринк
источник
источник
Ответы:
Короткий ответ заключается в том, что хеш-таблицы в большинстве случаев быстрее , но в худшем случае могут быть очень плохими. Деревья поиска имеют много преимуществ, включая ручное поведение в худшем случае , но в некоторых случаях они несколько медленнее.
Когда вы бросаете данные локальности в смесь, хеш-таблицы работают плохо. Они работают именно потому, что хранят связанные элементы далеко друг от друга, а это означает, что если приложение последовательно просматривает элементы с общим префиксом, оно не выиграет от эффектов кэширования. Это не актуально, если приложение выполняет случайные поиски.
Еще один фактор в пользу поисковых деревьев заключается в том, что они неизменны структурой данных: если вам нужно взять копию дерева и изменить несколько элементов в нем, вы можете поделиться большей частью структуры данных. Если вы берете копию хеш-таблицы, вам необходимо скопировать весь массив указателей. Кроме того, если вы работаете на чисто функциональных языках, хеш-таблицы часто не подходят.
В частности, если вам понадобится заказ ключей, например, если вы хотите иметь возможность перечислять ключи в алфавитном порядке, то хеш-таблицы не помогут (вам нужно их отсортировать), тогда как вы может напрямую пройти по дереву поиска по порядку.
Вы можете объединить двоичные деревья поиска и хеш-таблицы в виде хеш-деревьев . Хеш-дерево хранит ключи в дереве поиска в соответствии с их хеш-кодом. Это полезно, например, в чисто функциональном языке программирования, где вы хотите работать с данными, которые не имеют простого для вычисления отношения порядка.
Когда ключи являются строками (или целыми числами), trie может быть другой опцией. Дерево - это дерево, но оно индексируется не так, как дерево поиска: вы записываете ключ в двоичном виде и идете влево на 0 и вправо на 1. Таким образом, стоимость доступа пропорциональна длине ключа. Попытки могут быть сжаты для удаления промежуточных узлов; это известно как дерево патриция или основание дерева . Радикальные деревья могут превзойти сбалансированные деревья, особенно когда многие ключи имеют общий префикс.
источник