logo

Działanie HashMap w Javie


Co to jest haszowanie

Jest to proces przekształcania obiektu w wartość całkowitą. Wartość całkowita pomaga w indeksowaniu i szybszym wyszukiwaniu.

Czym jest HashMap

HashMap jest częścią struktury kolekcji Java. Wykorzystuje technikę zwaną hashowaniem. Implementuje interfejs mapy. Przechowuje dane w parze klucza i wartości. HashMap zawiera tablicę węzłów, a węzeł jest reprezentowany jako klasa. Wykorzystuje wewnętrznie strukturę danych tablicy i LinkedList do przechowywania klucza i wartości. W HashMap są cztery pola.

Działanie HashMap w Javie

Zanim zrozumiesz wewnętrzne działanie HashMap, musisz zapoznać się z metodami hashCode() i równości().

globalna zmienna JavaScript
    równa się():Sprawdza równość dwóch obiektów. Porównuje Klucz, niezależnie od tego, czy są one równe, czy nie. Jest to metoda klasy Object. Można to zastąpić. Jeśli zastąpisz metodę równości(), obowiązkowe będzie nadpisanie metody hashCode().hashCode():To jest metoda klasy obiektu. Zwraca odwołanie do pamięci obiektu w postaci całkowitej. Wartość uzyskana z metody służy jako numer zasobnika. Numer segmentu to adres elementu na mapie. Kod skrótu klucza zerowego to 0.Wiadra:Tablica węzła nazywana jest segmentami. Każdy węzeł ma strukturę danych podobną do LinkedList. Więcej niż jeden węzeł może współużytkować ten sam zasobnik. Może mieć różną pojemność.
Działanie HashMap w Javie

Wstaw klucz, parę wartości w HashMap

Używamy metody put(), aby wstawić parę klucz i wartość do HashMap. Domyślny rozmiar HashMap to 16 (0 do 15).

Przykład

W poniższym przykładzie chcemy wstawić trzy pary (Klucz, Wartość) do HashMap.

 HashMap map = new HashMap(); map.put('Aman', 19); map.put('Sunny', 29); map.put('Ritesh', 39); 

Zobaczmy, pod jakim indeksem para klucz-wartość zostanie zapisana w HashMap. Kiedy wywołujemy metodę put(), wówczas oblicza ona kod skrótu klucza „Aman”. Załóżmy, że kod skrótu „Aman” to 2657860. Aby zapisać klucz w pamięci, musimy obliczyć indeks.

Obliczanie indeksu

Indeks minimalizuje rozmiar tablicy. Wzór na obliczenie wskaźnika to:

 Index = hashcode(Key) & (n-1) 

Gdzie n jest rozmiarem tablicy. Stąd wartość indeksu dla „Aman” wynosi:

rodzaje uczenia maszynowego
 Index = 2657860 & (16-1) = 4 

Wartość 4 to obliczona wartość indeksu, w której klucz i wartość będą przechowywane w HashMap.

Działanie HashMap w Javie

Kolizja hasha

Dzieje się tak, gdy obliczona wartość indeksu jest taka sama dla dwóch lub więcej kluczy. Obliczmy kod skrótu dla innego klucza „Sunny”. Załóżmy, że kod skrótu dla „Sunny” to 63281940. Aby zapisać klucz w pamięci, musimy obliczyć indeks, korzystając ze wzoru na indeks.

 Index=63281940 & (16-1) = 4 

Wartość 4 to obliczona wartość indeksu, w którym klucz będzie przechowywany w HashMap. W tym przypadku metoda równości() sprawdza, czy oba klucze są równe, czy nie. Jeśli klucze są takie same, zastąp wartość bieżącą wartością. W przeciwnym razie połącz ten obiekt węzła z istniejącym obiektem węzła za pomocą listy LinkedList. Dlatego oba klucze będą przechowywane pod indeksem 4.

Działanie HashMap w Javie

Podobnie będziemy przechowywać klucz „Ritesh”. Załóżmy, że kod skrótu klucza to 2349873. Wartość indeksu będzie wynosić 1. Dlatego ten klucz będzie przechowywany pod indeksem 1.

Działanie HashMap w Javie

get() w HashMap

Metoda get() służy do pobierania wartości według klucza. Nie pobierze wartości, jeśli nie znasz klucza. Po wywołaniu metody get(K Key) oblicza ona kod skrótu klucza.

jak duży jest mój monitor

Załóżmy, że musimy zdobyć Klucz „Aman”. Zostanie wywołana następująca metoda.

 map.get(new Key('Aman')); 

Generuje kod skrótu jako 2657860. Teraz oblicz wartość indeksu 2657860, korzystając ze wzoru na indeks. Wartość indeksu wyniesie 4, jak obliczyliśmy powyżej. metoda get() szuka wartości indeksu 4. Porównuje pierwszy element Key z podanym Kluczem. Jeśli oba klucze są równe, zwraca wartość, w przeciwnym razie sprawdza następny element w węźle, jeśli istnieje. W naszym scenariuszu znajduje się jako pierwszy element węzła i zwraca wartość 19.

Przynieśmy kolejny klucz „Sunny”.

Kod skrótu klucza „Sunny” to 63281940. Obliczona wartość indeksu 63281940 wynosi 4, tak jak obliczyliśmy dla metody put(). Przejdź do indeksu 4 tablicy i porównaj Klucz pierwszego elementu z podanym Kluczem. Porównuje także Klucze. W naszym scenariuszu podany Klucz jest drugim elementem, a następny węzeł ma wartość null. Porównuje drugi element Key z określonym Key i zwraca wartość 29. Zwraca wartość null, jeśli następny węzeł ma wartość null.