Złożoność runtime tabeli Hash (wstawianie, wyszukiwanie i usuwanie)

Idealnie, hashtable to O(1). Problem polega na tym, że dwa klucze nie są sobie równe, jednak powodują ten sam hash.

Na przykład, wyobraź sobie ciągi "to był najlepszy czas, to był najgorszy czas" i "zielone jajka i szynka" oba dały wartość skrótu 123.

Po włożeniu pierwszego Sznurka wkłada się go do wiadra 123. Gdy drugi łańcuch jest wstawiany, zobaczy, że wartość dla bucket 123 już istnieje. Następnie porównałby nowe wartość do istniejącej wartości, i zobaczyć, że nie są równe. W takim przypadku dla tego klucza zostanie utworzona tablica lub lista powiązana. W tym momencie pobranie tej wartości staje się O(n), ponieważ hashtable musi przejrzeć każdą wartość w tym wiadrze, aby znaleźć żądaną.

Z tego powodu, podczas korzystania z tabeli skrótów, ważne jest, aby użyć klucza z naprawdę dobrą funkcją skrótu, która jest zarówno Szybka, jak i często nie powoduje powielania wartości dla różnych obiektów.

Ma sens?

Niektóre tabele hash (} mają zagwarantowane o (1) lookup

Zależy od tego, jak zaimplementujesz hashowanie, w najgorszym przypadku może przejść do O(n), w najlepszym przypadku jest to 0(1) (ogólnie można osiągnąć, jeśli twój DS nie jest tak duży łatwo)

Być może patrzyłeś na złożoność przestrzeni? To jest O (n). Pozostałe zawiłości są zgodne z oczekiwaniami w tabeli hash . Złożoność wyszukiwania zbliża się do O (1) wraz ze wzrostem liczby kubełków. Jeśli w najgorszym przypadku masz tylko jedno wiadro w tabeli hash, to złożoność wyszukiwania wynosi O (n).

Edit w odpowiedzi na komentarz nie wydaje mi się, aby słuszne było stwierdzenie O(1) to Przeciętny przypadek. Naprawdę jest (jak mówi strona Wikipedii) O (1+n/k) gdzie k jest wielkość tabeli hash. Jeśli K jest wystarczająco duże, to wynikiem jest efektywnie O(1). Ale załóżmy, że K jest 10, A N jest 100. W takim przypadku każde wiadro będzie miało średnio 10 wpisów, więc czas wyszukiwania zdecydowanie nie wynosi O(1); jest to wyszukiwanie liniowe do 10 wpisów.