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

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

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

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

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

Хэш-таблица (см. статью в Википедии, где приведены некоторые основы)

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

Бинарное дерево

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

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

Наконец, для наборов вы также можете рассмотреть вероятностные структуры данных, такие как фильтры Блума.

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

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

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

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

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

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

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

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

Деревья, как правило, являются «средним исполнителем». Нет ничего, что они делают особенно хорошо, но и ничего особенно плохого они не делают.

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

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

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

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

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

1. Наличие отношений общего порядка.
2. Наличие хорошей хэш-функции для отношения эквивалентности.
3. Априорное знание количества элементов.
4. Знание скорости вставки, удаления и поиска.
5. Относительная сложность функций сравнения и хеширования.

Хэш-таблицы обеспечивают более быстрый поиск:

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

Бинарные деревья:

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

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

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

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

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

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) узлами, которые необходимо создать (остальная часть дерева идентична).

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

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

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

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

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