Zalety binarnych drzew Wyszukiwania nad tabelami Hash

Jedną z zalet, na które nikt inny nie zwrócił uwagi, jest to, że binarne drzewo wyszukiwania pozwala na efektywne wyszukiwanie zakresów.

Aby zilustrować mój pomysł, chcę zrobić ekstremalny przypadek. Powiedz, że chcesz uzyskać wszystkie elementy, których klucze są od 0 do 5000. A właściwie jest tylko jeden taki element i 10000 innych elementów, których kluczy nie ma w zasięgu. BST może wykonywać wyszukiwanie zakresów dość efektywnie, ponieważ nie przeszukuje podzbioru, który jest niemożliwy do odpowiedz.

While, jak można przeszukiwać zakresy w tabeli hash? Albo trzeba iterować każdą przestrzeń kubełkową, która jest O (n), albo trzeba szukać, czy każdy z 1,2,3,4... istnieje do 5 tys. (a co z kluczami od 0 do 5000 to nieskończony zestaw? na przykład klucze mogą być dziesiętne)

Jedną z "zalet" drzewa binarnego jest to, że może ono być przesuwane, aby wyświetlić listę wszystkich elementów w kolejności. Nie jest to niemożliwe z tabelą Haszującą, ale nie jest to normalne działanie jednego projektu w strukturę haszowaną.

Oprócz wszystkich innych dobrych komentarzy:

Tabele Hash ogólnie mają lepsze zachowanie pamięci podręcznej, wymagające mniej odczytów pamięci w porównaniu z drzewem binarnym. W przypadku tabeli hash zwykle tylko jeden odczyt odbywa się przed uzyskaniem dostępu do referencji przechowującej dane. Drzewo binarne, jeśli jest wariantem zrównoważonym, wymaga czegoś w kolejności K * LG(N) odczytu pamięci dla pewnej stałej k.

Z drugiej strony, jeśli wróg zna twoją funkcję hashową, wróg może wymusić tabelę hash, aby dokonać kolizji, znacznie utrudniając jej wydajność. Obejściem jest losowy wybór funkcji hash z rodziny, ale BST nie ma tej wady. Ponadto, gdy ciśnienie stołu mieszającego rośnie zbyt mocno, często masz tendencję do powiększania i ponownego przydzielania stołu mieszającego, co może być kosztowną operacją. BST ma tutaj prostsze zachowanie i nie ma tendencji do nagłego przydzielania dużej ilości danych i wykonywania operacji ponownego ładowania.

Drzewa wydają się być ostateczne średnia struktura danych. Mogą działać jako listy, mogą być łatwo dzielone do pracy równoległej, mają szybkie usuwanie, wstawianie i wyszukiwanie w kolejności O (lg n) . Nie robią nic [3]} szczególnie [4]} cóż, ale nie mają też zbyt złego zachowania.

Wreszcie, BST są znacznie łatwiejsze do zaimplementowania w (czystych) językach funkcyjnych w porównaniu do tabel hashowych i nie wymagają destrukcyjnych aktualizacji do implementacji (argument persistence napisany przez Pascala powyżej).

Główne zalety drzewa binarnego nad tabelą hash jest to, że drzewo binarne daje dwie dodatkowe operacje, których nie można wykonać (łatwo, szybko) z tabelą hash

• Znajdź element najbliższy (niekoniecznie równy) dowolnej wartości klucza (lub najbliższy powyżej/poniżej)

• Iteracja poprzez zawartość drzewa w posortowanej kolejności

Oba są połączone -- drzewo binarne zachowuje swoją zawartość w uporządkowanej kolejności, więc rzeczy, które wymagają ten uporządkowany porządek jest łatwy do zrobienia.

(zbalansowane) binarne drzewo wyszukiwania ma również tę zaletę, że jego asymptotyczna złożoność jest w rzeczywistości górną granicą, podczas gdy "stałe" czasy dla tabel skrótów są czasy amortyzowane: jeśli masz nieodpowiednią funkcję skrótu, możesz w końcu obniżyć się do czasu liniowego, a nie stałego.

Hashtable zajmowałby więcej miejsca przy pierwszym utworzeniu-będzie miał wolne miejsca na elementy, które mają być jeszcze wstawione (niezależnie od tego, czy są kiedykolwiek wstawiane), binarne drzewo wyszukiwania będzie tylko tak duże, jak musi być. Ponadto, gdy tabela hash wymaga więcej miejsca, rozszerzenie do innej struktury może być czasochłonne, ale to może zależeć od implementacji.

