Jak działa HashMap w Javie

Większość z Was zgodzi się HashMap, że jest to obecnie najpopularniejszy temat rozmów podczas rozmów kwalifikacyjnych. Czasami prowadziłem podobne dyskusje z kolegami i naprawdę mi to pomogło. Teraz przeprowadzę z tobą taką dyskusję. Zakładam, że jeśli interesują Cię elementy wewnętrzne i działanie HashMap, to znasz już podstawy HashMap , więc pominę tę część. Jeśli jednak jesteś w tym nowy, sugeruję przejście do witryny Java Docs . Zanim przejdziemy dalej, gorąco polecam zapoznanie się z moim poprzednim artykułem: Praca z hashCode i metodą równości w Javie. Treść tego artykułu:

1. Jedyna możliwa odpowiedź.
2. Co to jest haszowanie.
3. Trochę o klasie Entry.
4. Co robi put().
5. Jak działa metoda get().
6. Notatki

Jedyna możliwa odpowiedź

Jeśli ktoś poprosi mnie o wyjaśnienie „ Jak działa HashMap?” „, odpowiem po prostu: „ Zgodnie z zasadami Hashowania ”. To nie mogłoby być prostsze. Aby to zrozumieć i uzyskać rozszerzoną odpowiedź, musisz upewnić się, że znasz podstawy haszowania. Prawidłowy?

Co to jest haszowanie

Haszowanie w najprostszej formie to sposób na konwersję dowolnej zmiennej/obiektu na unikalny kod po zastosowaniu dowolnej formuły/algorytmu do ich właściwości. Prawdziwa funkcja skrótu musi spełniać następującą zasadę: Funkcja skrótu musi zwracać ten sam kod skrótu, gdy zostanie zastosowana do tych samych lub równych obiektów. Innymi słowy, dwa identyczne obiekty muszą po kolei zwracać te same kody skrótu. Więcej na ten temat możesz przeczytać tutaj: Praca z metodą hashCode i równa się w Javie

Trochę o klasie Entry

Z definicji mapa to „obiekt przechowujący wartości i klucze w parach”. Całkiem proste, prawda? Zatem musi istnieć jakiś mechanizm w HashMap, który przechowuje pary wartości i kluczy? Odpowiedź - tak. HashMapma klasę wewnętrzną Entry, która wygląda następująco:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной kod тут…
}

Oczywiście klasa Entryma klucz i wartość przechowywane jako atrybuty. Klucz jest oznaczony jako finali widzimy też dwa dodatkowe pola: nexti hash. Postaramy się zrozumieć cel tych pól w miarę postępu artykułu.

Do czego służy metoda put() w języku Java?

Zanim zagłębimy się w implementację metody put(), bardzo ważne jest, aby zrozumieć, że instancje klasy Entrysą przechowywane w tablicy. Klasa HashMap definiuje tę zmienną jako:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

Teraz spójrz na kod implementacji metody put():

