(Kiedy) to wyszukiwanie tablicy skrótów O (1)?

70

Często mówi się, że wyszukiwanie tablicy skrótów działa w stałym czasie: obliczasz wartość skrótu, co daje indeks dla wyszukiwania tablicy. Jednak ignoruje to kolizje; w najgorszym przypadku każdy przedmiot ląduje w tym samym wiadrze, a czas wyszukiwania staje się liniowy ( ). $\Theta(n)$

Czy istnieją warunki dotyczące danych, które mogą sprawić, że wyszukiwanie tablicy skrótów będzie naprawdę ? Czy to tylko średnio, czy może tablica haszująca może wyszukiwać w najgorszym przypadku ? $O(1)$ $O(1)$

Uwaga: pochodzę z perspektywy programisty; kiedy przechowuję dane w tabeli skrótów, prawie zawsze są to ciągi znaków lub niektóre złożone struktury danych, a dane zmieniają się podczas życia tabeli skrótów. Chociaż doceniam odpowiedzi na temat idealnych skrótów, są urocze, ale niepotwierdzone i niepraktyczne z mojego punktu widzenia.

PS Kontynuacja: Dla jakiego rodzaju danych są operacje tabeli skrótów O (1)?

— Gilles
źródło

3

Czy możesz żyć z zamortyzowanym czasem dostępu? Zasadniczo wydajność tabeli skrótów będzie w dużym stopniu zależeć od tego, ile narzutów dla rzadkich tabel skrótów jesteś gotów tolerować oraz od tego, jak rozłożone są rzeczywiste wartości skrótów.

O (1)

$\cal{O}(1)$

— Raphael

5

Och, przy okazji: możesz uniknąć liniowego zachowania w najgorszym przypadku, używając (zrównoważonych) drzew wyszukiwania zamiast list.

— Raphael

1

@Raphael Byłbym bardzo zainteresowany odpowiedzią, która wyjaśnia (ogólnie), kiedy mogę liczyć na amortyzację a kiedy nie mogę. Jeśli chodzi o sposób dystrybucji wartości skrótu, to jest naprawdę część mojego pytania: skąd mogę wiedzieć? Wiem, że funkcje skrótu powinny dobrze rozprowadzać wartości; ale jeśli zawsze tak robią, najgorszy przypadek nigdy nie zostanie osiągnięty, co nie ma sensu.

O (1)

$O(1)$

— Gilles

1

Uważaj również na przedwczesną optymalizację; dla danych o niewielkich rozmiarach (kilka tysięcy elementów) często widziałem zbalansowane drzewa binarne przewyższają tabele hasht z powodu niższego obciążenia (porównania ciągów są znacznie tańsze niż skróty ciągów).

O (\log n)

$O(\log n)$

— isturdy

Daj nam kontynuować tę dyskusję w czacie .

— Raphael

41

Istnieją dwa ustawienia, w których można uzyskać najgorsze przypadki . $O(1)$

Jeśli twoja konfiguracja jest statyczna, to mieszanie FKS zapewni najgorsze gwarancje . Ale jak wskazałeś, twoje ustawienie nie jest statyczne. $O(1)$
Jeśli używasz mieszania kukułki, wówczas zapytania i usunięcia są najgorszym przypadkiem , ale wstawienie oczekuje tylko . Mieszanie kukułki działa całkiem dobrze, jeśli masz górną granicę całkowitej liczby wstawek i ustawisz rozmiar stołu na około 25% większy. $O(1)$ $O(1)$

Jest więcej informacji tutaj .

— Suresh
źródło

3

Czy mógłbyś rozwinąć się w FKS i Kukułkę? Oba warunki są dla mnie nowe.

— Gilles,

1

Co z dynamicznym haszowaniem idealnym? Ma w najgorszym przypadku wyszukiwań i amortyzowane wkładanie i usuwanie. ( citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8165 )

O (1)

$O(1)$

O (1)

$O(1)$

— Joe

2

FKS to inicjały (Fredman, Komlós, Szemerédi), a kukułka to nazwa gatunku brid. Służy do tego rodzaju mieszania, ponieważ pisklęta kukułki wypychają jaja rodzeństwa z gniazda. To trochę przypomina działanie tej metody skrótu.

— uli

1

@Suresh: Naprawdę? Myślałem, że potrzebujesz niezależnych funkcji, które zawsze kojarzyły mi się z potrzebą ekspanderów. Poprawiono mnie. Za chwilę usunie mój komentarz.

\log n

$\log n$

— Louis

1

Aby dodać bardziej użyteczny komentarz do tej odpowiedzi, jak wskazuje @Suresh, haszowanie kukułki będzie działało dobrze bez fantazyjnych (i dużych) funkcji skrótu używanych do teoretycznej analizy.

— Louis

21

Ta odpowiedź zawiera podsumowanie części TAoCP tom 3, rozdział 6.4.

Załóżmy, że mamy zestaw wartości , których chcemy przechowywać w tablicy o rozmiarze . Używamy funkcji skrótu ; zazwyczaj . Nazywamy $V$ $n$ $A$ $m$ $h : V \to [0..M)$ $M \ll |V|$ owspółczynnik obciążeniao. Zakładamy tutaj naturalne; w praktycznych scenariuszach mamyi musimysamizmapować do. $\alpha = \frac{n}{m}$ $A$ $m=M$ $m \ll M$ $m$

Pierwszą obserwacją jest to, że nawet jeśli ma jednolite cechy¹, prawdopodobieństwo dwóch wartości mających tę samą wartość skrótu jest wysokie; jest to w zasadzie przykład niesławnego paradoksu urodzinowego . Dlatego zwykle będziemy musieli radzić sobie z konfliktami i możemy porzucić nadzieję na najgorszy czas dostępu do . $h$ $\mathcal{O}(1)$

