Czy tabele hash naprawdę mogą być O(1)?

Musisz obliczyć hash, więc kolejność jest O (n) dla rozmiaru wyszukiwanych danych. Wyszukiwanie może być O (1) po wykonaniu O (n) pracy, ale to nadal wychodzi na O (n) W Moich Oczach.

I jeśli nie masz idealnego hasha lub dużej tabeli hashów, prawdopodobnie na wiadrze znajduje się kilka pozycji, więc i tak w pewnym momencie przekształca się w małe wyszukiwanie liniowe.

Wymiana tabel hashowych to oczywiście złożoność przestrzeni. Zamieniasz przestrzeń na czas, co wydaje się być zwyczajnym przypadkiem w informatyce.

Wspominasz o używaniu łańcuchów jako kluczy w jednym z innych komentarzy. Martwisz się o ile czasu potrzeba, aby obliczyć hash łańcucha znaków, ponieważ składa się on z kilku znaków? Jak ktoś inny zauważył ponownie, nie musisz koniecznie patrzeć na wszystkie znaki, aby obliczyć hash, chociaż może to wytworzyć lepszy hash, jeśli to zrobiłeś. W takim przypadku, jeśli w Twoim kluczu są średnio m znaki i użyłeś ich wszystkich do obliczenia hasha, to przypuszczam, że masz rację, że wyszukiwanie zajmie O(m). Jeśli {[6] } to możesz mieć problem. Pewnie lepiej będzie z w takim razie BST. Lub wybierz tańszą funkcję mieszania.

Hash ma stały rozmiar - wyszukanie odpowiedniego zasobnika hash jest operacją o stałym koszcie. Oznacza to, że jest O (1).

Obliczanie skrótu nie musi być szczególnie kosztowną operacją - nie mówimy tu o kryptograficznych funkcjach skrótu. Ale to przy okazji. Sama funkcja skrótu nie zależy od liczby N elementów; chociaż może zależeć od wielkości danych w elemencie, nie jest to to, do czego odnosi się n. Tak więc obliczanie skrótu nie zależy od n i jest również O (1).

Hashowanie jest O(1) tylko wtedy, gdy w tabeli jest tylko stała liczba kluczy i przyjęto pewne inne założenia. Ale w takich przypadkach ma przewagę.

Jeśli twój klucz ma reprezentację n-bitową, twoja funkcja skrótu może użyć 1, 2, ... n tych bitów. Myślenie o funkcji hash, która wykorzystuje 1 bit. Ocena jest O (1) na pewno. Ale tylko dzielisz przestrzeń klucza na 2. Więc mapujesz aż 2 ^ (n-1) Klucze do tego samego kosza. korzystanie z wyszukiwania BST zajmuje do n-1 kroków aby zlokalizować określony klucz, jeśli jest prawie pełny.

Możesz to rozszerzyć, aby zobaczyć, że jeśli twoja funkcja hash używa bitów K, twój rozmiar bin wynosi 2^(n-k).

Więc K-bitowa funkcja hashowa ==> nie więcej niż 2^K efektywnych pojemników ==> do 2^(n-K) n-bitowe klucze na pojemnik ==> (N-K) kroki (BST) do rozwiązywania kolizji. W rzeczywistości większość funkcji hash jest znacznie mniej "efektywna" i potrzebuje / używa więcej niż bitów K do wytworzenia 2 ^ K bins. Więc nawet to jest optymistyczne.

Możesz to zobaczyć w ten sposób -- będziesz potrzebował ~n kroków, aby być w stanie jednoznacznie odróżnić parę kluczy N bitów w najgorszym przypadku. Tak naprawdę nie ma sposobu na obejście tego limitu teorii informacji, tabeli hash czy nie.

Jednak nie tak / Kiedy używasz tabeli hash!

