Czym jest mapa hashowa w programowaniu i gdzie można ją wykorzystać
Często słyszałem ludzi mówiących o hashing i hash Mapy i tabele hash. Chciałem wiedzieć, co to jest i gdzie można je najlepiej wykorzystać.
4 answers
Najpierw powinieneś przeczytać ten Artykuł .
Kiedy używasz list i szukasz specjalnego elementu, zwykle musisz iterację nad pełną listą. Jest to bardzo drogie, gdy masz duże listy.
Hashtable może być znacznie szybszy, w najlepszych okolicznościach otrzymasz przedmiot, którego szukasz, z tylko jednym dostępem.
Jak to działa? Jak słownik ... gdy szukasz słowa "hashtable" w słowniku, nie zaczynasz od pierwsze słowo pod "a". Ale raczej idź prosto do litery "h". Potem do 'ha', 'ma' i tak dalej, aż znajdziesz swoje słowo. Używasz indeksu w słowniku, aby przyspieszyć wyszukiwanie.
Hashtable robi w zasadzie to samo. Każdy element otrzymuje unikalny indeks (tzw. hash). Używasz tego hasha do wyszukiwania. Hash może być indeksem na zwykłej liście połączonej. Na przykład twój hash może być liczbą taką jak 2130, co oznacza, że powinieneś spojrzeć na pozycję 2130 na liście. Wyszukiwanie w znanym indeksie na zwykłej liście jest bardzo łatwe i szybkie.
Problemem całego podejścia jest tzw. hash function, który przypisuje ten indeks każdemu elementowi. Jeśli szukasz przedmiotu, powinieneś być w stanie obliczyć indeks z wyprzedzeniem. Podobnie jak w prawdziwym słowniku, gdzie widzisz, że słowo 'hashtable' zaczyna się na literę 'h' i dlatego znasz przybliżoną pozycję.
Dobra funkcja hash zapewnia hashcodes, które są równomiernie rozłożone na przestrzeni wszystkie możliwe hashcodes. I oczywiście stara się unikać collisions. Kolizja ma miejsce, gdy dwa różne elementy otrzymują ten sam hashcode.
W C# na przykład każdy obiekt ma GetHashcode() metoda, która dostarcza do niej hash (niekoniecznie unikalny). Może to być używane do wyszukiwania i sortowania w słowniku.
Kiedy zaczynasz używać hashtabli, zawsze pamiętaj, że prawidłowo radzisz sobie z kolizjami. Może się to zdarzyć dość łatwo w dużych hashtablach, że dwa obiekty mam ten sam hash (może twoje przeciążenie GetHashcode () jest wadliwe, może stało się coś innego).
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-04-12 12:04:49
Zasadniczo, HashMap pozwala na przechowywanie elementów z identyfikatorami. Są one przechowywane w formacie tabeli, a identyfikator jest haszowany za pomocą algorytmu haszującego.
Zazwyczaj są one bardziej wydajne do pobierania przedmiotów niż wyszukiwania drzew itp.
Może Ci się to przydać: http://www.relisoft.com/book/lang/pointer/8hash.html
Hope it helps,
Chris
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
2010-04-07 11:43:49
Hashowanie (w sensie nonkryptograficznym) jest ogólnym terminem na pobranie danych wejściowych, a następnie wygenerowanie danych wyjściowych, aby je zidentyfikować. Trywialnym przykładem hasha jest dodanie sumy liter łańcucha, tj.:
f(abc) = 6
Zauważ, że ten trywialny schemat skrótu spowodowałby kolizję między łańcuchami abc, bca, AE itd. Efektywny schemat skrótu generowałby różne wartości dla każdego ciągu znaków, naturalnie.
Hashmapy i Hashtable są strukturami danych (jak tablice i listy), które używają hashowania do przechowywania danych. W tabeli hashtable tworzony jest skrót (albo z podanego klucza, albo z samego obiektu), który określa, gdzie w tabeli obiekt jest przechowywany. Oznacza to, że dopóki użytkownik hashtable jest świadomy klucza, pobieranie obiektu jest niezwykle szybkie.
W liście, w porównaniu, trzeba by w jakiś sposób przeszukiwać listę, aby znaleźć poszukiwany obiekt. To również stanowi zaplecze hashtables, czyli to, że znalezienie w nim obiektu bez znajomości klucza jest bardzo skomplikowane, ponieważ to, gdzie obiekt jest przechowywany w tabeli, nie ma znaczenia dla jego wartości, ani kiedy został wprowadzony.
Hashmapy są podobne do hashtabli, ale przechowywany jest w nich tylko jeden przykład każdego obiektu (stąd nie trzeba podawać klucza, sam obiekt jest kluczem).
Jest to oczywiście bardzo proste wyjaśnienie, więc sugeruję, abyś przeczytał dogłębnie od tego momentu. Mam nadzieję, że nie popełniłem głupich błędów. =)
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
2010-04-07 11:57:19
Hashmap jest używany do przechowywania danych w parach wartości klucza. Możemy użyć hashmap do przechowywania obiektów w aplikacji i używać go dalej w tej samej aplikacji do przechowywania, aktualizacji, usuwania wartości. Klucz Hashmap i wartości są przechowywane w zasobniku do określonego wpisu, lokalizacja tego wpisu jest określana za pomocą funkcji Hashcode. Ta funkcja hashcode określa hash, w którym przechowywana jest wartość. Szczegółowe wyjaśnienie działania hashmap jest opisane w tym filmie: https://youtu.be/iqYC1odZSNo
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-12-05 17:16:06