Co to jest mapa skrótów w programowaniu i gdzie można go używać

Question

Często słyszałam ludzi mówiących o hashach i hash mapach i tablicach hash. Chciałem wiedzieć, czym są i gdzie najlepiej można z nich korzystać.

Answer 1

najpierw ty Shoud może odczytać to article.

Podczas korzystania z list i szukania specjalnego elementu zwykle trzeba przejrzeć całą listę. Jest to bardzo drogie, gdy masz duże listy.
Hafter może być dużo szybszy, w najlepszych okolicznościach dostaniesz przedmiot, którego szukasz tylko jednym dostępem.
Jak to działa? Podobnie jak słownik ... kiedy szukasz słowa "hashtable" w słowniku, nie zaczynasz od pierwszego słowa pod "a". Ale raczej idziesz prosto do litery "h". Następnie do "ha", "ma" i tak dalej, aż znalazłeś słowo. Używasz indeksu w słowniku, aby przyspieszyć wyszukiwanie.
Hafter robi zasadniczo to samo. Każdy przedmiot otrzymuje unikalny indeks (tzw. hash). Ten skrót jest używany do wyszukiwania. Hash może być indeksem na normalnie połączonej liście. Na przykład twój hash może być liczbą podobną do 2130, co oznacza, że ​​powinieneś spojrzeć na pozycję 2130 na liście. Wyszukiwanie znanego indeksu w ramach normalnej listy jest bardzo łatwe i szybkie.
Problemem całego podejścia jest tak zwana hash function, która przypisuje ten indeks do każdego elementu. Kiedy szukasz przedmiotu, powinieneś być w stanie obliczyć indeks z góry. Podobnie jak w prawdziwym słowniku, gdzie widzisz, że słowo "hashtable" zaczyna się od litery "h" i dlatego znasz przybliżoną pozycję.
Dobra funkcja haszowania zapewnia hashcodes, które są równomiernie rozproszone w przestrzeni wszystkich możliwych kodów hash. I oczywiście próbuje uniknąć collisions. Kolizja ma miejsce, gdy dwa różne elementy otrzymują ten sam kod skrótu.
W języku C# na przykład każdy obiekt ma metodę GetHashcode(), która zapewnia jego skrót (niekoniecznie unikalny). Można go użyć do wyszukiwania i sortowania w słowniku.

Po rozpoczęciu używania tablic asocjacyjnych zawsze należy pamiętać, że poprawnie obsługuje kolizje. Zdarza się to dość łatwo w dużych hashtables, że dwa obiekty mają ten sam skrót (może twoje przeciążenie GetHashcode() jest wadliwe, może coś innego się stało).

Answer 2

Zasadniczo, HashMap pozwala na przechowywanie przedmiotów z identyfikatorami. Są one przechowywane w formacie tabeli z hasłem mieszanym przy użyciu algorytmu mieszania.

Zazwyczaj są one bardziej wydajne, aby odzyskać przedmioty niż drzew wyszukiwania itp

może okazać się pomocne: http://www.relisoft.com/book/lang/pointer/8hash.html

Nadzieja pomaga,

Chris

Answer 3

Hashing (w sensie niekryptograficznym) jest terminem zbiorczym do pobrania danych wejściowych, a następnie tworzenia danych wyjściowych w celu identyfikacji. Trywialny przykładem mieszania dodaje sumę liter sznurku, a mianowicie:

f(abc) = 6 

pamiętać, że ten banalny schemat hash stworzyłoby kolizję między strunami abc, BCA, ae itp efektywny program hashowy w naturalny sposób wytworzyłby różne wartości dla każdego ciągu.

Hashmapy i hashtables to dane strukturalne (takie jak tablice i listy), które korzystają z funkcji mieszania do przechowywania danych. W hashtable, hash jest tworzony (albo z dostarczonego klucza, albo z samego obiektu), który określa, gdzie w tabeli obiekt jest przechowywany. Oznacza to, że tak długo jak użytkownik hashtable jest świadomy klucza, pobieranie obiektu jest niezwykle szybkie.

Na liście, w porównaniu, musisz w jakiś sposób przeszukać listę, aby znaleźć poszukiwany obiekt. Reprezentuje to również tyłkę hashtables, która polega na tym, że bardzo trudno znaleźć w niej obiekt bez znajomości klucza, ponieważ miejsce, w którym obiekt jest przechowywany w tabeli, nie ma żadnego znaczenia dla jego wartości ani kiedy zostało wprowadzone.

Hashmapy są podobne do hashtables, ale przechowywany jest w nich tylko jeden przykład każdego obiektu (stąd nie ma potrzeby podawania klucza, sam obiekt jest kluczem).

Jest to oczywiście bardzo proste wytłumaczenie, więc sugeruję, abyś przeczytał dogłębnie od tego miejsca. Mam nadzieję, że nie popełniłem żadnych głupich błędów. =)

Answer 4

Hashmap służy do przechowywania danych w parach wartości kluczy. 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. Hashmap i wartości są przechowywane w wiadrze do określonego wpisu, ta lokalizacja wpisu jest określana za pomocą funkcji Hashcode. Ta funkcja hashcode określa wartość mieszania, w której zapisana jest wartość. Szczegółowy opis działania funkcji działający jest opisany w tym filmie: https://youtu.be/iqYC1odZSNo