W jaki sposób hashowanie ma czas Wyszukiwania o(1)? [duplikat]

Cóż to jest trochę trochę kłamstwa -- to może trwać dłużej, ale zazwyczaj nie.

W zasadzie tabela hash jest tablicą zawierającą wszystkie klucze do wyszukiwania. Pozycja każdego klawisza w tablicy jest określona przez funkcję skrótu , która może być dowolną funkcją, która zawsze mapuje to samo wejście na to samo wyjście. Przyjmiemy, że funkcja hash jest O (1).

Więc kiedy wstawiamy coś do tabeli hash, używamy funkcji hash (niech nazwij to h ), aby znaleźć miejsce, w którym go umieścić, i umieścić go tam. Teraz wstawiamy inną rzecz, hashowanie i przechowywanie. I jeszcze jeden. Za każdym razem, gdy wstawiamy dane, wstawianie ich zajmuje o(1) czas (ponieważ funkcja hash to O(1).

Wyszukiwanie danych jest takie samo. Jeśli chcemy znaleźć wartość x , musimy tylko znaleźć h (x), która mówi nam, gdzie x znajduje się w tabeli hash. Możemy więc również sprawdzić dowolną wartość hash w O(1).

Teraz do kłamstwa: The powyżej jest bardzo ładna teoria z jednym problemem: co jeśli wstawimy Dane i już coś jest w tej pozycji tablicy? Nie ma nic, co gwarantowałoby, że funkcja hash nie wytworzy tego samego wyjścia dla dwóch różnych wejść (chyba że masz idealną funkcję hash , ale są one trudne do wytworzenia). Dlatego, gdy wstawiamy musimy przyjąć jedną z dwóch strategii:

• przechowuje wiele wartości w każdym miejscu tablicy (powiedzmy, że każdy slot tablicy ma połączony lista). Teraz, gdy wykonujesz wyszukiwanie, nadal jest O (1), Aby Dotrzeć do właściwego miejsca w tablicy, ale potencjalnie liniowe wyszukiwanie w dół (miejmy nadzieję, krótką) połączoną listę. Nazywa się to "oddzielnym łańcuchem".
• Jeśli znajdziesz coś już tam jest, hash ponownie i znaleźć inne miejsce. Powtarzaj, aż znajdziesz puste miejsce i umieść je tam. Procedura wyszukiwania może postępować zgodnie z tymi samymi zasadami, aby znaleźć dane. Teraz jest jeszcze O (1), aby dostać się do pierwszej lokalizacji, ale jest potencjalnie (miejmy nadzieję krótkie) wyszukiwanie liniowe, aby odbijać się wokół stołu, aż znajdziesz DANE, których szukasz. Nazywa się to"otwartą adresacją".

Zasadniczo oba podejścia są nadal głównie O(1), ale z miejmy nadzieję krótkim ciągiem liniowym. Możemy założyć dla większości celów, że jest to O (1). Jeśli tabela hash staje się zbyt pełna, te liniowe wyszukiwania mogą się wydłużyć i wydłużyć, a następnie nadszedł czas na "ponowne hashowanie", co oznacza utworzenie nowej tabeli hash o znacznie większym rozmiarze i wstawienie wszystkich danych z powrotem.