To będzie długa odpowiedź, weź drinka i czytaj dalej…
Hashowanie polega na przechowywaniu w pamięci pary klucz-wartość, którą można szybciej odczytywać i zapisywać. Przechowuje klucze w tablicy i wartości w LinkedList.
Powiedzmy, że chcę przechowywać 4 pary kluczowych wartości -
{
“girl” => “ahhan” ,
“misused” => “Manmohan Singh” ,
“horsemints” => “guess what”,
“no” => “way”
}
Aby przechowywać klucze, potrzebujemy tablicy 4 elementów. Jak teraz odwzorować jeden z tych 4 kluczy na 4 indeksy tablic (0,1,2,3)?
Więc java znajduje hashCode poszczególnych kluczy i mapuje je na określony indeks tablicy. Formuły Hashcode to -
1) reverse the string.
2) keep on multiplying ascii of each character with increasing power of 31 . then add the components .
3) So hashCode() of girl would be –(ascii values of l,r,i,g are 108, 114, 105 and 103) .
e.g. girl = 108 * 31^0 + 114 * 31^1 + 105 * 31^2 + 103 * 31^3 = 3173020
Hash i dziewczyna !! Wiem o czym myślisz. Twoja fascynacja dzikim duetem może sprawić, że przegapisz ważną rzecz.
Dlaczego Java pomnoży to przez 31?
To dlatego, że 31 jest nieparzystą liczbą pierwszą w postaci 2 ^ 5 - 1. A nieparzysta liczba pierwsza zmniejsza prawdopodobieństwo kolizji Hash
Jak ten kod skrótu jest odwzorowany na indeks tablicy?
Odpowiedź brzmi Hash Code % (Array length -1) . Tak “girl”jest odwzorowane (3173020 % 3) = 1w naszym przypadku. który jest drugim elementem tablicy.
a wartość „ahhan” jest przechowywana w LinkedList powiązanej z indeksem tablicy 1.
HashCollision - Jeśli spróbujesz znaleźć hasHCodeklucze “misused”i “horsemints”użyć opisanych powyżej formuł, zobaczysz, że oba dają nam to samo 1069518484. Whooaa !! wyciągnięta lekcja -
2 równe obiekty muszą mieć ten sam hashCode, ale nie ma gwarancji, że jeśli hashCode się zgadza, to obiekty są równe. Powinien więc przechowywać zarówno wartości odpowiadające „niewłaściwie użytemu”, jak i „koniom” w segmencie 1 (1069518484% 3).
Teraz mapa skrótu wygląda następująco -
Array Index 0 –
Array Index 1 - LinkedIst (“ahhan” , “Manmohan Singh” , “guess what”)
Array Index 2 – LinkedList (“way”)
Array Index 3 –
Teraz, jeśli jakieś ciało spróbuje znaleźć wartość klucza “horsemints”, java szybko znajdzie jej hashCode, moduł i zacznie szukać jego wartości w odnośniku LinkedList index 1. W ten sposób nie musimy przeszukiwać wszystkich 4 indeksów tablic, co przyspieszy dostęp do danych.
Ale poczekaj jedną sekundę. istnieją 3 wartości w tym odnośniku 1 odpowiadającym indeksowi tablicy, w jaki sposób dowiaduje się, która z nich była wartością kluczowych „konników”?
Właściwie skłamałem, kiedy powiedziałem, że HashMap po prostu przechowuje wartości w LinkedList.
Przechowuje obie pary wartości klucza jako wpis mapy. Mapa faktycznie wygląda tak.
Array Index 0 –
Array Index 1 - LinkedIst (<”girl” => “ahhan”> , <” misused” => “Manmohan Singh”> , <”horsemints” => “guess what”>)
Array Index 2 – LinkedList (<”no” => “way”>)
Array Index 3 –
Teraz możesz zobaczyć Podczas przechodzenia przez LinkedList odpowiadającą ArrayIndex1 faktycznie porównuje on klucz każdego wpisu do tej LinkedList z „koniami”, a gdy go znajdzie, po prostu zwraca jego wartość.
Mam nadzieję, że dobrze się bawiłeś podczas czytania :)
