TL; DR: Tabele skrótu gwarantują O(1)oczekiwany najgorszy czas, jeśli wybierzesz funkcję skrótu równomiernie losowo z uniwersalnej rodziny funkcji skrótu. Oczekiwany najgorszy przypadek nie jest tym samym, co przeciętny przypadek.
Uwaga: formalnie nie udowadniam O(1), że tablice skrótów są , dlatego spójrz na ten film wideo z coursera [ 1 ]. Nie omawiam też amortyzowanych aspektów tabel skrótów. To jest ortogonalne w stosunku do dyskusji o haszowaniu i kolizjach.
Widzę zaskakująco duże zamieszanie wokół tego tematu w innych odpowiedziach i komentarzach i spróbuję poprawić niektóre z nich w tej długiej odpowiedzi.
Rozumowanie o najgorszym przypadku
Istnieją różne rodzaje analizy najgorszego przypadku. Analiza, której dotychczas dokonała większość odpowiedzi, nie jest przypadkiem najgorszym, ale raczej przeciętnym [ 2 ]. Analiza przeciętnego przypadku jest bardziej praktyczna. Może twój algorytm ma jeden zły, najgorszy przypadek, ale w rzeczywistości działa dobrze dla wszystkich innych możliwych danych wejściowych. Najważniejsze jest to, że czas działania zależy od zestawu danych , z którego korzystasz.
Rozważmy następujący pseudokod getmetody tablicy skrótów. Tutaj zakładam, że kolizję rozwiązujemy przez łańcuchowanie, więc każdy wpis w tabeli jest połączoną listą (key,value)par. Zakładamy również, że liczba segmentów mjest stała, ale jest O(n), gdzie njest liczbą elementów w danych wejściowych.
function get(a: Table with m buckets, k: Key being looked up)
bucket <- compute hash(k) modulo m
for each (key,value) in a[bucket]
return value if k == key
return not_found
Jak wskazywały inne odpowiedzi, jest to przeciętne O(1)i najgorsze O(n). Możemy tutaj zrobić mały szkic dowodu poprzez wyzwanie. Wyzwanie wygląda następująco:
(1) Przekazujesz swój algorytm tablicy mieszającej przeciwnikowi.
(2) Przeciwnik może go przestudiować i przygotować tak długo, jak chce.
(3) W końcu przeciwnik podaje wielkość, nktórą należy wstawić do tabeli.
Pytanie brzmi: jak szybko twoja tablica mieszania jest na wejściu przeciwnika?
Od kroku (1) przeciwnik zna twoją funkcję skrótu; podczas kroku (2) przeciwnik może stworzyć listę nelementów z tym samym hash modulo m, np. przez losowe obliczenie skrótu zbioru elementów; a następnie w (3) mogą dać ci tę listę. Ale spójrzcie, ponieważ wszystkie nelementy są mieszane do tego samego zasobnika, algorytm potrzebuje O(n)czasu, aby przejść przez połączoną listę w tym zasobniku. Bez względu na to, ile razy podejmiemy wyzwanie, przeciwnik zawsze wygrywa i tak zły jest twój algorytm, w najgorszym przypadku O(n).
Dlaczego haszowanie jest O (1)?
Tym, co nas zrzuciło w poprzednim wyzwaniu, było to, że przeciwnik bardzo dobrze znał naszą funkcję skrótu i mógł wykorzystać tę wiedzę do stworzenia jak najgorszego wkładu. A co by było, gdybyśmy zamiast zawsze używać jednej ustalonej funkcji skrótu, mielibyśmy zestaw funkcji skrótu H, z których algorytm może wybierać losowo w czasie wykonywania? Jeśli jesteś ciekawy, Hnazywa się uniwersalną rodziną funkcji skrótu [ 3 ]. W porządku, spróbujmy dodać do tego trochę przypadkowości .
Najpierw załóżmy, że nasza tabela skrótów zawiera również ziarno ri rjest przypisana do liczby losowej w czasie budowy. Przypisujemy go raz, a następnie jest to naprawione dla tej instancji tablicy skrótów. Wróćmy teraz do naszego pseudokodu.
function get(a: Table with m buckets and seed r, k: Key being looked up)
rHash <- H[r]
bucket <- compute rHash(k) modulo m
for each (key,value) in a[bucket]
return value if k == key
return not_found
Jeśli spróbujemy jeszcze raz: od kroku (1) przeciwnik może poznać wszystkie funkcje skrótu, w których mamy H, ale teraz zależy od konkretnej funkcji skrótu, której używamy r. Wartość rjest prywatna dla naszej struktury, przeciwnik nie może jej sprawdzić w czasie wykonywania ani przewidzieć z wyprzedzeniem, więc nie może ułożyć listy, która zawsze jest dla nas szkodliwa. Załóżmy, że w etapie (2) przeciwnik wybiera jedną funkcję hashw Hlosowo, potem rzemiosła listę nkolizji wynikających hash modulo mi wysyła je do kroku (3), przejście palce, że przy starcie H[r]będzie taki sam hashwybrali.
To poważny zakład dla przeciwnika, lista, którą stworzył, koliduje z nią hash, ale będzie po prostu losowym wpisem w dowolnej innej funkcji skrótu H. Jeśli wygra ten zakład, nasz czas pracy będzie najgorszy, tak O(n)jak poprzednio, ale jeśli przegra, to cóż, otrzymujemy losowe dane wejściowe, które zajmują średni O(1)czas. I rzeczywiście, w większości przypadków przeciwnik przegrywa, wygrywa tylko raz w każdym |H|wyzwaniu, a my możemy zrobić |H|bardzo duże.
Porównaj ten wynik z poprzednim algorytmem, w którym przeciwnik zawsze wygrywał wyzwanie. Trochę tu macham ręką, ale ponieważ w większości przypadków przeciwnik zawiedzie, a dotyczy to wszystkich możliwych strategii, jakie przeciwnik może wypróbować, wynika z tego, że chociaż jest O(n)to najgorszy przypadek, w rzeczywistości jest to oczekiwany najgorszyO(1) .
Ponownie, nie jest to formalny dowód. Gwarancją, jaką otrzymujemy z tej oczekiwanej analizy najgorszego przypadku, jest to, że nasz czas wykonywania jest teraz niezależny od jakichkolwiek konkretnych danych wejściowych . Jest to prawdziwie przypadkowa gwarancja, w przeciwieństwie do przeciętnej analizy przypadku, w której wykazaliśmy, że zmotywowany przeciwnik może łatwo stworzyć złe dane wejściowe.