Analiza złożoności zakłada, że dla n-bitowych kluczy, można mieć O (2^n) klucze w tabeli (np. 1/4 wszystkich możliwych kluczy). Ale większość, jeśli nie cały czas używamy tabeli hash, mamy tylko stałą liczbę n-bitowych kluczy w tabeli. If you only want a stała liczba kluczy w tabeli, powiedzmy, że C jest twoją maksymalną liczbą, wtedy możesz utworzyć tabelę haszującą o(C) bins, która gwarantuje oczekiwaną stałą kolizję (z dobrą funkcją haszującą); oraz funkcję haszującą używając ~logC n bitów w kluczu. Wtedy każde zapytanie jest O (logC) = O(1). W ten sposób ludzie twierdzą ,że"dostęp do tabel hash jest O(1)" /

Jest tu kilka haczyków-po pierwsze, mówienie, że nie potrzebujesz wszystkich bitów, może być tylko sztuczką rozliczeniową. Najpierw nie można przekazać wartości klucza do funkcji hash, bo to byłoby przeniesienie n bitów w pamięci, która jest O (n). Więc trzeba zrobić np. reference passing. Ale nadal musisz go gdzieś przechowywać, co było operacją O (n); po prostu nie przypisujesz go do hashowania; nie możesz tego uniknąć. Po drugie, robisz hashowanie, znajdujesz kosz i znajdujesz więcej niż 1 klucze; twój koszt zależy od metody rozdzielczości - jeśli wykonujesz porównanie na podstawie (BST lub List), będziesz miał operację O (N) (Przypomnij klucz jest n-bit); jeśli robisz 2nd hash, cóż, masz ten sam problem, jeśli 2nd hash ma kolizję. Tak więc O(1) nie jest w 100% gwarantowana, chyba że nie masz kolizji (możesz zwiększyć szansę, mając stół z większą ilością pojemników niż kluczy, ale nadal).

Rozważ alternatywę, np. BST, w tym przypadku. istnieją klucze C, więc Zbalansowany BST będzie o(logC) w głębi, więc wyszukiwanie trwa O (logC) kroki. Jednak porównanie w tym przypadku byłoby operacją O (n)... wygląda więc na to, że hashowanie jest lepszym wyborem w ta sprawa.

