Таблицы хэша v самобалансирующиеся деревья поиска

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

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

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

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

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

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

Ответ 1

Вот что я могу придумать:

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

Ответ 2

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

Ответ 3

Просто хотел добавить:

У сбалансированных бинарных деревьев есть предсказуемое время получения данных [log n], не зависящих от типа данных. Часто для вашего приложения может быть важно оценить время отклика для вашего приложения. [хэш-таблицы могут иметь непредсказуемое время отклика]. Помните, что для меньшего размера n, как и в большинстве распространенных случаев, разница в производительности в обращении в памяти вряд ли будет иметь значение, а шея бутылки системы будет в другом месте, и иногда вы просто хотите сделать систему намного проще отлаживать и анализировать.
Деревья, как правило, более эффективны с точки зрения памяти по сравнению с хэш-таблицами и намного проще реализовать без какого-либо анализа распределения входных ключей и возможных конфликтов и т.д.

Ответ 4

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

В реальном мире стена памяти делает их намного менее эффективными, чем на бумаге.

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

Одним словом: держите его простым. Если это просто для вас, то это просто для вашего компьютера.

Ответ 5

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