A co z przeciętnym przypadkiem? Załóżmy, że każdy klucz z występuje z takim samym prawdopodobieństwem. Średnia liczba sprawdzonych wpisów (udane wyszukiwanie) lub. (nieudane wyszukiwanie) zależy od zastosowanej metody rozwiązywania konfliktów. $[0..M)$ $C_n^S$ $C_n^U$

Łańcuch

Każda pozycja tablicy zawiera (wskaźnik do początku) połączonych list. To dobry pomysł, ponieważ oczekiwana długość listy jest niewielka ( ) nawet jeśli prawdopodobieństwo kolizji jest wysokie. Ostatecznie otrzymujemy $\frac{n}{m}$ Można to nieco poprawić, przechowując listy (częściowo lub całkowicie) wewnątrz tabeli.

C_{n}^{S} \approx 1 + \frac{α}{2} and C_{n}^{U} \approx 1 + \frac{α^{2}}{2} .

$C_n^S \approx 1 + \frac{\alpha}{2} \quad \text{ and } \quad C_n^U \approx 1 + \frac{\alpha^2}{2} .$

Sondowanie liniowe

$v$

h (v), h (v) - 1, \dots, 0, m - 1, \dots, h (v) + 1

$h(v), h(v)-1,\dots,0,m-1,\dots,h(v)+1$

v

$v$

α \to 1

$\alpha \to 1$

C_{n}^{S} \approx \frac{1}{2} (1 + \frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{2} (1 + {(\frac{1}{1 - α})}^{2}) .

$C_n^S \approx \frac{1}{2}\left(1 +\frac{1}{1-\alpha}\right) \quad \text{ and } \quad C_n^U \approx \frac{1}{2}\left(1 +\left(\frac{1}{1-\alpha}\right)^2\right).$

α < 0.75

$\alpha < 0.75$

Podwójne mieszanie

$M$

C_{n}^{S} \approx \frac{1}{α} \ln (\frac{1}{1 - α}) and C_{n}^{U} \approx \frac{1}{1 - α} .

$C_n^S \approx \frac{1}{\alpha}\ln\left(\frac{1}{1-\alpha}\right)\quad \text{ and } \quad C_n^U \approx \frac{1}{1-\alpha} .$

Należy pamiętać, że usuwanie elementów i rozszerzanie tabel ma różne stopnie trudności dla poszczególnych metod.

$\mathcal{O}(1)$ $\alpha$ $h$

$h$
Hashtable

— Raphael
źródło

10

$S$ $\{0, 1, 2, ..., n\}$ $O(1)$ $O(1)$ $l$ $S$ $l$ $x$ $x \in S$ $O(|l|)$ $S$ $O(|S|)$ $O(|l| + |S|)$ $O(|l||S|)$ $O(\log(|l|)|S|)$ $O(|l|)$ $l$

$O(|l|)$

$l$ $U \subset \mathbb{N}$ $S \subseteq U$ $x \in S$ $l$ $l$ $h: U \rightarrow \{true, false\}$ $h$ $h(x) = false$ $x \in U$ $y$ $l$ $h(y) = true$ $O(|l|)$ $O(|U|)$

$l$ $O(|U|)$ $O(|1|)$ $O(|U|)$

$U$ $h$

— Patrick87
źródło

O (| l |)

$O(|l|)$

O (| S |)

$O(|S|)$

O (| l | \cdot | S |)

$O(|l|\cdot|S|)$

h

$h$

h : U \to {f a l s e, t r u e}

$h:U\to\{\mathrm{false},\mathrm{true}\}$

h

$h$

@Gilles Zasadniczo jest używany jako tabela odnośników do członkostwa na liście. Jeśli masz idealną funkcję skrótu ze znaną i tanią odwrotnością, zamiast przechowywać samą rzecz, musisz zapisać tylko 1 bit (niezależnie od tego, czy dodano rzecz z unikalnym hashem). Jeśli kolizje są możliwe, myślę, że robi się to nazywane filtrem Blooma, ale w każdym razie może stanowić zdecydowane „nie” w kwestii członkostwa, co jest nadal przydatne w wielu scenariuszach.

— Patrick87,

9

$\cal{O}(1)$

$\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$ $\cal{O}(1)$

— Nicholas Meyer
źródło

Idealna funkcja skrótu byłaby idealna, ale jak ją zdobyć? Ile będzie mnie to kosztować? A skąd mam wiedzieć, jaka jest maksymalna lub oczekiwana liczba kolizji?

— Gilles

2

@Gilles idealną funkcją skrótu jest każda funkcja, która wytworzy unikalny skrót dla wszystkich możliwych danych wejściowych. Jeśli twoje możliwe dane wejściowe są skończone (i unikalne), jest to łatwe do zrobienia.

— Rafe Kettler

1

@RafeKettler Moje dane wejściowe są zwykle łańcuchami lub złożonymi strukturami danych, i zazwyczaj dodaję i usuwam wpisy w miarę ewolucji moich danych. Jak zrobić dla tego idealny skrót?

— Gilles

4

Tak, ale o to chodzi. Deterministyczna idealna funkcja skrótu nie istnieje, jeśli domena jest większa niż zakres.

— Suresh,

@Suresh: Jeśli możesz wybrać nową funkcję skrótu i zwiększyć rozmiar tabeli za każdym razem, gdy dochodzi do kolizji, zawsze możesz znaleźć (deterministyczną) funkcję skrótu, która - dla danych już w tabeli plus jedna nowa element, który próbujesz wstawić - nie ma kolizji (jest „idealny”). Właśnie dlatego dynamiczne idealne mieszanie okresowo wybiera nową losową funkcję skrótu.

— David Cary,