Преимущества двоичных поисковых деревьев над таблицами Hash

Ответ 1

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

Например, если хеш-функция имеет диапазон R(h) = 0...100, тогда вам нужно выделить массив из 100 (указателей-элементов) элементов, даже если вы просто хэшируете 20 элементов. Если бы вы использовали двоичное дерево поиска для хранения той же информации, вы бы выделили столько места, сколько вам нужно, а также некоторые метаданные о ссылках.

Ответ 2

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

Чтобы проиллюстрировать мою идею, я хочу сделать крайний случай. Скажем, вы хотите получить все элементы с ключами от 0 до 5000. И на самом деле есть только один такой элемент и 10000 других элементов, ключи которых не находятся в диапазоне. BST может выполнять поиск по диапазону довольно эффективно, так как он не ищет поддерево, которое невозможно получить.

Пока, как вы можете выполнять поиск диапазона в хеш-таблице? Вам либо нужно перебирать каждое пространство в ковше, что есть O (n), либо вам нужно искать, существует ли каждый из 1,2,3,4... до 5000. (как насчет клавиш между 0 и 5000 - бесконечный набор? Например, клавиши могут быть десятичными)

Ответ 3

Одно "преимущество" двоичного дерева состоит в том, что его можно пройти, чтобы перечислить все элементы по порядку. Это невозможно сделать с таблицей Hash, но не является нормальной работой одного проекта в хешированной структуре.

Ответ 4

В дополнение ко всем остальным хорошим комментариям:

Хэш-таблицы в целом имеют лучшее поведение кэша, требующее меньше чтения памяти по сравнению с бинарным деревом. Для хеш-таблицы обычно вы получаете только одно чтение, прежде чем у вас будет доступ к ссылке, содержащей ваши данные. Бинарное дерево, если оно является сбалансированным вариантом, требует чего-то в порядке чтения k * lg (n) для некоторой константы k.

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

Деревья, как правило, представляют собой среднюю среднюю структуру данных. Они могут выступать в качестве списков, их можно легко разделить для параллельной работы, иметь быстрое удаление, вставку и поиск по порядку O (lg n). Они не делают ничего особенно хорошо, но у них также нет чрезмерно плохого поведения.

Наконец, BST намного проще реализовать в (чистых) функциональных языках по сравнению с хеш-таблицами, и они не требуют реализации разрушительных обновлений (аргумент persistence от Pascal выше).

Ответ 5

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

• найдите ближайший элемент (не обязательно равный) произвольному значению ключа (или ближайшему выше/ниже)

• перебирать содержимое дерева в отсортированном порядке

Оба подключены - двоичное дерево сохраняет свое содержимое в отсортированном порядке, поэтому вещи, требующие упорядоченного порядка, просты.

Ответ 6

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

Ответ 7

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

Ответ 8

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

Ответ 9

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

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

Ответ 10

BST также предоставляют операции "findPredecessor" и "findSuccessor" (чтобы найти следующий наименьший и следующий по величине элементы) в O (logn) времени, что также может быть очень удобным. Хэш-таблица не может обеспечить эффективность этого времени.

Ответ 11

Из Трещины в кодировании Интервью, 6-е издание

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

Ответ 12

Если вы хотите получить доступ к данным отсортированным образом, сортированный список должен поддерживаться параллельно хэш-таблице. Хорошим примером является словарь в .Net. (см. http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx).

У этого есть побочный эффект не только замедления вставок, но он потребляет больший объем памяти, чем b-дерево.

Кроме того, поскольку b-дерево сортируется, легко найти диапазоны результатов или выполнить объединения или слияния.

Ответ 13

Это также зависит от использования, Hash позволяет находить точное соответствие. Если вы хотите запросить диапазон, то выбор BST - выбор. Предположим, что у вас много данных e1, e2, e3..... en.

С хэш-таблицей вы можете найти любой элемент в постоянное время.

Если вы хотите найти значения диапазона больше e41 и меньше e8, BST может быстро найти это.

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

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

Ответ 14

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

Ответ 15

Таблицы Hast не подходят для индексирования... когда вы ищете диапазон... BST лучше. Именно поэтому большинство индексов базы данных используют деревья B + вместо HashTables

Ответ 16

Хешмап - это набор ассоциативных массивов. Таким образом, ваш массив входных значений объединяется в ведра. В открытой схеме адресации у вас есть указатель на ведро, и каждый раз, когда вы добавляете новое значение в ведро, вы обнаруживаете, где в ведре есть свободные пробелы. Есть несколько способов сделать это: вы начинаете в начале ведра и каждый раз увеличиваете указатель и проверяете, занят ли он. Это называется линейным зондированием. Затем вы можете выполнить двоичный поиск, например add, где вы удваиваете разницу между началом ведра и где вы удваиваете или отбрасываете каждый раз, когда ищете свободное пространство. Это называется квадратичным зондированием. ОК. Теперь проблемы в обоих этих методах заключаются в том, что если ведро переполняется в следующий адрес ковшей, вам нужно -

• Сдвиньте каждый квадрат size-malloc (N ковшей)/измените функцию хэша - Требуемое время: зависит от реализации malloc.
• Перенести/Скопировать каждую из данных более ранних ковшей в новые данные ковшей. Это операция O (N), где N представляет все данные

OK. но если вы используете связанный список, не должно быть такой проблемы? Да, в связанных списках у вас нет этой проблемы. Учитывая, что каждое ведро начинается со связанного списка, и если у вас есть 100 элементов в ковше, вам нужно пройти эти 100 элементов, чтобы добраться до конца связанного списка, поэтому List.add(Element E) потребуется время -

• Хэш элемента в ведро. Нормальный, как и во всех реализациях.
• Найдите время, чтобы найти последний элемент в указанной операции bucket-O (N).

Преимущество реализации связанного списка заключается в том, что вам не нужна операция выделения памяти и O (N) передача/копирование всех ковшей, как в случае реализации открытой адресации.

Таким образом, способ минимизации операции O (N) состоит в том, чтобы преобразовать реализацию в бинарное дерево поиска, где операции поиска - O (log (N)), и вы добавляете элемент в свою позицию на основе его значения, Добавленная особенность BST заключается в том, что она сортируется!

Ответ 17

Основное преимущество хэш-таблицы состоит в том, что она почти все ops в ~ = O (1). И его очень легко понять и реализовать. Он эффективно решает многие "проблемы с интервью". Так что, если вы хотите взломать интервью по кодированию, заведите лучших друзей с хэш-таблицей, -)

Ответ 18

Классы HashSet и Table являются неупорядоченными коллекциями. Это не очевидно из интерфейса (и может быть иначе), но хэш-таблицы были реализованы с использованием AVL Trees. Это означает, что хеш-код не уменьшается по модулю массива (меньше коллизий), а также означает, что нет повторной обработки массива (более плавная производительность). Тот факт, что они являются неупорядоченными коллекциями, означает, что вы предоставляете только функцию equals и функцию hashCode, а не полный сопоставление, как для деревьев. Итак, используете ли вы хэш-таблицу Table < K, T > или двоичное дерево Tree < K, T > зависит от класса K - полностью ли он сопоставим или сравним только равенство.

Бывают случаи, когда тип данных сопоставим, а равенство сравнимо - как String. Это означает, что HashSet <String> и Set <String> возможны. Поиски хеш-набора строк имеют тенденцию примерно в 10 раз быстрее, чем поиск по упорядоченному набору строк. Если компаратор дорог, тогда деревья замедляются по сравнению с HashTables. Если компаратор работает быстро (например, для целых чисел и поплавков), деревья будут работать быстрее, чем хеш-таблицы.