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

Question

Каковы преимущества двоичных поисковых деревьев над хэш-таблицами?

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

Answer 1

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

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

Answer 2

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

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

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

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

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

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

• Итайте через содержимое дерева в отсортированном порядке

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

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

Answer 10

BSTS также предоставляет операции «FindPredecessor» и «Findsuccessor» (чтобы найти следующие самые маленькие и следующие крупные элементы) в o (logn) время, которые также могут быть очень удобными операциями. Хэш-таблица не может обеспечить в этой эффективности времени.

Answer 11

От Взломать кодирующее интервью, 6-е издание

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

Answer 12

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

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

Кроме того, поскольку B-дерево сортируется, просто находить диапазоны результатов или для выполнения профсоюзов или сливаются.

Answer 13

Это также зависит от использования, HASH позволяет найти точное совпадение. Если вы хотите запросить диапазон, то BST - это выбор. Предположим, у вас есть много данных E1, E2, E3 ..... EN.

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

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

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

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

Answer 14

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

1. Двойные каждые ведра - MALLOC (N BGETS) / изменение функции хеша. Требуется время: зависит от реализации MALLOC
2. Передача / скопируйте каждое из более ранних ведерных данных в новые данные ведра. Это операция O (N), где n представляет все данные

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

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

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

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

Answer 15

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

Answer 16

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

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

1. Максимум
2. Минимально
3. Преемник
4. Предшественник

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

Таким образом, если все, что вы хотите, это операционные вставки, удалить и удалить, то Hash Table является непревзойденным (большую часть времени) в производительности. Но если вы хотите или все операции, перечисленные выше, вы должны использовать BST, предпочтительно самобалансируя BST.

Answer 17

Двоичные валы поиска могут быть быстрее при использовании со строчными клавишами. Особенно, когда строки длинные.

Двоичные валы поиска, использующие сравнения для менее / больше, которые быстрыми для строк (когда они не равны). Таким образом, BST может быстро ответить, когда строка не найдена. Когда он найдет, ему нужно будет делать только одно полное сравнение.

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

Answer 18

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