Złożoność środowiska wykonawczego tabeli haszów (wstawianie, wyszukiwanie i usuwanie)

Question

Dlaczego nadal widzę różne komplikacje środowiska wykonawczego dla tych funkcji na tabeli mieszania?

Na wiki, wyszukiwanie i usuwanie to O (n) (Myślałem, że punkt tabel hash ma mieć stałe wyszukiwanie, więc jaki jest sens, jeśli wyszukiwanie to O (n)).

W niektórych notatkach z kursu widziałem od dawna szeroki zakres zawiłości w zależności od pewnych szczegółów, w tym jednego z wszystkimi O (1). Dlaczego miałbym użyć jakiejkolwiek innej implementacji, jeśli mogę uzyskać wszystkie O (1)?

Jeśli używam standardowych tabel mieszania w języku takim jak C++ lub Java, co mogę spodziewać się złożoności czasu?

Answer 1

Hash tables są O(1)średnie i amortized złożoność sprawy, to jednak cierpi z O(n)najgorszym przypadku czasu złożoności.[I myślę, że to jest, gdy zamieszanie jest]

tabele Hash cierpią O(n) najgorszy czas złożoności z dwóch powodów:

1. Jeśli zbyt wiele elementów zostało przerywanych na ten sam klucz: patrząc wewnątrz tego klucza może weź czas O(n).
2. Po przejściu tabeli mieszania load balance - należy ponownie utworzyć [utworzyć nową większą tabelę i ponownie wstawić każdy element do tabeli].

jednak mówi się O(1) średni i amortyzowane przypadek, ponieważ:

1. Jest bardzo rzadki, że wiele elementów, które zostaną zakodowane na tym samym klawiszu [jeśli wybraliśmy dobrą funkcji skrótu i nie mają zbyt dużego balansu obciążenia.
2. Operacja mikstura, która jest O(n), może co najwyżej zdarzyć po n/2 OPS, które są Zakłada O(1): Tak, jeśli zsumować średni czas na op dostaniesz: (n*O(1) + O(n))/n) = O(1)

Uwaga powodu uporczywie powtarzanym issue - aplikacje i aplikacje działające w czasie rzeczywistym, które potrzebują niskiej wartości latency - nie powinny używać tabeli skrótów jako struktury danych.

EDIT: Annother problem z tabelami hash: cache
Inną kwestią, w której można zobaczyć straty wydajności w dużych tablic hash ze względu na wydajność pamięci podręcznej. Tabele haszów mają słabą wydajność pamięci podręcznej, a tym samym w przypadku dużej kolekcji - czas dostępu może trwać dłużej, ponieważ trzeba ponownie załadować odpowiednią część tabeli z pamięci z powrotem do pamięci podręcznej.

Answer 2

Zależy od sposobu wdrożenia hashowania, w najgorszym przypadku może przejść do O (n), w najlepszym przypadku jest to 0 (1) (zazwyczaj można to osiągnąć, jeśli twoje DS nie jest zbyt duże)

Answer 3

Być może patrzyłeś na złożoność przestrzeni? To jest O (n). Inne złożoności są zgodne z oczekiwaniami na wejściu hash table. Złożoność wyszukiwania zbliża się do O (1) w miarę wzrostu liczby kubełków. Jeśli w najgorszym przypadku w tabeli mieszającej znajduje się tylko jedno wiadro, złożoność wyszukiwania to O (n).

Edytuj w odpowiedzi na komentarz Nie sądzę, że prawidłowe jest stwierdzenie, że O (1) to przeciętny przypadek. Naprawdę jest (jak mówi strona wikipedia) O (1 + n/k) gdzie K jest rozmiarem tabeli mieszania. Jeśli K jest wystarczająco duże, wówczas wynikiem jest efektywnie O (1). Załóżmy jednak, że K wynosi 10, a N to 100. W takim przypadku każdy z nich będzie miał średnio 10 wpisów, więc czas wyszukiwania zdecydowanie nie jest równy O (1); jest to liniowe wyszukiwanie do 10 pozycji.

Answer 4

Idealnie hashtable to O(1). Problem polega na tym, że dwa klucze nie są równe, ale skutkują tym samym hashem.

Na przykład, wyobraźmy sobie struny „To było najlepsze czasy to był najgorszy od czasów” i „Zielone Jajka i Szynka” zarówno dała wartość hash 123.

Po wstawieniu pierwszego ciągu jest on wstawiany do wiadra 123. Po wstawieniu drugiego ciągu zobaczy on, że dla wiadra 123 istnieje już wartość. Następnie porównuje nową wartość z istniejącą wartością i zobaczy, że nie są one równe. W tym przypadku dla tego klucza tworzona jest tablica lub lista połączona. W tym momencie odzyskiwanie tej wartości staje się O(n), ponieważ obiekt hashtable musi iterować każdą wartość w tym segmencie, aby znaleźć żądaną wartość.

Z tego powodu przy korzystaniu z tabeli mieszania ważne jest użycie klucza o naprawdę dobrej funkcji skrótu, która jest szybka i często nie powoduje duplikacji wartości dla różnych obiektów.

Sens?

Answer 5

Niektóre tabele hash (kukułka mieszania) mają zagwarantowane O (1) Lookup