Binarne drzewo wyszukiwania może być zaimplementowane za pomocą interfejsu persistent, gdzie zwracane jest nowe drzewo, ale stare drzewo nadal istnieje. Starannie zaimplementowane stare i nowe drzewa dzielą większość swoich węzłów. Nie można tego zrobić przy użyciu standardowej tabeli hash.

Drzewo binarne jest wolniejsze do przeszukiwania i wstawiania, ale ma bardzo ładną funkcję przejścia infiksu, co zasadniczo oznacza, że można iterację przez węzły drzewa w kolejności posortowanej.

Iteracja wpisów w tabeli hash po prostu nie ma większego sensu, ponieważ wszystkie są rozproszone w pamięci.

From Cracking the Coding Interview, 6th Edition

Możemy zaimplementować tabelę hashową za pomocą zbalansowanego binarnego drzewa wyszukiwania (BST). To daje nam czas Wyszukiwania O (log n). Zaletą tego jest potencjalnie mniej miejsca, ponieważ nie przydzielamy już dużej tablicy. Możemy również iterować za pomocą kluczy w kolejności, co może być czasami przydatne.

BSTs dostarczają również operacje "findPredecessor" i "findSuccessor" (aby znaleźć kolejne najmniejsze i następne największe elementy) w czasie o (logn), co również może być bardzo przydatne. Tabela Hash nie może zapewnić w tym czasie efektywności.

Jeśli chcesz uzyskać dostęp do danych w sposób posortowany, to posortowana lista musi być utrzymywana równolegle do tabeli hash. Dobrym przykładem jest słownik w .Net. (zobacz http://msdn.microsoft.com/en-us/library/3fcwy8h6.aspx).

Ma to efekt uboczny nie tylko spowalniających wstawek, ale zużywa większą ilość pamięci niż drzewo B.

Ponadto, ponieważ drzewo b jest posortowane, łatwo jest znaleźć zakresy wyników lub wykonać połączenia lub połączenia.

To również zależy od zastosowania, Hash pozwala zlokalizować dokładne dopasowanie. Jeśli chcesz zapytać o zakres, to BST jest wyborem. Załóżmy, że masz dużo danych e1, e2, e3 ..... en.

Za pomocą tabeli hash można zlokalizować dowolny element w stałym czasie.

Jeśli chcesz znaleźć wartości zakresu większe niż e41 i mniejsze niż e8, BST może to szybko znaleźć.

Kluczową rzeczą jest funkcja hash używana do uniknięcia kolizji. Oczywiście nie możemy całkowicie uniknąć kolizji, w którym to przypadku uciekajcie się do łączenia lub innych metod. To sprawia, że pobieranie nie jest już stały czas w najgorszych przypadkach.

Po wypełnieniu tabela hash musi zwiększyć rozmiar wiadra i ponownie skopiować wszystkie elementy. Jest to dodatkowy koszt nieobecny w BST.

Binarne drzewa wyszukiwania są dobrym wyborem do zaimplementowania słownika, jeśli klucze mają określoną całkowitą kolejność (klucze są porównywalne) i chcesz zachować informacje o kolejności.

Ponieważ BST zachowuje informacje o kolejności, zapewnia cztery dodatkowe operacje zestawów dynamicznych, które nie mogą być wykonywane (efektywnie)przy użyciu tabel skrótów. Operacje te to:

1. maksimum
2. Minimum
3. następca
4. poprzednik

Wszystkie te operacje jak każda operacja BST mają złożoność czasową O (H). Dodatkowo wszystkie zapisane klucze pozostają posortowane w BST, dzięki czemu można uzyskać posortowaną sekwencję kluczy po prostu przemierzając drzewo w kolejności.

W podsumowaniu jeśli wszystko, co chcesz to operacje insert, delete i remove, to tabela hash jest nie do pobicia (przez większość czasu) w wydajności. Ale jeśli chcesz dowolne lub wszystkie operacje wymienione powyżej, powinieneś użyć BST, najlepiej samobalansującego BST.

Główną zaletą tabeli hash jest to, że wykonuje prawie wszystkie operacje w ~ = O (1). I jest bardzo łatwy do zrozumienia i wdrożenia. Skutecznie rozwiązuje wiele "problemów z wywiadem". Więc jeśli chcesz złamać wywiad z kodowaniem, zaprzyjaźnij się z tabelą hash; -)

