Мне любопытно узнать, что такое рассуждение, которое может перевесить для использования техники балансировки дерева для хранения предметов, чем использование хеш-таблицы.
Я вижу, что хеш-таблицы не могут поддерживать порядок вставки, но я всегда мог использовать связанный список сверху, чтобы сохранить последовательность вставки.
Я вижу, что для небольшого числа значений добавлена стоимость хэш-функции, но я всегда мог сохранить хеш-функцию вместе с ключом для быстрого поиска.
Я понимаю, что хэш-таблицы трудно реализовать, чем прямое выполнение красно-черного дерева, но в практической реализации не было бы желания пойти лишней милей на неприятности?
Я вижу, что с хэш-таблицами это нормально для коллизий, но с методами открытой адресации, такими как двойное хеширование, которые позволяют сохранять ключи в самой хеш-таблице, не проблема была уменьшена до эффекта не опрокидывая предпочтение красным черным деревьям для таких реализаций?
Мне любопытно, если у меня явно отсутствует недостаток хеш-таблицы, которая по-прежнему делает красные черные деревья вполне жизнеспособной структурой данных в практических приложениях (например, файловых системах и т.д.).
Вот что я могу придумать:
Распределение памяти - еще одно соображение. Каждый раз, когда вы заполняете все ведра в хеш-таблице, вам нужно выделить новое хранилище и перехватить все. Этого можно избежать, если вы заранее знаете размер данных. С другой стороны, сбалансированные деревья вообще не страдают от этой проблемы.
Просто хотел добавить:
У сбалансированных бинарных деревьев есть предсказуемое время получения данных [log n], не зависящих от типа данных. Часто для вашего приложения может быть важно оценить время отклика для вашего приложения. [хэш-таблицы могут иметь непредсказуемое время отклика]. Помните, что для меньшего размера n, как и в большинстве распространенных случаев, разница в производительности в обращении в памяти вряд ли будет иметь значение, а шея бутылки системы будет в другом месте, и иногда вы просто хотите сделать систему намного проще отлаживать и анализировать.
Деревья, как правило, более эффективны с точки зрения памяти по сравнению с хэш-таблицами и намного проще реализовать без какого-либо анализа распределения входных ключей и возможных конфликтов и т.д.
По моему скромному мнению, самобалансирующиеся деревья работают очень хорошо, как академические темы. И я не знают ничего, что можно квалифицировать как "прямолинейную реализацию красно-черное дерево ".
В реальном мире стена памяти делает их намного менее эффективными, чем на бумаге.
С учетом этого хэш-таблицы являются достойными альтернативами, особенно если вы не практикуете их академический стиль (забудьте о ограничении размера таблицы, и вы волшебно решаете проблема изменения размера таблицы и почти все проблемы с конфликтами).
Одним словом: держите его простым. Если это просто для вас, то это просто для вашего компьютера.
Я думаю, что если вы хотите запросить диапазон ключей вместо одного ключа, самобалансированная древовидная структура будет работать лучше, чем структура хеш-таблицы.