Jest to ogólna odpowiedź niespecyficzna dla języka Python.
Porównanie złożoności algorytmicznej
| Hash Table | Red-Black Tree |
-------+-------------+---------------------+
Space | O(n) : O(n) | O(n) : O(n) |
Insert | O(1) : O(n) | O(log n) : O(log n) |
Fetch | O(1) : O(n) | O(log n) : O(log n) |
Delete | O(1) : O(n) | O(log n) : O(log n) |
| avg :worst | average : worst |
Problem z tabelami skrótów polega na tym, że skróty mogą się kolidować. Istnieją różne mechanizmy rozwiązywania kolizji, np. Otwarte adresowanie lub oddzielne tworzenie łańcuchów. Absolutnie najgorszym przypadkiem jest to, że wszystkie klucze mają ten sam kod skrótu, w którym to przypadku tabela skrótów ulegnie degradacji do połączonej listy.
We wszystkich innych przypadkach tablica skrótów jest świetną strukturą danych, łatwą do wdrożenia i zapewniającą dobrą wydajność. Minusem jest to, że implementacje, które mogą szybko powiększać tabelę i redystrybuować swoje wpisy, prawdopodobnie zmarnują prawie tyle pamięci, ile faktycznie jest używane.
Drzewa RB są samowyważące i w najgorszym przypadku nie zmieniają złożoności algorytmicznej. Są jednak trudniejsze do wdrożenia. Ich średnia złożoność jest również gorsza niż w przypadku tabeli skrótów.
Ograniczenia dotyczące kluczy
Wszystkie klucze w tabeli haszującej muszą być haszowalne i porównywalne, aby zapewnić sobie równość. Jest to szczególnie łatwe w przypadku ciągów lub liczb całkowitych, ale jest również dość łatwe do rozszerzenia na typy zdefiniowane przez użytkownika. W niektórych językach, takich jak Java, właściwości te są z definicji gwarantowane.
Klucze w drzewie RB muszą mieć całkowitą kolejność: każdy klucz musi być porównywalny z każdym innym kluczem, a oba klucze muszą albo porównywać mniejsze, większe lub równe. Ta równość porządkowa musi być równoważna z równością semantyczną. Jest to proste w przypadku liczb całkowitych i innych liczb, również dość łatwe w przypadku ciągów znaków (kolejność musi być tylko spójna i nie może być obserwowana z zewnątrz, więc kolejność nie musi uwzględniać ustawień narodowych [1] ), ale trudna w przypadku innych typów, które nie mają właściwej kolejności . Absolutnie niemożliwe jest posiadanie kluczy różnych typów, chyba że możliwe jest ich porównanie.
[1]: Właściwie tutaj się mylę. Dwa łańcuchy mogą nie być równe bajtom, ale nadal mogą być równoważne zgodnie z regułami niektórych języków. Zobacz np. Normalizacje Unicode dla jednego przykładu, w którym dwa równe łańcuchy są zakodowane inaczej. To, czy kompozycja znaków Unicode ma znaczenie dla klucza skrótu, jest czymś, czego implementacja tablicy skrótów nie może wiedzieć.
Można by pomyśleć, że tanim rozwiązaniem dla kluczy RB-Tree byłoby najpierw sprawdzenie równości, a następnie porównanie tożsamości (tj. Porównanie wskaźników). Jednak ta kolejność nie byłaby przechodnia: jeśli a == bi id(a) > id(c), to również musi być zgodna z tym id(b) > id(c), co nie jest tutaj zagwarantowane. Zamiast tego możemy użyć kodu skrótu kluczy jako kluczy wyszukiwania. Tutaj porządkowanie działa poprawnie, ale możemy otrzymać wiele różnych kluczy z tym samym kodem skrótu, które zostaną przypisane do tego samego węzła w drzewie RB. Aby rozwiązać te kolizje skrótów, możemy zastosować oddzielne tworzenie łańcuchów, podobnie jak w przypadku tabel skrótów, ale dziedziczy to również najgorsze zachowanie dla tabel skrótów - najgorsze z obu światów.
Inne aspekty
Oczekuję, że tablica skrótów będzie miała lepszą lokalizację pamięci niż drzewo, ponieważ tabela skrótów jest w zasadzie tylko tablicą.
Wpisy w obu strukturach danych mają dość wysoki narzut:
- tablica skrótów: klucz, wartość i wskaźnik następnego wpisu w przypadku oddzielnego tworzenia łańcuchów. Przechowywanie kodu skrótu może także przyspieszyć zmianę rozmiaru.
- Drzewo RB: klucz, wartość, kolor, lewy wskaźnik potomny, prawy wskaźnik potomny. Zwróć uwagę, że chociaż kolor jest jednym bitem, problemy z wyrównaniem mogą oznaczać, że nadal będziesz marnował wystarczająco dużo miejsca na prawie cały wskaźnik, a nawet prawie cztery wskaźniki, gdy można przypisać tylko bloki pamięci o dwóch rozmiarach. W każdym razie pozycja drzewa RB zużywa więcej pamięci niż pozycja tabeli mieszania.
Wstawienia i usunięcia w drzewie RB obejmują rotację drzewa. Nie są one naprawdę kosztowne, ale wiążą się z dodatkowymi kosztami. W skrócie wstawianie i usuwanie nie są droższe niż zwykły dostęp (chociaż zmiana rozmiaru tabeli skrótów po wstawieniu jest O(n)przedsięwzięciem).
Tabele skrótów są z natury zmienne, podczas gdy drzewo RB można również wdrożyć w niezmienny sposób. Jest to jednak rzadko przydatne.