сравнить Hash с бинарным деревом поиска

Question

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

Вот как мне придумать этот вопрос? Я заметил, что Standard C ++ STL имеет set и map, которые реализованы с помощью дерева двоичного поиска, но не имеют хеш-кода (не говоря о нестандартных hash_set, hash_map). В то время как Руби имеет только Hash. Я хочу понять, что стоит за этой разницей.

Answer 1

Деревья допускают перемещение в порядке.

Наихудшая производительность для хеш-таблицы - O (N) (линейный поиск по одному сегменту), двоичный поиск ограничен O (log N).

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

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

В конце концов, STL, вероятно, просто использовал один «базовый» шаблон контейнера - дерево, чтобы избежать дополнительной сложности реализации.

Answer 2

Чтобы добавить дополнительный ответ, хеш-структуры, хотя теоретически быстрее при вставке и удалении, в значительной степени зависят от фактических данных, выбранной хеш-функции и объема данных.

• Идеальная хеш-функция зависит от количества и распределения данных.

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

Answer 3

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

Деревья, с другой стороны, относительно проще. Уже было известно, что, поскольку это структуры данных в памяти, мы можем просто использовать двоичное дерево вместо B-дерева. Тогда это был выбор между деревьями AVL и RB. Деревья RB обычно выбираются из-за лучших рабочих характеристик, которые я не могу комментировать, но статьи Википедии об обеих структурах ( AVL и RB ) расскажут вам больше в относительно хорошей детализации.

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

Answer 4

Вы можете получить доступ к данным в двоичном дереве поиска по порядку.

Answer 5

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

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

Запрос памяти влечет за собой просмотр этой структуры данных и поиск блока наименьшего (подразумевает упорядочение!), Удовлетворяющего запросу. Например, если у вас есть блоки с ключами 10, 20, 30 и приходит запрос на 20 байтов памяти, вы выбираете второй блок. Хэш-карта может сделать это легко.

Но что, если запрос на 22 байта? Поскольку ключа со значением 20 нет, вам нужно выполнить итерацию всего хеш-таблицы, чтобы найти правильный ключ (30), который является операцией O (n). Но если вы использовали дерево, то «найти наименьший ключ, больший, чем данный ключ» - это операция O (log n).

Answer 6

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

Интересно, что .NET Framework требует, чтобы каждый класс реализовывал (или наследовал) функцию GetHashCode, позволяющую хранить каждый объект в хеш-таблице. Однако это также добавляет дополнительную нагрузку на разработчиков, которые обязаны реализовывать семантически правильные хеш-функции, даже если они не предназначены для хеширования класса. Одним из решений является возвращение постоянного значения из GetHashCode, которое семантически правильно, но не очень эффективно, если функция когда-либо используется для хеширования.

Answer 7

Ну, деревья поиска упорядочены, хешей нет.

Answer 8

Во времена C ++ люди все еще были поклонниками жесткого академического подхода к структурам данных и алгоритмам, поэтому они предпочитали структуры с меньшим объемом памяти и хорошо понимаемым поведением в лучшем и худшем случаях.

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