Dlaczego hashmap lookup to O (1), czyli stały czas?

Question

Dlaczego hashmap lookup to O (1), czyli stały czas?

Jeśli spojrzymy z perspektywy Javy, możemy powiedzieć, że wyszukiwanie hashmap trwa cały czas. Ale co z wewnętrzną implementacją? Nadal musiałoby przeszukiwać konkretne wiadro (dla którego klucza pasował hashcode) w poszukiwaniu różnych pasujących kluczy.Dlaczego więc mówimy, że wyszukiwanie hashmap trwa cały czas? Proszę wyjaśnić.

21

big-o hashmap hashtable data-structures hash

Author: templatetypedef, 2013-03-18

Source

3 answers

Klucz znajduje się w tej instrukcji w dokumentach:

Jeśli wiele mapowań ma być przechowywanych w instancji HashMap, utworzenie jej o wystarczająco dużej pojemności pozwoli na przechowywanie mapowań bardziej wydajnie niż pozwala na automatyczne ponowne rozmycie w razie potrzeby, aby powiększyć tabelę.

I

Współczynnik obciążenia jest miarą tego, jak pełna jest tabela hash, zanim jej pojemność zostanie automatycznie zwiększona. Gdy liczba wpisów w tabela haszująca przekracza iloczyn współczynnika obciążenia i aktualnej pojemności, tabela haszująca jest przebudowywana (czyli przebudowywane są wewnętrzne struktury danych) tak, że tabela haszująca ma około dwukrotnie większą liczbę łyżek.

Http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html

Wewnętrzna struktura łyżki zostanie faktycznie przebudowana, jeśli współczynnik obciążenia zostanie przekroczony, co pozwoli na amortyzowany koszt z get i put {[18] } to be O(1).

Zauważ, że jeśli struktura wewnętrzna jest przebudowana, to wprowadza karę wydajności, która prawdopodobnie wynosi O(N), więc sporo get i put może być wymagane, zanim zamortyzowany koszt zbliży się ponownie do O (1). Z tego powodu odpowiednio zaplanuj początkową pojemność i współczynnik obciążenia, aby nie marnować miejsca, ani nie wywołać możliwej do uniknięcia przebudowy struktury wewnętrznej.

7

Author: Eric J.,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-03-18 04:37:14

Aby śledzić komentarze templatetypedef również:

Implementacją tabeli hash może być hashmap, za pomocą której można zaimplementować listę tablic logicznych, która wskazuje, czy dany element istnieje w bucket. Jeśli jednak implementujesz połączoną listę dla swojej hashmapy, najgorszy przypadek wymagałby przejrzenia każdego wiadra i przejścia przez końce list.

0

Author: jim-zed-li,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-11-16 20:54:19

score 26 · Accepted Answer

Zgodnie z odpowiednimi założeniami dotyczącymi używanej funkcji hash, możemy powiedzieć, że wyszukiwanie tabeli hash zajmuje oczekiwany o(1) czas. Oznacza to, że średnio ilość pracy wykonywanej przez tabelę hash w celu przeprowadzenia wyszukiwania jest co najwyżej pewną stałą.

Intuicyjnie, jeśli masz "dobrą" funkcję skrótu, spodziewasz się, że elementy będą mniej lub bardziej równomiernie rozłożone w tabeli skrótów, co oznacza, że liczba elementów w każdym zasobniku będzie bliska liczba elementów podzielona przez liczbę wiader. Jeśli implementacja tabeli hash utrzymuje tę liczbę na niskim poziomie (np. dodając więcej łyżek za każdym razem, gdy stosunek elementów do łyżek przekracza pewną stałą), to Oczekiwana ilość pracy, która zostanie wykonana, kończy się pewną ilością pracy bazowej, aby wybrać, które łyżki mają być skanowane, a następnie robi "nie za dużo" pracy patrząc na elementy tam, ponieważ na oczekiwanie będzie tylko stała liczba elementów w tym zestawie. wiadro.

Nie oznacza to, że tabele hash mają zagwarantowane o(1) zachowanie. W rzeczywistości, w najgorszym przypadku, schemat mieszania ulegnie degeneracji, a wszystkie elementy trafią do jednego wiadra, co sprawi, że wyszukiwanie zajmie Czas Θ (n) w najgorszym przypadku. Dlatego ważne jest, aby zaprojektować dobre funkcje skrótu.

Aby uzyskać więcej informacji, warto przeczytać podręcznik algorytmów, aby dowiedzieć się, dlaczego tabele hash tak efektywnie wspierają wyszukiwanie. Jest to zwykle zawarte jako część typowego kursu uniwersyteckiego na temat algorytmów i struktur danych, a w Internecie jest wiele dobrych zasobów.

Mam nadzieję, że to pomoże!