Какие факторы следует учитывать, когда мне нужно выбирать между хэш-таблицей или сбалансированным двоичным деревом для реализации набора или ассоциативного массива?Хэш-таблица против сбалансированного двоичного дерева
На этот вопрос нельзя ответить, в общем, я боюсь.
Проблема в том, что существует множество типов хеш-таблиц и сбалансированных двоичных деревьев, а их характеристики сильно различаются.
Итак, наивный ответ: это зависит от функциональности, в которой вы нуждаетесь.Используйте хеш-таблицу, если вам не требуется упорядочение и сбалансированное двоичное дерево в противном случае.
Для более подробного ответа давайте рассмотрим некоторые альтернативы.
Hash Table (см записи Википедии для некоторых основ)
Binary Tree
Давайте не будем забывать, что O (1) является асимптотической сложности. Для нескольких элементов коэффициент обычно более важен (по производительности). Что особенно актуально, если ваша хеш-функция медленная ...
Наконец, для наборов вы также можете рассмотреть вероятностные структуры данных, например Bloom Filters.
@ProfVersaggi: На самом деле это даже не так, некоторые хеш-таблицы плохо обрабатывают дубликаты, но некоторые преуспевают. Я советую вам прочитать [записи по теме] Хоакина М Лопеса Муньоса (http://bannalia.blogspot.fr/2014/01/a-better-hash-table.html).Он создал и поддерживает Boost MultiIndex. –
Хэш-таблицы обычно лучше, если нет необходимости хранить данные в какой-либо последовательности. Двоичные деревья лучше, если данные необходимо сортировать.
Не сохраняя сортировку, хеш-таблицы, которые могут поддерживать (вставить), несколько тривиальны. –
Это не так просто. Я боюсь нескольких вещей: 1.хэш-таблицы имеют плохую производительность (O (n)) в худшем случае 2. Чтобы изменить размер хеш-таблицы, мне нужно что-то перефразировать, это довольно дорого. Этот вопрос заключается в том, чтобы знать, как я могу избежать таких моментов и быть информированным о других _issues_. – peoro
pst: Поддержание порядка вставки возможно при использовании любой коллекции «черного ящика»; насколько можно поддерживать порядок сортировки с хэш-таблицей лучше, чем с «черным ящиком»? – supercat
таблицы хеширования являются более быстрый поиск:
Бинарные деревья:
Что вы имеете в виду, когда говорите, что бинарные деревья детерминированы? Хэш-таблицы также детерминированы. Кроме того, операции с бинарными деревьями - это O (h), где h - высота. Если это * сбалансированное * двоичное дерево, то h = O (log (n)). –
Неправда! Хэш-таблицы могут «пропустить». Например, если у вас есть массив из 10 и использовать номер телефона для его индексации (например, для использования по модулю), вы можете получить хэш, который указывает на первый элемент массива. Однако, если при создании массива сначала использовались 9 других чисел с одинаковым хешем; вам действительно нужно пройти весь путь до последнего элемента. В двоичном поиске вы получите BigO (log n), несмотря ни на что. ! ПРЕДУПРЕЖДЕНИЕ! Все зависит от того, как вы создаете свой хэш-сортировку/поиск. Существует много способов ... – whitey04
Добавление элемента в середине * не означает, что перемещение остального вокруг. Его связанная структура данных, а не массив (возможно, вы вводите в заблуждение двоичное дерево поиска с двоичным поиском, которые представляют собой две разные вещи. Все операции: O (log (n)), если добавление/удаление в середину означает перемещение остальных было бы O (n). – MAK
Если вам нужно всего лишь получить доступ к отдельным элементам, то хеш-таблицы лучше. Если вам нужен целый ряд элементов, у вас просто нет другого варианта, кроме бинарных деревьев.
Достойный момент в современной архитектуре: таблица Hash обычно, если ее коэффициент загрузки мал, имеет меньше памяти, чем двоичное дерево. Поскольку доступ к памяти имеет тенденцию быть довольно дорогостоящим по сравнению с горящими циклами ЦП, таблица Hash часто бывает быстрее.
В следующем двоичном дереве предполагается, что оно является самобалансирующимся, как красное черное дерево, дерево AVL или подобно treap.
С другой стороны, если вам нужно перефразировать все в хеш-таблице, когда вы решите его продлить, это может быть дорогостоящей операцией, которая возникает (амортизируется). Двоичные деревья не имеют этого ограничения.
Двоичные деревья проще реализовать на чисто функциональных языках.
Двоичные деревья имеют естественный порядок сортировки и естественный способ ходить по дереву для всех элементов.
Если коэффициент загрузки в хеш-таблице низок, вы можете тратить много места на память, но с двумя указателями бинарные деревья имеют тенденцию занимать больше места.
Хэш-таблицы - это почти O (1) (в зависимости от того, как вы обрабатываете коэффициент нагрузки), против деревьев бинов O (lg n).
Деревья, как правило, «средний исполнитель». Они ничего особенного не делают, но тогда ничего особенного они не делают.
Чтобы добавить другие большие ответы выше, я бы сказал:
Используйте хэш-таблицу, если объем данных не изменится (например, хранения констант); но, если количество данных изменится, используйте дерево. Это связано с тем, что в хеш-таблице после достижения коэффициента загрузки хэш-таблица должна изменяться. Операция изменения размера может быть очень медленной.
В худшем случае для добавления элемента в хеш-таблицу является O (n) из-за изменения размера, но если хеш-таблица удваивается каждый раз, доля добавлений, требующих переименования, будет уменьшаться по мере увеличения размера таблицы , Среднее количество операций переадресации на элемент никогда не будет превышать два, независимо от того, насколько большой размер таблицы. – supercat
Если размер хеш-таблицы * удваивается *, то я был бы удивлен, если количество столкновений уменьшилось, потому что хэш-таблицы работают лучше (т. Е. Небольшое количество столкновений), когда размер таблицы является простым. Кроме того, если вы просите систему предоставить вам вдвое больше памяти при каждом изменении размера, вы быстро исчерпаете память (или замедлите систему, если система перегруппирует свою память, чтобы дать вам объем смежной памяти просят). – Davidann
удвоение - это общая стратегия, но это не требуется. Требуется экспоненциальный рост. Вы можете выбрать меньшую экспоненту, если хотите, это просто означает, что среднее число операций перефразирования будет выше. В любом случае амортизированная стоимость n вставок в таблице с экспоненциальным ростом равна O (n), а самобалансирующиеся двоичные деревья поиска стоят O (n * log (n)). – rlibby
Для двоичного дерева поиска требуется общее отношение порядка между ключами. Хэш-таблица требует только отношения эквивалентности или идентичности с последовательной хэш-функцией.
Если доступно соотношение общего порядка, то сортированный массив имеет производительность поиска, сравнимую с бинарными деревьями, производительность вставки в худшем случае в порядке хэш-таблиц и меньшую сложность и использование памяти, чем обе.
В худшем случае сложность ввода хэш-таблицы может быть оставлена при O (1)/O (log K) (с K количество элементов с одинаковым хэшем), если приемлемо увеличить наихудший поиск сложность для O (K) или O (log K), если элементы могут быть отсортированы.
Инварианты для деревьев и хеш-таблиц дорого восстанавливаются, если ключи изменяются, но меньше O (n log N) для отсортированных массивов.
Эти факторы необходимо учитывать при принятии решения, реализация которых использовать:
«Для двоичного дерева поиска требуется общее отношение порядка между ключами. Хэш-таблица требует только отношения эквивалентности или идентичности с последовательной хэш-функцией». Это вводит в заблуждение. Двоичное дерево поиска всегда может использовать только те же ключи, что и хеш-таблица: хеш-значения. Это не ограничение на случаи, когда деревья могут использоваться, по сравнению с хэш-таблицами. – rlibby
@rlibby Хотя большинство реализаций хеш-ключей по умолчанию используют типы, на которых определяется общий порядок (целые числа или указатели), требуется только эквивалентность, если вы предоставляете свои собственные хэши. Таким образом, вы не можете использовать двоичное дерево поиска по хэш-ключам, потому что вы не знаете, что такое хэши, откуда они пришли, или намного меньше, если они поддерживают отношение полного порядка. – Apalala
, но если я правильно понимаю ваше предложение, то такое хэш-значение также не может использоваться в хеш-таблице. Конечно, если он * может * использоваться * в хеш-таблице, то он может * также * использоваться в наборе деревьев. Если его можно использовать в таблице, то он должен отобразиться в некоторый индекс в таблице. Можно использовать функцию, которая генерирует этот индекс для генерации ключей для набора деревьев. – rlibby
Если у вас будет много немного разных экземпляров наборов, вы, вероятно, захотите, чтобы они разделили структуру. Это легко с деревьями (если они неизменяемы или копируются на запись). Я не уверен, насколько хорошо вы можете это сделать с помощью hashtables; это, по крайней мере, менее очевидно.
По моему опыту, hastables всегда быстрее, потому что деревья страдают слишком большим количеством эффектов кеша.
Чтобы увидеть некоторые реальные данные, вы можете проверить исходную страницу из моей библиотеки TommyDS http://tommyds.sourceforge.net/
Здесь вы можете увидеть по сравнению производительность наиболее распространенного в hashTable, дерево и TRIE доступных библиотек.
Один пункт, который, как я думаю, не был рассмотрен, заключается в том, что деревья намного лучше для стойких структуры данных. То есть неизменные структуры. Стандартная хеш-таблица (т. Е. Одна, которая использует один массив связанных списков) не может быть изменена без изменения всей таблицы. Одна из ситуаций, в которой это актуально, состоит в том, что две параллельные функции имеют копию хэш-таблицы, а одна из них изменяет таблицу (если таблица изменчива, это изменение будет видно и для другого). Другая ситуация будет что-то вроде следующего:
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) узлов, которые необходимо создать (остальная часть дерева идентична).
Это означает, что эффективное дерево может быть очень удобным, когда требуются неизменные карты.
Один пункт для заметок - об обходном, минимальном и максимальном значении. Хэш-таблицы не поддерживают какой-либо упорядоченный обход или доступ к минимальным или максимальным элементам. Если эти возможности важны, бинарное дерево - лучший выбор.
https://stackoverflow.com/questions/4128546/advantages-of-binary-search-trees-over-hash-tables –