Hashmap jest ustawioną tablicą asocjacyjną. Tak więc Twoja tablica wartości wejściowych jest łączona w wiadra. W otwartym schemacie adresowania masz wskaźnik do wiadra i za każdym razem, gdy dodajesz nową wartość do wiadra, dowiadujesz się, gdzie w wiadrze znajdują się wolne miejsca. Istnieje kilka sposobów na to-zaczynasz na początku wiadra i za każdym razem zwiększasz wskaźnik i sprawdzasz, czy jest zajęty. To się nazywa sondowanie liniowe. Następnie możesz wykonać wyszukiwanie binarne, takie jak add, gdzie podwoić różnicę między początkiem wiadra i gdzie podwoić w górę lub z powrotem w dół za każdym razem, gdy szukasz wolnego miejsca. Nazywa się to sondowaniem kwadratowym. OK. Problem w obu tych metodach polega na tym, że jeśli wiadro przepełni się do następnego adresu wiadra, musisz-

1. podwojenie rozmiaru każdego wiadra-malloc(N buckets) / zmiana funkcji hash- Wymagany czas: zależy od implementacji malloc
2. Przenieś/skopiuj każdy z wcześniejszych danych buckets do nowe dane wiader. Jest to operacja O (N), gdzie N reprezentuje całe dane

OK. ale jeśli używasz linkedlist, nie powinno być takiego problemu, prawda? Tak, w linkowanych listach nie masz tego problemu. Biorąc pod uwagę, że każdy element bucket zaczyna się od listy połączonej, a jeśli masz 100 elementów w wiadrze, wymaga to przejścia tych 100 elementów, aby dotrzeć do końca listy połączonej, stąd lista.add (Element E) zajmie trochę czasu-

1. Hash element do wiadra- Normalne jak we wszystkich implementacjach
2. Znajdź ostatni element w operacji bucket - O(N).

Zaletą implementacji linkedlist jest to, że nie jest potrzebna operacja alokacji pamięci i O(N) transfer/Kopia wszystkich kubełków, jak w przypadku implementacji open addressing.

Tak więc, sposobem zminimalizowania operacji O(N) jest przekonwertowanie implementacji do binarnego drzewa wyszukiwania, w którym operacje find to o(log(n)) i dodanie elementu w swojej pozycji opartej na jego wartości. Dodatkową cechą BST jest to, że jest sortowane!

Tabele Hash nie nadają się do indeksowania. Kiedy szukasz zasięgu, BST są lepsze. Z tego powodu większość indeksów baz danych używa drzew B+ zamiast tabel Hashowych

Binarne drzewa wyszukiwania mogą być szybsze, gdy są używane z kluczami łańcuchowymi. Zwłaszcza, gdy struny są długie.

Binarne drzewa wyszukiwania wykorzystujące porównania dla mniej / więcej, które są szybkie dla ciągów (gdy nie są równe). Tak więc BST może szybko odpowiedzieć, gdy ciąg znaków nie został znaleziony. Kiedy zostanie znaleziony, będzie musiał zrobić tylko jedno pełne porównanie.

W tabeli hash. Musisz obliczyć hash łańcucha, a to oznacza, że musisz przejść przez wszystkie bajty co najmniej raz, aby obliczyć hash. Z drugiej strony, gdy znaleziono pasujący wpis.

GCC C++ case study

Jak pokazano na Jaka jest podstawowa struktura danych zestawu STL w C++?, w GCC 6.4:

• std::map używa BST
• std::unordered_map używa hashmap

Więc to już wskazuje na fakt, że nie można skutecznie poprzeć hashmapy, co jest być może głównym przewaga BST.

A następnie porównałem czasy wstawiania w hash map vs BST vs heap w Heap vs Binary Search Tree (BST), co wyraźnie podkreśla kluczowe cechy wydajności:

• Wstawianie BST to o (log), hashmap to O(1). I w tej konkretnej implementacji, hashmap jest prawie zawsze szybszy niż BST, nawet dla stosunkowo małych rozmiarów

• Hashmap, chociaż ogólnie jest znacznie szybszy, ma kilka bardzo powolnych wstawek widoczne jako pojedyncze punkty na powiększonym wykresie.

  Dzieje się tak, gdy implementacja zdecyduje, że nadszedł czas, aby zwiększyć jej rozmiar i trzeba ją skopiować na większą.

  Dokładniej, wynika to z faktu, że tylko jego złożoność amortyzowana jest O (1), a nie najgorszym przypadkiem, który w rzeczywistości jest O(n) podczas kopii tablicy.

  Może to sprawić, że hashmapy będą nieodpowiednie dla niektórych aplikacji w czasie rzeczywistym, gdzie potrzebujesz silniejszego czasu Gwarancje.

Powiązane:

• drzewa binarne a listy połączone a tabele Hash
• https://cs.stackexchange.com/questions/270/hash-tables-versus-binary-trees