Wewnętrzna praca HashMap

HashMap jest strukturą danych, która przechowuje dane w parach (Klucz, Wartość), podobną do Słownika w pythonie, jeśli jesteś w tym dobry!

Aby zrozumieć wewnętrzne działanie Hashmap, zapoznajmy się z następującymi terminami:

HASHING:
Hashing jest procesem przekształcania danego klucza w inną wartość na podstawie wzoru przy użyciu funkcji. Funkcja haszująca jest używana do generowania nowej wartości zgodnie z algorytmem matematycznym. Wynik funkcji haszującej jest znany jako wartość haszująca lub po prostu, hasz. Jest on używany do indeksowania i pobierania elementów oraz do
algorytmów szyfrowania.

Prawdziwa funkcja haszująca musi przestrzegać tej zasady –

„Funkcja haszująca powinna zwracać ten sam kod haszujący za każdym razem, gdy funkcja jest stosowana na tych samych lub równych obiektach. Innymi słowy, dwa równe obiekty muszą konsekwentnie generować ten sam kod skrótu.”

Wszystkie obiekty w Javie dziedziczą domyślną implementację funkcji hashCode() zdefiniowaną w klasie Object.

KOLIZJE :
Pamiętaj, że dwa klucze mogą wygenerować ten sam hash, który może prowadzić do tego samego adresu. Zjawisko to znane jest jako kolizja.

Funkcje HashMap

1. Public V get(Object key) : czyli pobieranie wartości z mapy na podstawie klucza.
2. Public V put(K key, V value) : czyli wstawianie pary klucz , wartość do mapy.

Uwaga: Ogólnie konieczne jest nadpisanie metody hashCode() za każdym razem, gdy nadpisywana jest metoda equals(), tak aby zachować ogólny kontrakt dla metody hashCode(), który mówi, że równe obiekty muszą mieć równe kody hash.

HashMap w JAVIE

Sposoby na zainicjowanie HashMap w java:
1. Konstruuje pustą mapę HashMap z podaną początkową
pojemnością i współczynnikiem obciążenia.

public HashMap(int initialCapacity, float loadFactor)

2. Konstruuje pustą mapę HashMap z podaną początkową
pojemnością i domyślnym współczynnikiem obciążenia (0,75).

public HashMap(int initialCapacity)

3. Konstruuje pustą HashMap z domyślną początkową pojemnością (16) i domyślnym współczynnikiem obciążenia (0.75).

public HashMap()

Współczynnik obciążenia i pojemność początkowa.

Instancja HashMap ma dwa parametry, które wpływają na jej działanie:
1. Pojemność początkowa
2. Współczynnik obciążenia.

Pojemność początkowa :
Pojemność to liczba wiaderek w tablicy hash, a pojemność początkowa to po prostu pojemność w momencie tworzenia tablicy hash.

Współczynnik obciążenia:
Współczynnik obciążenia jest miarą tego, jak bardzo tablica hash może się zapełnić, zanim jej pojemność zostanie automatycznie zwiększona. Gdy liczba wpisów w tablicy haseł przekroczy iloczyn współczynnika obciążenia i bieżącej pojemności, tablica haseł jest przebudowywana (to znaczy, wewnętrzne struktury danych są przebudowywane) tak, że tablica haseł ma w przybliżeniu dwa razy więcej kubełków.

UWAGA:

