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

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)$$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)?

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

1. Jeśli twoja konfiguracja jest statyczna, to mieszanie FKS zapewni najgorsze gwarancje . Ale jak wskazałeś, twoje ustawienie nie jest statyczne.$O(1)$

2. 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)$$O(1)$

Jest więcej informacji tutaj .

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

Załóżmy, że mamy zestaw wartości , których n chcemy przechowywać w tablicy A o rozmiarze m . Używamy funkcji skrótu h : V → [ 0 .. M ) ; zazwyczaj M ≪ | V | . Nazywamy α = $V$$n$$A$$m$$h : V \to [0..M)$$M \ll |V|$ owspółczynnik obciążeniaoA. Zakładamy tutaj naturalnem=M; w praktycznych scenariuszach mamym≪Mi musimysamizmapować dom.$\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 O ( 1 ) .$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 C S n (udane wyszukiwanie) lub. C U n (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 C S n ≈1+$\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{\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$$ $v$$\alpha \to 1$ $$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).$$ $\alpha < 0.75$

Podwójne mieszanie

$M$

$$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

$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$

$\cal{O}(1)$

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