Хэш-таблица против сбалансированного двоичного дерева

Ответ 1

На этот вопрос нельзя ответить, в общем, я боюсь.

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

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

Для более подробного ответа рассмотрим некоторые альтернативы.

Таблица хэшей (см. запись в Wikipedia для некоторых основ)

• Не все хеш-таблицы используют связанный список как ведро. Популярной альтернативой является использование "лучшего" ведра, например двоичного дерева или другой хеш-таблицы (с другой хэш-функцией),...
• Некоторые хеш-таблицы вообще не используют ведра: см. раздел "Открытая адресация" (они приходят с другими проблемами, очевидно)
• Есть что-то под названием "Линейное повторное хеширование" (это качество детализации реализации), которое позволяет избежать ловушки "stop-the-world-and-rehash". В основном на этапе миграции вы вставляете только "новую" таблицу, а также перемещаете одну "старую" запись в "новую" таблицу. Конечно, фаза миграции означает двойной поиск и т.д.

Двоичное дерево

• Повторная балансировка стоит дорого, вы можете рассмотреть Skip-List (также лучше для многопоточных доступов) или Splay Tree.
• Хороший распределитель может "упаковывать" узлы вместе в память (лучшее поведение кэширования), хотя это не облегчает проблему поиска указателя.
• B-Tree и варианты также предлагают "упаковку"

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

Наконец, для множеств вы также можете рассмотреть вероятностные структуры данных, например Bloom Filters.

Ответ 2

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

Ответ 3

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

В следующем двоичном дереве предполагается, что он является самобалансирующимся, например, красным черным деревом, деревом AVL или подобно treap.

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

Двоичные деревья проще реализовать в чисто функциональных языках.

Двоичные деревья имеют естественный порядок сортировки и естественный способ ходить по дереву для всех элементов.

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

Таблицы хэшей почти равны O (1) (в зависимости от того, как вы обрабатываете коэффициент загрузки) и Bin tree O (lg n).

Деревья обычно являются "средним исполнителем". Они ничего особенного не делают, но тогда ничего особенного они не делают.

Ответ 4

Таблицы хэшей быстрее просматриваются:

• Вам нужен ключ, который генерирует равномерное распределение (в противном случае вы пропустите много, и вам придется полагаться на что-то другое, кроме хеша, например, на линейный поиск).
• Хэш может использовать много пустого пространства. Вы можете зарезервировать 256 записей, но только 8 (пока).

Двоичные деревья:

• Детерминированный. O (log n) Я думаю...
• Не нужно дополнительное пространство, например, хеш-таблицы
• Должен быть отсортирован. Добавление элемента в середину означает перемещение остальных вокруг.

Ответ 5

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

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

В худшем случае сложность вставки хэш-таблицы может быть оставлена ​​при O (1)/O (log K) (с K количество элементов с одинаковым хэшем), если это приемлемо для увеличения сложности поиска в наихудшем случае к O (K) или O (log K), если элементы могут быть отсортированы.

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

Это факторы, которые необходимо учитывать при принятии решения о том, какую реализацию использовать:

• Доступность отношения полного порядка.
• Наличие хорошей хэш-функции для отношения эквивалентности.
• Предварительное знание количества элементов.
• Знание о скорости вставки, удаления и поиска.
• Относительная сложность функций сравнения и хэширования.

Ответ 6

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

Ответ 7

Чтобы добавить к другим замечательным ответам выше, я бы сказал:

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

Ответ 8

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

def bar(table):
    # some intern stuck this line of code in
    table["hello"] = "world"
    return table["the answer"]

def foo(x, y, table):
    z = bar(table)
    if "hello" in table:
        raise Exception("failed catastrophically!")
    return x + y + z

important_result = foo(1, 2, {
    "the answer": 5,
    "this table": "doesn't contain hello", 
    "so it should": "be ok"
})
# catastrophic failure occurs

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

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

Это означает, что эффективное дерево может быть очень удобным, когда требуются неизменные карты.

Ответ 9

Если у вас будет несколько немного разных экземпляров наборов, вы, вероятно, захотите, чтобы они разделили структуру. Это легко с деревьями (если они неизменяемы или копируются на запись). Я не уверен, насколько хорошо вы можете это сделать с помощью hashtables; это, по крайней мере, менее очевидно.

Ответ 10

По моему опыту, hastables всегда быстрее, потому что деревья страдают слишком большим количеством эффектов кеша.

Чтобы увидеть некоторые реальные данные, вы можете проверить контрольную страницу моей библиотеки TommyDS http://tommyds.sourceforge.net/

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

Ответ 11

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