Wygląda na to, że jeśli X jest sufitem (#elementów w tabeli/# pojemników), to lepszą odpowiedzią jest o(log (X)) zakładając sprawną implementację bin lookup.

TL;DR: tabele Hash gwarantują O(1) oczekiwany najgorszy czas przypadku, jeśli wybierzesz swoją funkcję hash jednolicie losowo z uniwersalnej rodziny funkcji hash. Oczekiwany najgorszy przypadek nie jest taki sam jak przeciętny.

Zastrzeżenie: formalnie nie udowadniam, że tabele hashowe są O(1), za to spójrz na ten film z coursera [1]. Nie dyskutuję również oamortyzowanych aspektach tabel hashowych. To jest ortogonalne do dyskusji o hashowaniu i kolizje.

Widzę zaskakująco wiele zamieszania wokół tego tematu w innych odpowiedziach i komentarzach, i postaram się poprawić niektóre z nich w tej długiej odpowiedzi.

Rozumowanie o najgorszym przypadku

Istnieją różne rodzaje analizy najgorszego przypadku. Analiza, którą do tej pory przeprowadziła większość odpowiedzi nie jest najgorszym przypadkiem, ale raczej przeciętnym przypadkiem [2]. Przeciętny przypadek analiza wydaje się być bardziej praktyczna. Może twój algorytm ma jedno złe najgorsze wejście, ale faktycznie działa dobrze dla wszystkich innych możliwych wejść. Bottomline jest runtime zależy od zbioru danych , na którym pracujesz.

Rozważmy następujący pseudokod metody get tabeli hash. Zakładam, że zajmujemy się kolizją poprzez łańcuchowanie, więc każdy wpis tabeli jest połączoną listą (key,value) par. Zakładamy również, że liczba elementów m jest stała, ale jest O(n), gdzie n jest liczbą elementów w wejście.

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, przebiega to średnio O(1) i w najgorszym przypadku O(n). Możemy zrobić mały szkic dowodu przez wyzwanie tutaj. Wyzwanie wygląda następująco:

(1) przekazujesz swój algorytm tabeli hash przeciwnikowi.

(3) w końcu przeciwnik daje Ci Dane wejściowe o rozmiarze n, które możesz wstawić do swojej tabeli.

Pytanie brzmi: jak szybko jest Twój tabela hash na wejściu przeciwnika?

Z kroku (1) przeciwnik zna twoją funkcję haszującą; podczas kroku (2) przeciwnik może stworzyć listę n elementów z tym samym hash modulo m, np. losowo obliczając hash kilku elementów; a następnie w (3) mogą dać ci tę listę. Ale oto, ponieważ wszystkie n elementy hashują do tego samego wiadra, Twój algorytm zajmie O(n) czas, aby przejść przez połączoną listę w tym wiadrze. Bez względu na to, ile razy ponawiamy wyzwanie, przeciwnik zawsze wygrywa, i tak kiepski jest Twój algorytm, najgorszy przypadek O(n).

Dlaczego hashowanie jest O(1)?

To, co nas zniechęciło w poprzednim wyzwaniu, to fakt, że przeciwnik bardzo dobrze znał naszą funkcję haszującą i mógł wykorzystać tę wiedzę do stworzenia najgorszego możliwego wkładu. Co by było, gdyby zamiast zawsze używać jednej stałej funkcji skrótu, faktycznie mieliśmy zestaw funkcji skrótu H, z których algorytm może wybierać losowo w czasie wykonywania? Jeśli jesteś ciekawy, H nazywa się uniwersalna rodzina funkcji hashowych [3]. W porządku, spróbujmy dodać trochę losowości do tego.

Najpierw Załóżmy, że nasza tabela hash zawiera również ziarno r i r jest przypisana do liczby losowej w czasie budowy. Przypisujemy go raz, a następnie jest on naprawiony dla tej instancji tabeli hash. Teraz wróćmy 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 wyzwania jeszcze raz: z kroku (1) przeciwnik może poznać wszystkie funkcje hashowe, które mamy w H, Ale teraz konkretna funkcja hash, której używamy, zależy od r. Wartość r jest prywatna dla naszej struktury, przeciwnik nie może jej sprawdzić w czasie wykonywania, ani przewidzieć jej z wyprzedzeniem, więc nie może wymyślić listy, która zawsze jest dla nas zła. Załóżmy, że w Kroku (2) przeciwnik wybierze jedną funkcję hash W H losowo, następnie wykona listę kolizji n Pod hash modulo m i wyśle ją dla kroku (3), krzyżując palce, które w czasie wykonywania H[r] będą tymi samymi hash. wybrałem.

Jest to poważny zakład dla przeciwnika, lista, którą stworzył, zderza się pod hash, ale będzie po prostu losowym wejściem pod dowolną inną funkcją hashową w H. Jeśli wygra ten zakład, nasz czas trwania będzie najgorszy O(n), jak wcześniej, ale jeśli przegra, wtedy otrzymamy losowe wejście, które zajmuje średni czas O(1). I rzeczywiście, w większości przypadków przeciwnik przegrywa, wygrywa tylko raz w każdym wyzwaniu, a my możemy sprawić, że będą bardzo duże.

Kontrast wynik ten do poprzedniego algorytmu, w którym przeciwnik zawsze wygrywał wyzwanie. Trochę tu Oszczędzania rąk, ale ponieważw większości przypadków przeciwnik poniesie porażkę i dotyczy to wszystkich możliwych strategii, które przeciwnik może wypróbować, wynika z tego, że chociaż najgorszy przypadek jest O(n), oczekiwany najgorszy przypadek jest w rzeczywistości O(1).

Istnieją dwa ustawienia, pod którymi można uzyskać o (1) najgorsze czasy.

1. Jeśli Twoja konfiguracja jest statyczna, to hashowanie FKS da ci najgorszą gwarancję O (1) . Ale jak już wspomniałeś, Twoje ustawienie nie jest statyczne.
2. Jeśli używasz Cuckoo hashing, To zapytania i DELETE są O (1) w najgorszym przypadku, ale wstawianie jest tylko o(1) oczekiwane. Haszowanie kukułki działa całkiem dobrze, jeśli masz górną granicę całkowitej liczby wstawek i ustaw tabelę Rozmiar Około 25% większy.

Skopiowane z tutaj

A. Wartość int jest mniejsza niż wielkość tabeli hash. Dlatego wartość jest własnym hash, więc nie ma tabeli hash. Ale gdyby tak było, byłoby O(1) i nadal byłoby nieefektywne.

Jest to przypadek, w którym można trywialnie odwzorować klucze na różne wiadra, więc tablica wydaje się lepszym wyborem struktury danych niż tabela hash. Mimo to nieefektywność nie rośnie wraz z rozmiarem tabeli.

(możesz nadal używać tabeli hash, ponieważ nie ufasz ints, aby pozostać mniejsze niż rozmiar tabeli w miarę rozwoju programu, chcesz, aby Kod mógł być potencjalnie wielokrotnego użytku, gdy ta relacja nie utrzymuje się, lub po prostu nie chcesz, aby ludzie czytający / utrzymujący kod musieli marnować wysiłek umysłowy zrozumienie i utrzymanie relacji).

B. musisz obliczyć hash wartości. W tej sytuacji kolejność jest O (n) dla wielkości wyszukiwanych danych. Wyszukiwanie może być O (1) po wykonaniu O (n) pracy, ale to wciąż wychodzi mi O (n) w oczach.

Musimy rozróżnić rozmiar klucza (np. w bajtach), a rozmiar liczby kluczy przechowywanych w tabeli hash. Twierdzenia, że tabele hash zawierają operacje O(1) oznaczają, że operacje (insert/erase/find) nie zwalniają dalszego tempa wraz ze wzrostem liczby klawiszy od setek do tysięcy do milionów do miliardów (przynajmniej nie jeśli wszystkie dane są dostępne/aktualizowane w równie szybkim magazynie, być że RAM lub efekty pamięci podręcznej dysku mogą wchodzić w grę, ale nawet koszt najgorszego przypadku miss pamięci podręcznej wydaje się być jakąś stałą wielokrotnością najlepszego przypadku hit).

Rozważ książkę telefoniczną: możesz mieć tam imiona, które są dość długie, ale niezależnie od tego, czy książka ma 100 imion, czy 10 milionów, średnia długość nazwy będzie dość spójna, i najgorszy przypadek w historii...

Rekord Guinnessa na najdłuższą nazwę używaną przez kogokolwiek został ustanowiony przez Adolpha Blaine ' a Charlesa David Earl Frederick Gerald Hubert Irvin John Kenneth Lloyd Martin Nero Oliver Paul Quincy Randolph Sherman Thomas Uncas Victor William Xerxes Yancy Wolfeschlegelsteinhausenbergerdorff, Senior {]}

...wc mówi mi, że to 215 znaków - to nie jest twardy górny-związany z długością klucza, ale nie musimy się martwić, że będzie masowo więcej.

To dotyczy większości tabel hash w świecie rzeczywistym: średnia długość klucza nie rośnie wraz z liczba używanych kluczy. Istnieją wyjątki, na przykład procedura tworzenia klucza może zwracać ciągi zawierające inkrementujące liczby całkowite, ale nawet wtedy za każdym razem, gdy zwiększasz liczbę kluczy o rząd wielkości, zwiększasz długość klucza tylko o 1 znak: nie jest to istotne.

Możliwe jest również utworzenie hasha z ilości kluczowych danych o stałym rozmiarze. Na przykład, Visual C++ firmy Microsoft jest dostarczany ze standardową implementacją biblioteki std::hash<std::string>, która tworzy hash zawierający tylko dziesięć bajtów równomiernie rozmieszczonych wzdłuż łańcucha, więc jeśli łańcuchy różnią się tylko w innych indeksach, otrzymujemy kolizje(a więc w praktyce zachowania inne niż o (1) po stronie wyszukiwania po kolizji), ale czas na utworzenie hasha ma twardą górną granicę.

I jeśli nie masz idealnego hasha lub dużej tabeli hash, prawdopodobnie jest kilka elementów na wiadrze. W pewnym momencie i tak przechodzi w małe, liniowe poszukiwania.

Ogólnie prawda, ale zajebista rzecz o tabele hash polega na tym, że liczba kluczy odwiedzanych podczas tych "małych wyszukiwań liniowych" jest - dla podejścia separate chaining do kolizji - funkcją tabeli hash współczynnik obciążenia (stosunek kluczy do wiader).

Na przykład, przy współczynniku obciążenia 1.0 średnia długość tych wyszukiwań liniowych wynosi ~1.58, niezależnie od liczby kluczy (zobacz moja odpowiedź tutaj). Na zamknięte hashowanie to trochę więcej skomplikowane, ale niewiele gorsze, gdy współczynnik obciążenia nie jest zbyt wysoki.

Jest to technicznie prawdziwe, ponieważ funkcja hash nie jest wymagana, aby używać wszystkich informacji w kluczu, a więc może być stały czas, a ponieważ wystarczająco duża tabela może doprowadzić kolizje do prawie stałego czasu.

Ten rodzaj nie trafia w sedno. Każdy rodzaj asocjacyjnej struktury danych musi czasem wykonywać operacje na każdej części klucza (nierówność może być określona tylko z części klucza, ale równość generalnie wymaga uwzględnienia każdego bitu). Co najmniej może on raz hashować klucz i przechowywać jego wartość, a jeśli użyje wystarczająco silnej funkcji hash - np. 64-bitowego MD5 - może praktycznie zignorować nawet możliwość skrócenia dwóch kluczy do tej samej wartości (firma, dla której pracowałem, zrobiła dokładnie to dla rozproszonej bazy danych: Czas generowania hash był nadal nieznaczny w porównaniu do transmisji w sieci WAN). Więc nie ma zbyt dużo uwagi na temat kosztów przetwarzania klucza: jest to nieodłączne w przechowywaniu kluczy niezależnie od struktury danych, a jak wspomniano powyżej - nie ma tendencji do pogorszenia się średnio przy większej liczbie kluczy.

Jeśli chodzi o wystarczająco duże tabele hashowe, które sprowadzają kolizje w dół, to też o to chodzi. W przypadku oddzielnego łączenia łańcuchów nadal masz stałą średnią długość łańcucha kolizji przy danym współczynniku obciążenia - jest ona po prostu wyższa, gdy współczynnik obciążenia jest wyższy, a zależność ta wynosi nieliniowa. Tak użytkownik Hans komentuje moja odpowiedź również linkowała wyżej że:

[[4]}Średnia Długość łyżki uwarunkowana łyżkami nieregulowanymi jest lepszą miarą wydajności. Jest to a / (1-e^{-a}) [gdzie a jest współczynnikiem obciążenia, e jest 2.71828...]

Tak więc, sam współczynnik obciążenia określa średnią liczbę kolidujących kluczy, które musisz przeszukiwać podczas operacji wstawiania/kasowania/znajdowania. Dla oddzielnego łączenia, nie tylko zbliża się do bycia stałym, gdy współczynnik obciążenia jest niski-to zawsze stała. W przypadku adresowania otwartego Twoje roszczenie ma pewną Ważność: niektóre kolidujące elementy są przekierowywane do alternatywnych łyżek i mogą następnie zakłócać operacje na innych kluczach, więc przy wyższych współczynnikach obciążenia (zwłaszcza > .8 lub .9) Długość łańcucha kolizji znacznie się pogarsza.

Jest to prawda w praktyce, ponieważ z czasem działa tak długo, jak długo funkcja hash i rozmiar tabeli są dobierane w celu zminimalizowania kolizji, mimo że często oznacza to nie Używanie funkcji skrótu o stałym czasie.

Cóż, rozmiar tabeli powinien skutkować rozsądnym współczynnikiem obciążenia biorąc pod uwagę wybór close hashing lub oddzielnego łańcucha, ale także jeśli funkcja hash jest nieco słaba i klucze nie są bardzo losowe, posiadanie pierwszej liczby łyżek często pomaga zmniejszyć kolizje zbyt (hash-value % table-size następnie owija się tak, że zmiany tylko na bit lub dwa wysokiego rzędu w wartości hash nadal rozwiązać wiadra rozłożone pseudo-losowo na różne części tabeli hash).