Tabela Hash vs zbalansowane drzewo binarne [zamknięte]

Tabele Hash są na ogół lepsze, jeśli nie ma potrzeby przechowywania danych w jakiejkolwiek kolejności. Drzewa binarne są lepsze, jeśli dane muszą być sortowane.

GODNY UWAGI punkt w nowoczesnej architekturze: tablica Hashowa zwykle, jeśli jej współczynnik obciążenia jest niski, będzie miała mniej odczytów pamięci niż drzewo binarne. Ponieważ dostęp do pamięci jest dość kosztowny w porównaniu z cyklem wypalania procesora, tabela skrótów jest często szybsza.

w poniższym drzewie binarnym przyjmuje się, że jest samobalansujące, jak czerwone czarne drzewo, drzewo AVL lub jak treap .

Z drugiej strony, jeśli trzeba ponownie wszystko w tabeli hash, gdy zdecydujesz się na rozszerzyć go, może to być kosztowna operacja, która występuje (amortyzowane). Drzewa binarne nie mają tego ograniczenia.

Drzewa binarne są łatwiejsze do zaimplementowania w językach czysto funkcjonalnych.

Drzewa binarne mają naturalny porządek sortowania i naturalny sposób chodzenia po drzewie dla wszystkich elementów.

Gdy współczynnik obciążenia w tabeli hash jest niski, możesz marnować dużo miejsca w pamięci, ale z dwoma wskaźnikami drzewa binarne zajmują więcej miejsca.

Tabele Hash są prawie O (1) (w zależności od sposobu obsługi współczynnika obciążenia) vs.Bin trees O (lg n).

Drzewa wydają się być "przeciętnym wykonawcą". Nic nie robią szczególnie dobrze, ale nic nie robią szczególnie źle.

Binarne drzewo wyszukiwania wymaga całkowitej relacji kolejności między kluczami. Tabela hash wymaga tylko relacji równoważności lub tożsamości ze spójną funkcją hash.

Jeśli dostępna jest całkowita relacja kolejności, to posortowana tablica ma wydajność wyszukiwania porównywalną z drzewami binarnymi, najgorszą wydajność wstawiania w kolejności tabel hashowych oraz mniejszą złożoność i zużycie pamięci niż obie.

Najgorszą złożoność wstawiania tabeli hash można pozostawić na O(1) / O(log K) (Z k liczba elementów z tym samym hash), jeśli dopuszczalne jest zwiększenie złożoności wyszukiwania najgorszych przypadków do O(K) lub o(log K), jeśli elementy mogą być sortowane.

Niezmienniki zarówno dla drzew, jak i tabel hashowych są kosztowne do przywrócenia w przypadku zmiany kluczy, ale mniej niż O (N log N) dla posortowanych tablic.

Są to czynniki, które należy wziąć pod uwagę przy podejmowaniu decyzji, którą implementację zastosować:

1. dostępność całego zamówienia związek.
2. dostępność dobrej funkcji hashującej dla relacji równoważności.
3. A - znajomość liczby elementów.
4. Wiedza o szybkości wstawiania, usuwania i wyszukiwania.
5. względna złożoność funkcji porównawczych i hashujących.

Tabele Hash są szybszymi wyszukiwaniami:

• potrzebny jest klucz, który generuje równomierną dystrybucję (w przeciwnym razie wiele stracisz i będziesz musiał polegać na czymś innym niż hash; jak wyszukiwanie liniowe).
• Hash ' y mogą używać dużo pustej przestrzeni. Możesz zarezerwować 256 wpisów, ale potrzebujesz tylko 8 (na razie).

Drzewa binarne:

Deterministyczne. O (log n) chyba...
• nie potrzebujesz dodatkowego miejsca, jak tabele hash mogą
• musi być uporządkowane. Dodawanie elementu w środek oznacza przenoszenie reszty.

Jeśli potrzebujesz tylko dostępu do pojedynczych elementów, Hashtable są lepsze. Jeśli potrzebujesz szeregu elementów, po prostu nie masz innej opcji niż drzewa binarne.

Aby dodać do innych wspaniałych odpowiedzi powyżej, powiedziałbym:

Użyj tabeli hash, jeśli ilość danych się nie zmieni (np. przechowywanie stałych); ale jeśli ilość danych się zmieni, użyj drzewa. Wynika to z faktu, że w tabeli hash, po osiągnięciu współczynnika obciążenia, tabela hash musi zmienić rozmiar. Operacja zmiany rozmiaru może być bardzo powolna.

Jedna kwestia, o której nie sądzę, że została poruszona, to fakt, że drzewa są znacznie lepsze dlatrwałych struktur danych. Czyli niezmienne struktury. Standardowa tabela hash (tj. taka, która używa pojedynczej tablicy połączonych List) nie może być modyfikowana bez modyfikacji całej tabeli. Jedną z sytuacji, w której ma to znaczenie, jest sytuacja, w której dwie równoległe funkcje mają kopię tabeli hash, a jedna z nich zmienia tabelę (jeśli tabela jest zmienna, zmiana ta będzie widoczna dla drugiej jako cóż). Inna sytuacja byłaby podobna do następującej:

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

W przypadku zmiennej tabeli nie możemy zagwarantować, że tabela, którą odbiera funkcja, pozostanie tą tabelą przez cały czas jej wykonywania, ponieważ inne wywołania funkcji mogą ją zmodyfikować.

Oznacza to, że wydajne drzewo może być bardzo wygodne, gdy pożądane są niezmienne mapy.

Jeśli masz wiele nieco różnych wystąpień zestawów, prawdopodobnie będziesz chciał, aby współdzieliły strukturę. Jest to łatwe w przypadku drzew (jeśli są niezmienne lub kopiują przy zapisie). Nie jestem pewien, jak dobrze można to zrobić z hashtables; to przynajmniej mniej oczywiste.

Z mojego doświadczenia wynika, że hastable są zawsze szybsze, ponieważ drzewa cierpią za dużo efektów pamięci podręcznej.

Aby zobaczyć prawdziwe dane, możesz sprawdzić stronę benchmark mojej biblioteki TommyDS http://tommyds.sourceforge.net/

Tutaj możesz zobaczyć porównanie wydajności najpopularniejszych bibliotek hashtable, tree i trie.

Jeden punkt do zwrócenia uwagi dotyczy elementu trawersowego, minimalnego i maksymalnego. Tabele Hash nie obsługują żadnych uporządkowanych przejść ani dostępu do minimalnych lub maksymalnych elementów. Jeśli te możliwości są ważne, drzewo binarne jest lepszym wyborem.