Jakie są zalety haszowania kukułki w porównaniu z dynamicznym haszowaniem idealnym?

12

Dynamiczne idealne tabele skrótów i tabele skrótów kukułki to dwie różne struktury danych, które obsługują wyszukiwanie w najgorszym przypadku O (1) i oczekiwane wstawianie i usuwanie w czasie O (1). Oba wymagają dla swoich operacji O (n) przestrzeni pomocniczej i dostępu do rodzin funkcji skrótu.

Myślę, że obie te struktury danych są same w sobie piękne i genialne, ale nie jestem pewien, czy widzę, jak i kiedy jedna z nich byłaby lepsza od drugiej.

Czy istnieją konkretne konteksty, w których jedna z tych struktur danych ma wyraźną przewagę nad drugą? Czy są w większości wymienne?

data-structures hash-tables templatetypedef
źródło
Nie jestem pewien, czy któraś z tych technik jest faktycznie stosowana w praktyce. Zwykle tego rodzaju struktury danych, które oferują najlepsze asymptotyczne granice, są głównie przedmiotem badań, ponieważ zwykle mają dużą stałą ukrytą w adnotacji W praktyce możesz preferować prostszą, łatwiejszą do wdrożenia technikę O ( log n ) o naprawdę małej stałej niż bardziej skomplikowaną metodę O ( 1 ) o naprawdę dużej stałej. OO(log⁡n)O(1)
Tom van der Zanden
@TomvanderZanden To zdecydowanie prawda. Interesują mnie również teoretyczne zalety jednego podejścia względem drugiego - czy są jakieś fajne właściwości teoretyczne, które każde podejście ma do zaoferowania w stosunku do drugiego?
templatetypedef
@templatetypedef, zachęcam więc do dodania tego do pytania. Ludzie nie powinni czytać komentarzy, aby zrozumieć twoje pytanie - komentarze są przejściowe i mogą zniknąć w dowolnym momencie.
DW
Tak, te techniki są faktycznie stosowane w praktyce, zwykle w obszarach niszowych.
Pseudonim
1
Jedną z zalet mieszania kukułki jest to, że łatwo ją zrozumieć i wdrożyć. Ponadto, imho, jest o wiele łatwiej analizować niż dynamiczne haszowanie idealne.
A.Schulz

Odpowiedzi:

3

Dynamiczne doskonałe haszowanie w rozumieniu Dietzfelbinger i in. potrzebuje tylko 2 niezależnych skrótów . Chociaż istnieją pewne wyniki dotyczące prostego haszowania dla tablic haszyszowych z kukułką, takie jak skręcone haftowanie tabelaryczne i „Jawne i wydajne rodziny mieszania wystarczające do mieszania kukułki za pomocą skrytki”, oryginalne dynamiczne haszowanie idealne jest w pewnym sensie bardziej solidne.

jbapple
źródło
Zobacz wyjaśniający komentarz PO: „Interesują mnie również teoretyczne zalety jednego podejścia w stosunku do drugiego - czy są jakieś fajne właściwości teoretyczne, które każde podejście ma do zaoferowania w stosunku do drugiego?”
jbapple
3

W haszowaniu kukułki wyszukiwania można przeprowadzać równolegle, podczas gdy w oryginalnym dynamicznym haszowaniu idealnym Dietzfelbinger i in., Wyszukiwania wymagają dwóch łańcuchowych dostępów do pamięci, w których drugi dostęp wykorzystuje informacje uzyskane z pierwszego.

jbapple
źródło
1

Względnie łatwo jest zwiększyć efektywność przestrzenną haszowania kukułki, pozwalając, aby w każdym miejscu było więcej niż jeden przedmiot. W przypadku gniazd o rozmiarze 4 wydajność przestrzeni wynosi około 95%. Oznacza to, że przedmioty można wstawiać, dopóki 95% miejsca w tabeli nie zostanie wykorzystane do przechowywania przedmiotów, a nie tylko miejsc, do których mogą się udać.

Z drugiej strony granice w Dietzfelbinger i in. papier z dynamicznym haszowaniem doskonałym dowodzi tylko, że operacje wstawiania mogą być kontynuowane, dopóki tabela nie będzie wypełniona w więcej niż 3%.

jbapple
źródło
Możesz połączyć dwie odpowiedzi razem. :-)
templatetypedef
0

O(1)O(n)

jbapple
źródło