Wierzę, że będzie bardziej pomocne, jeśli wyjaśnię HashMapy po angielsku.

Co to jest HashMap?

HashMap jest strukturą danych, która jest w stanie mapować pewne klucze do pewnych wartości. Te klucze i wartości mogą być dowolne. Na przykład, gdybym tworzył grę, mógłbym połączyć każdą nazwę użytkownika z listą przyjaciół, reprezentowaną przez Listę łańcuchów.

Dlaczego warto używać HashMap?

HashMap są znacznie szybsze w odzyskiwaniu danych niż tablice i listy połączone. Posortowana tablica może znaleźć konkretną wartość w O(log n) z wyszukiwaniem binarnym. Jednak HashMap może sprawdzić, czy zawiera konkretny klucz w O(1). Wszystkie klucze muszą być unikalne.

Jak działają HashMapy?

HashMapy używają tablicy w tle. Każdy element w tablicy jest inną strukturą danych (zwykle połączoną listą lub drzewem wyszukiwania binarnego). HashMap używa funkcji na kluczu, aby określić, gdzie umieścić wartość klucza w tablicy. Na przykład, jeśli moja HashMap akceptuje Strings … możliwe funkcje haszujące mogą być:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

Wartość zwrócona określi indeks, w którym wartość trafi do tablicy.

But Wait! There’s a Problem!

Możliwe jest, że zwrócona wartość będzie poza granicami tablicy. Dlatego mamy modyfikować zwracaną wartość o długość tablic.

return Math.abs(number%hashMapArray.length);

Kolizje:

Czy nie jest możliwe, że wiele kluczy sprawi, że funkcja haszująca wygeneruje ten sam indeks? Tak. Na przykład, jeśli użyliśmy pierwszej funkcji hashującej pokazanej powyżej w mapie hashującej ciągów znaków…dowolne dwa ciągi znaków, które zaczynają się od tej samej litery, otrzymają ten sam indeks tablicy.

To się nazywa kolizja.

Jak radzimy sobie z kolizjami?

Jedna z technik obsługi kolizji nazywa się Chaining. Ponieważ każdy element w tablicy jest połączoną listą (lub podobną strukturą danych), wiele kluczy, które mają tę samą wartość hash, zostanie umieszczonych w tej samej połączonej liście lub „wiadrze”. Następnie mapa hashowa jest w stanie pobrać wartości, obliczając kod hash za pomocą funkcji hashowania i przeszukując konkretną połączoną listę, aby sprawdzić, czy zawiera ona wartość z tym samym kluczem.

Dobra funkcja haszująca musi być napisana tak, aby uniknąć kolizji.

Zalety łańcuchowania:

-Array nie może się przepełnić

-Data może być łatwo usunięta

Wady łańcuchowania:

-Może cierpieć na wydajność, jeśli kubełki zawierają bardzo długie listy połączone.

Całkowita liczba wpisów do liczby kubełków jest nazywana współczynnikiem obciążenia. Jeśli współczynnik obciążenia jest zbyt niski, marnuje się dużo miejsca. Jeśli współczynnik obciążenia jest zbyt wysoki, traci się zaletę haszowania. Dobrym kompromisem w kwestii współczynnika obciążenia jest .75

.