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

Question

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

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

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

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

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

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

Несколько причин, по которым я могу придумать:

1. Деревья являются динамическими (сложность пространства равна N), тогда как хеш-таблицы часто реализуются как массивы фиксированного размера, что означает, что они часто будут инициализироваться с размером K, где K> N, так что даже если вы в хэш-карте есть только 1 элемент, у вас может быть 100 пустых слотов, занимающих память. Еще один эффект этого:

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

3. Элементы в дереве можно собирать в отсортированном порядке (используя ex: in-order-traversal). Тем самым вы часто получаете отсортированный список в виде бесплатного перка с деревьями.
4. Деревья могут иметь лучшую производительность в худшем случае по сравнению с хеш-картой, в зависимости от того, как реализована хеш-карта (например, хеш-карта с цепочкой будет иметь O (N) наихудший случай, тогда как самоуравновешенные деревья могут гарантировать O (log N) наихудший) чехол для всех операций).

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

Answer 5

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

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

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

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

Answer 6

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