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 naprawdę małej stałej niż bardziej skomplikowaną metodę

o naprawdę dużej stałej.

O

$O$

O (\log n)

$O(\log n)$

O (1)

$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

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