Jako ogólna zasada, domyślny współczynnik obciążenia (.75) oferuje dobry kompromis między kosztami czasu i przestrzeni. Wyższe wartości zmniejszają narzut przestrzeni, ale zwiększają koszt lookupu (odzwierciedlony w większości operacji klasy HashMap, w tym get i put.

Przewidywana liczba wpisów w mapie i jej współczynnik obciążenia powinny być brane pod uwagę przy ustalaniu jej początkowej pojemności, tak aby zminimalizować liczbę operacji rehash. Jeśli początkowa pojemność jest większa niż maksymalna liczba wpisów podzielona przez współczynnik obciążenia, nigdy nie wystąpią żadne operacje rehash.

HashMap w Java 8

A HashMap (z java 8) przechowuje dane w wielu pojedynczo połączonych listach wpisów lub wielu Red BlacK Trees lub mieszance obu, w zależności od progu, zwanych również kubełkami lub koszami.

Wszystkie listy/drzewa są zarejestrowane w tablicy Entry (tablica Entry<K,V>) i domyślna pojemność tej wewnętrznej tablicy wynosi 16.

Każdy z pojedynczych rekordów lub pojedyncza para Klucz i Wartość w HashMap jest nazywana jako Entry<Key,Value>.

Entry

HashMaps używają wewnętrznej klasy do przechowywania danych: Entry<K, V>.
Ten wpis jest prostą parą klucz-wartość z dwoma dodatkowymi wartościami, które są następujące:

1. Odniesienie do innego wpisu, tak że HashMap może przechowywać wpisy jak pojedynczo połączone listy lub jako Drzewo z lewym i prawym węzłem dla zapewnienia lepszego wyszukiwania.

2. Wartość hash, która reprezentuje wartość hash klucza. Ta wartość hash jest przechowywana, aby uniknąć obliczania hasha za każdym razem, gdy HashMap go potrzebuje.

Węzeł w java 8 może być z 2 typów LinkedList Node lub RedBlack Tree Node.

*size tego, jak omówiono powyżej, jest albo zdefiniowany podczas instancjonowania, albo domyślnie 16. Na podstawie współczynnika obciążenia zwiększa się on do dwukrotności poprzedniego rozmiaru, aby pomieścić kolejne wpisy.

transient Node<K,V>tablica; //zawiera wszystkie wpisy.

W tablicy każdy indeks jest węzłem LinkedList lub RedBlackTree.
Hierarchia wpisów wygląda następująco:

Map.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>

LinkedList Node:

static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //do utrzymywania listy LinkedList.
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}

TreeNode:

HashMap, w java 8 , używa RedBlackTree po przekroczeniu pewnego progu znanego jako TREEIFY_THRESHOLD(wartość domyślna 8), ponieważ daje to w najgorszym przypadku złożoność czasową O(log n), w porównaniu do LinkedList, który daje wyszukiwanie w O(n).

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // czerwono-czarne powiązania drzewa
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // potrzebne do odłączenia next przy usuwaniu
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}

Working of HashMap Functions

1. Sprawdza, czy klucz jest null czy nie . Zauważ, że może być tylko jeden klucz null w HashMap.Jeśli klucz jest null , to Null klucze zawsze mapować do hash 0, a więc indeks 0 tabeli.
2. Jeśli klucz nie jest null to metoda wywołuje metodę hashCode() na obiekcie klucza (Overriden przez użytkownika w odpowiedniej klasie Key) i stosuje zwróconą wartość hashValue do własnej statycznej funkcji hash, aby znaleźć lokalizację wiadra (backing array), gdzie klucze i wartości są przechowywane w postaci zagnieżdżonej klasy o nazwie Entry.
Lokalizacja wiadra jest indeksem Entry mianowicie tabeli.

UWAGA: obliczamy wartość hash ponownie używając hash(hashValue), ponieważ broni to przed słabą jakością funkcji hash.

3. Końcowa wartość hash jest używana do znalezienia lokalizacji kubełka, w którym przechowywany jest obiekt Entry.
Złożoność funkcji get() i put() wynosi O(1), zakładając, że funkcja haszująca prawidłowo rozprasza elementy pomiędzy kubełkami.

Uwaga: Jak już wiemy, w przypadku kolizji hash obiekty Entry są przechowywane jako węzły w linked-list i metoda equals() jest używana do porównywania kluczy. To porównanie w celu znalezienia właściwego klucza w połączonej liście jest operacją liniową, więc w najgorszym przypadku złożoność staje się O(n).
Aby rozwiązać ten problem, elementy hash w Javie 8 używają zrównoważonych drzew zamiast połączonych list po osiągnięciu pewnego progu. Oznacza to, że HashMap zaczyna od przechowywania obiektów Entry w połączonej liście, ale po tym jak liczba elementów w haszu stanie się większa niż pewien próg, hasz zmieni się z użycia połączonej listy na zrównoważone drzewo, które poprawi wydajność najgorszego przypadku z O(n) do O(log n).