/**
* Связывает определенное oznaczający с определенным ключом в этой карте(map).
* Если карта перед этим содержала oznaczający для данного ключа, это oznaczający
* заменится на новое.
*
* @param key
*            ключ с которым указанное oznaczający должно быть связано.
* @param value
*            oznaczający которое должно быть связано с ключом.
* @return вернет предыдущее oznaczający связанное с key, Lub null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со oznaczającyм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

Rozwiążmy to krok po kroku:

• Przede wszystkim sprawdzamy, czy klucz istnieje. Jeśli klucz nie istnieje ( null), wartość jest umieszczana w tabeli na pozycji zero, ponieważ kod skrótu wartości to null, это – всегда 0.


• W kolejnym kroku wartość skrótu wyliczana jest na podstawie kodu skrótu klucza uzyskanego w wyniku wywołania metody hashCode(). Ta wartość skrótu służy do obliczenia pozycji w tablicy, w której obiekt zostanie umieszczony Entry. Projektanci JDK założyli, że źle napisana funkcja hashCode()może zwrócić wartość skrótu, która będzie zbyt wysoka lub zbyt niska. Aby rozwiązać ten problem, wprowadzono inną hash()funkcję i przekazano do niej wartość skrótu obiektu, aby wartość skrótu odpowiadała rozmiarowi tablicy.


• Teraz wywoływana jest funkcja, która indexFor(hash, table.length)oblicza dokładną pozycję, w której obiekt zostanie umieszczony Entry.


• Tutaj zaczyna się główna część. Teraz, w oparciu o to, co wiemy, że dwa różne obiekty mogą mieć takie same kody mieszające, zadajemy pytanie: Czy dwa różne obiekty zostaną umieszczone w tej samej pozycji w tablicy [bucket]? Odpowiedź brzmi: LinkedList. Jeśli pamiętasz, klasa Entryma atrybut „ next”. Ten atrybut zawsze wskazuje następny obiekt w łańcuchu. To jest dokładnie takie zachowanie LinkedList.

Zatem obiekty Entrysą przechowywane w formie LinkedList. Kiedy obiekt Entryma zostać umieszczony w określonej lokalizacji, HashMap sprawdza, czy w tej lokalizacji znajduje się już wpis. Jeśli nie ma wpisu, obiekt zostaje umieszczony w tej pozycji. Jeśli jednak na tej pozycji znajduje się już obiekt, sprawdzany jest kolejny atrybut. Jeśli powróci nulli bieżący obiekt Entrystanie się kolejnym łączem w pliku LinkedList. Jeżeli następna zmienna nie jest null, procedura jest powtarzana dla kolejnej, aż zostanie znaleziona null. A co jeśli umieścimy kolejny obiekt o innej wartości, ale z tym samym kluczem co poprzednio? Logicznie rzecz biorąc, powinno to skutkować zastąpieniem starej wartości. Jak to się stało? Ogólnie rzecz biorąc, po ustaleniu położenia obiektu Entry, podczas dochodzenia LinkedListdo obliczonej pozycji, HashMapwywołuje metodę porównania klucza dla każdego obiektu Entry. Wszystkie te Entryobiekty LinkedListmogą mieć podobne kody skrótu, ale metoda equals()sprawdzi prawdziwe podobieństwo. Spowoduje to jedynie zastąpienie wartości w pliku Entry. Tym samym HashMap gwarantuje unikalność wszystkich kluczy.

Jak działa metoda get() w Javie?

Teraz mamy pojęcie, w jaki sposób pary klucz-wartość są przechowywane w plikach HashMap. Następne ważne pytanie brzmi: co się stanie, gdy obiekt zostanie przekazany z HashMap do metody get()? Jak ustala się wartość przedmiotu? Odpowiedź powinniśmy już znać, gdyż sposób wyznaczania unikalności klucza w metodzie put()ma tę samą logikę, którą stosuje metoda get(). Po HashMapustaleniu klucza obiektu przekazanego jako argument po prostu zwraca wartość odpowiedniego obiektu Entry. Jeśli nie zostaną znalezione żadne dopasowania, metoda get()zwróci null. Rzućmy okiem na kod:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

Powyższy kod jest podobny do metody put()stosowanej do tej pory if (e.hash == hash && ((k = e.key) == key || key.equals(k))), a następnie zwraca po prostu wartość obiektu.

Notatki

• Struktura danych przechowywana w obiekcie Entryto tablica z nazwą tablei typem Entry.
• Każda pojedyncza pozycja w tablicy nazywana jest wiadrem, ponieważ może zawierać pierwszy element LinkedListobiektów Entry.
• hashCode()Klucz potrzebny jest do obliczenia pozycji obiektu Entry.
• equals()Klucz służy do sprawdzania unikalności klucza na mapie( map).
• hashCode()i equals()Wartości nie są używane w metodach get()i set()w HashMap.
• Kod skrótu dla kluczy z wartością nullwynosi zawsze 0. I taki obiekt Entrybędzie zawsze przechowywany w pozycji zerowej tablicy.

Mam nadzieję, że poprawnie przekazałem swoje myśli w tym artykule. Jeśli znajdziesz błędy lub masz pytania, zostaw je w komentarzach. Miłej nauki!