(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 ( ).Θ(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)?

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)
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)
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(logn)
isturdy

Odpowiedzi:

41

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 .

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)
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. logn
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 n chcemy przechowywać w tablicy A o rozmiarze m . Używamy funkcji skrótu h : V [ 0 .. M ) ; zazwyczaj M | V | . Nazywamy α = nVnAmh:V[0..M)M|V| owspółczynnik obciążeniaoA. Zakładamy tutaj naturalnem=M; w praktycznych scenariuszach mamymMi musimysamizmapować dom.α=nmAm=MmMm

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 ) .hO(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)CnSCnU

Ł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 n1+αnm Można to nieco poprawić, przechowując listy (częściowo lub całkowicie) wewnątrz tabeli.

CnS1+α2 and CnU1+α22.

Sondowanie liniowe

v

h(v),h(v)1,,0,m1,,h(v)+1
vα1
CnS12(1+11α) and CnU12(1+(11α)2).
α<0.75

Podwójne mieszanie

M

CnS1αln(11α) and CnU11α.

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

O(1)αh


h
Hashtable

Raphael
źródło
10

S{0,1,2,...,n}O(1)O(1)lSlxxSO(|l|)SO(|S|)O(|l|+|S|)O(|l||S|)O(log(|l|)|S|)O(|l|)l

O(|l|)

lUNSUxSllh:U{true,false}hh(x)=falsexUylh(y)=trueO(|l|)O(|U|)

lO(|U|)O(|1|)O(|U|)

Uh

Patrick87
źródło
O(|l|)O(|S|)O(|l||S|)
hh:U{false,true}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

O(1)

O(1)O(1)O(1)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,