Co jeśli dwa różne klucze mają ten sam hashcode ?

4. W indeksie możemy mieć wiele wartości, ponieważ możemy mieć kolizje w haszowaniu. Aby dowiedzieć się, którą z nich potrzebujemy, HashMap korzysta z pomocy equals().

Rozwiązanie, metoda equals() przychodzi na ratunek. Ponieważ kubełek jest jeden i mamy dwa obiekty o tym samym kodzie hash .

Więc po pobraniu indeksu klucza, pobiera pierwszy węzeł obecny na tym indeksie. Pierwszy węzeł jest następnie porównywany z kluczem za pomocą equals(), jeśli jest to pożądany węzeł, zwraca wartość bezpośrednio z tego miejsca.
Else, znajduje instancję węzła, aby dowiedzieć się, czy dane przechowywane w tym indeksie są w formacie listy połączonej lub drzewa RedBlack.

Gdy już się tego dowiemy, przemierzamy LinkedList lub drzewo, porównując klucze w każdym wpisie za pomocą keys.equals(), dopóki nie zwróci on wartości true. Następnie zwracany jest odpowiedni obiekt wpisu Value .

public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab; //reprezentuje tablicę Entry
Node<K,V> first, e;
int n; K k;

/* Sprawdzenie, czy tablica ma wpisy .*/
/* Również znalezienie indeksu na podstawie obliczonego hasha w poprzednich krokach, gdzie wpis jest przechowywany albo jako List albo Tree Node.*/

if ((tab = tablica) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Pobranie pierwszego węzła w indeksie uzyskanym na podstawie hasha.*/
if (first.hash == hash && /*zawsze sprawdzaj pierwszy węzeł*/
((k = first.key) == key||(key != null && key.equals(k))))
return first;

/*Jeśli pierwszy węzeł tego indeksu nie jest szukaną wartością, to następuje traversing.*/
if ((e = first.next) != null) {
if (pierwsza instancja TreeNode)
/*Pobieranie z Czerwono Czarnego Drzewa jeśli węzeł początkowy na indeksie if of TreeNode .*/

return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {

/*Pobieranie z LinkedList jeśli węzeł początkowy jest typu Node a nie Tree.*/

if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
while ((e = e.next) != null);
}}
return null;
}

PUT:

1. Jeśli klucz jest null, to klucze Null zawsze mapują do hasha 0, a więc do indeksu 0 tablicy.
2. Jeśli klucz nie jest null, metoda wywołuje metodę hashCode() na obiekcie klucza (nadpisywaną przez użytkownika w odpowiedniej klasie klucza) i stosuje zwróconą wartość hashValue do własnej statycznej funkcji hashującej, aby znaleźć lokalizację wiadra (tablicy wspierającej), gdzie klucze i wartości mają być przechowywane w postaci zagnieżdżonej klasy o nazwie Entry.Lokalizacja kubełka jest indeksem wpisu, czyli tablicy.
3. Końcowa wartość hash jest używana do znalezienia lokalizacji kubełka, w którym obiekt Entry ma być przechowywany. Następnie, klucze są przemierzane w taki sam sposób, jak opisano w get(), aby sprawdzić, czy klucz już istnieje, jeśli istnieje, wartość jest zastępowana nową wartością.
Jeśli rozmiar listy jest większy niż TREEIFY_THRESHOLD (domyślnie 8), węzły są przekształcane w RedBlackTree i nowy klucz jest przechowywany wraz z wartością w nim zawartą.
Jeśli próg nie jest przekroczony, nowy Wpis jest tworzony z odpowiednim kluczem-wartością i jest przechowywany.

public V put(K klucz, V wartość) {
return putVal(hash(klucz), klucz, wartość, false, true);}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = tab) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*Sprawdzenie czy TREEIFY_THRESHOLD jest przekroczone czy nie.*/

if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 dla 1st*/
treeifyBin(tab, hash);
break;}

if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}}

if (e != null) { /* istniejące mapowanie dla klucza*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}

++modCount;

if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;}