HashMap je datová struktura, která ukládá data v párech (Key, Value), podobně jako Dictionary v Pythonu, pokud vás to zajímá!
Abychom pochopili vnitřní fungování Hashmapy, seznámíme se s následujícími pojmy:
HASHING:
Hashing je proces převodu daného klíče na jinou hodnotu na základě vzorce pomocí funkce. K vygenerování nové hodnoty se používá hashovací funkce podle matematického algoritmu. Výsledek hashovací funkce se nazývá hashovací hodnota nebo jednoduše hash. Používá se k indexování a vyhledávání položek a pro
šifrovací algoritmy.
Pravá hašovací funkce musí splňovat toto pravidlo –
„Hašovací funkce by měla vracet stejný hašovací kód pokaždé, když je funkce použita na stejné nebo stejné objekty. Jinými slovy, dva stejné objekty musí konzistentně poskytovat stejný hash kód.“
Všechny objekty v Javě dědí výchozí implementaci funkce hashCode() definovanou ve třídě Object.
KOLIK :
Mějte na paměti, že dva klíče mohou generovat stejný hash, který může vést ke stejné adrese. Tento jev je známý jako kolize.
Funkce hashové mapy
1. Public V get(Object key) : tj. načtení hodnoty z mapy na základě klíče.
2. Public V put(K key, V value) : neboli vložení dvojice klíč , hodnota do mapy.
Poznámka: Obecně je nutné přepsat metodu hashCode() vždy, když je přepsána metoda equals(), aby byla zachována obecná smlouva pro metodu hashCode(), která říká, že stejné objekty musí mít stejné hash kódy.
HashMap in JAVA
Způsoby instancování HashMap v Javě:
1. Konstruuje prázdnou HashMap se zadanou počáteční
kapacitou a koeficientem zatížení.
public HashMap(int initialCapacity, float loadFactor)
2. Konstruuje prázdnou HashMap se zadanou počáteční
kapacitou a výchozím koeficientem zatížení (0,75).
public HashMap(int initialCapacity)
3. Konstruuje prázdnou HashMap s výchozí počáteční kapacitou (16) a výchozím faktorem zatížení (0.75).
public HashMap()
Faktor zatížení a počáteční kapacita.
Instance HashMap má dva parametry, které ovlivňují její výkon:
1. Počáteční kapacita
2. Faktor zatížení.
Počáteční kapacita :
Kapacita je počet kyblíků v hašovací tabulce a počáteční kapacita je jednoduše kapacita v okamžiku vytvoření hašovací tabulky.
Faktor zatížení:
Faktor zatížení je měřítkem toho, jak moc se může hašovací tabulka zaplnit, než se automaticky zvýší její kapacita. Když počet záznamů v tabulce hash překročí součin faktoru zatížení a aktuální kapacity, tabulka hash se přeplní (tj. vnitřní datové struktury se přestaví) tak, aby tabulka hash měla přibližně dvojnásobný počet bucketů.
POZNÁMKA:
Všeobecně platí, že výchozí faktor zatížení (.75) nabízí dobrý kompromis mezi časovými a prostorovými náklady. Vyšší hodnoty snižují prostorovou režii, ale zvyšují náklady na vyhledávání (což se projevuje ve většině operací třídy HashMap, včetně get a put.
Při nastavování počáteční kapacity mapy by se měl brát v úvahu očekávaný počet záznamů v mapě a její load factor, aby se minimalizoval počet operací rehash. Pokud je počáteční kapacita větší než maximální počet položek dělený faktorem zatížení, nikdy nedojde k žádným operacím rehash.
HashMap v Javě 8
Mapa HashMap(z Javy 8) ukládá data do několika singly linked seznamů položek nebo několika Red BlacK Trees nebo směsi obou , v závislosti na prahu, nazývaných také buckets nebo bins.
Všechny seznamy/stromy jsou zapsány v poli Entry (Entry<K,V> tabulka) a výchozí kapacita tohoto vnitřního pole je 16.
Každý z jednotlivých záznamů nebo jedna dvojice Klíč a hodnota v HashMap se nazývá jako Entry<Klíč,Hodnota>.
Entry
HashMaps používají k ukládání dat vnitřní třídu: Entry<K,V>.
Tento záznam je jednoduchá dvojice klíč-hodnota se dvěma dalšími hodnotami, které jsou následující:
1. Odkaz na jiný Entry, takže HashMap může ukládat položky jako jednosvazkové seznamy nebo jako strom s levým a pravým uzlem pro zajištění lepšího vyhledávání.
2. Hodnota hash, která představuje hodnotu hash klíče. Tato hodnota hashe je uložena, aby se zabránilo výpočtu hashe pokaždé, když ji HashMap potřebuje.
Zápis v javě 8 může být dvou typů LinkedList Node nebo RedBlack Tree Node.
*velikost tohoto, jak bylo řečeno výše, je buď definována během instanciace, nebo je výchozí 16. Na základě koeficientu zatížení se zvětší na dvojnásobek předchozí velikosti, aby se do ní vešly další položky.
tabulka přechodných uzlů<K,V>; //obsahuje všechny položky.
V tabulce je každý index uzlem buď LinkedListu, nebo RedBlackTree.
Hierarchie záznamů vypadá takto:
Mapa.Entry<K,V> → implementuje → Node<K,V> → rozšiřuje → 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; //pro udržování LinkedListu.
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, v Javě 8 , používá RedBlackTree po dosažení určité prahové hodnoty známé jako TREEIFY_THRESHOLD(výchozí hodnota 8), protože dává v nejhorším případě časovou složitost O(log n), oproti LinkedList, který dává vyhledávání v O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // červeno-černé propojení stromu
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // potřeba odlinkovat next při smazání
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Práce funkcí HashMap
1. Kontroluje, zda je klíč nulový nebo ne . Všimněte si, že v mapě HashMap může být pouze jeden nulový klíč. pokud je klíč nulový , pak se nulové klíče vždy mapují na hash 0, tedy na index 0 tabulky.
2. Pokud klíč není null, pak metoda zavolá metodu hashCode() na objektu klíče(Overriden by the user in the respective Key class) a použije vrácenou hashValue na svou vlastní statickou hash funkci, aby našla umístění kbelíku(backing array), kde jsou uloženy klíče a hodnoty ve formě vnořené třídy Entry.
Umístění kbelíku je index tabulky Entry namely.
POZNÁMKA: hodnotu hash počítáme opět pomocí hash(hashValue), protože se tím bráníme proti nekvalitní hashovací funkci.
3. Konečná hodnota hash se použije k nalezení umístění bucket, ve kterém je uložen objekt Entry.
Složitost get() a put() je O(1) ,za předpokladu, že hashovací funkce správně rozptýlí prvky mezi kbelíky.
Poznámka: Jak již víme, v případě kolize hashování jsou objekty entry uloženy jako uzel v propojeném seznamu a k porovnání klíčů se používá metoda equals(). Toto porovnání za účelem nalezení správného klíče s v linked-listu je lineární operace, takže v nejhorším případě složitost nabývá hodnoty O(n).
Pro řešení tohoto problému používají hashovací prvky v Javě 8 po dosažení určité prahové hodnoty vyvážené stromy místo linked-listů. Což znamená, že HashMap začíná s ukládáním objektů Entry do spojového seznamu, ale poté, co počet položek v hashi překročí určitou prahovou hodnotu, hash se změní z použití spojového seznamu na vyvážený strom, což zlepší výkonnost v nejhorším případě z O(n) na O(log n).
Co když mají dva různé klíče stejný hashcode ?
4. U indexu můžeme mít více hodnot, protože při hashování můžeme mít kolize. Abychom zjistili, kterou z nich potřebujeme, vezme si HashMap na pomoc metodu equals().
Řešení, na pomoc přichází metoda equals(). Protože kbelík je jeden a máme dva objekty se stejným hash kódem .
Takže po načtení indexu klíče načte první uzel přítomný na tomto indexu. První uzel pak porovná s klíčem pomocí equals(), Pokud je to požadovaný uzel ,vrátí hodnotu přímo odtud.
Pak zjistí instanci uzlu, aby zjistil, zda jsou obsažená data uložená v tomto indexu ve formátu linkedlistu nebo RedBlackova stromu.
Jakmile to zjistíme, procházíme LinkedList nebo strom , porovnáváme klíče v jednotlivých položkách pomocí keys.equals(), dokud nevrátí true. Pak se vrátí odpovídající položka objektu 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; //představuje pole Entry
Node<K,V> first, e;
int n; K k;/* Kontrola, zda tabulka obsahuje položky .*/
/* Také nalezení indexu na základě vypočteného hashe v předchozích krocích, kde je záznam uložen buď jako Seznam, nebo Stromový uzel.*/if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Vybrání prvního uzlu v indexu získaném na základě hashe.*/
if (first.hash == hash && /* vždy zkontrolujeme první uzel*/
((k = first.key) == key||(key != null && key.equals(k))))
return first;/*Pokud první uzel tohoto indexu není hodnota, kterou hledáme,pak se přejde k procházení.*/
if ((e = first.next) != null) {
if (první instance TreeNode)
/*Vyhledávání z červenočerného stromu, pokud začíná uzel na indexu if TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/*Vybírání z LinkedListu, pokud je počáteční uzel typu Node a ne 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. Zkontroluje, zda je klíč null nebo ne .
Pokud je klíč null , pak se Null klíče vždy mapují na hash 0, tedy index 0 tabulky.
2. Pokud klíč není null, metoda zavolá metodu hashCode() na objektu klíče(Overriden by the user in the respective Key class) a aplikuje vrácenou hashValue na vlastní statickou hash funkci, aby našla místo bucket(backing array), kde mají být uloženy klíče a hodnoty ve formě vnořené třídy Entry.Umístění bucket je index Entry, konkrétně tabulky.
3. Konečná hodnota hash se použije k nalezení umístění bucket, ve kterém má být objekt Entry uložen. Poté se prochází Klíče stejným způsobem, jaký je popsán v get(), aby se zkontrolovalo, zda klíč již existuje, pokud existuje, hodnota se nahradí novou hodnotou.
Pak se zkontroluje velikost seznamu,
pokud překročí TREEIFY_THRESHOLD(výchozí 8), uzly se restrukturalizují do RedBlackTree a uloží se nový klíč s hodnotou v něm.
Pokud hranice není překročena, vytvoří se nový Entry s příslušným klíčem-hodnotou a uloží se.
public V put(K key, V value) {
return putVal(hash(key), key, value, 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 = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traverzování jako v 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);
/*Kontrola, zda je překročen TREEIFY_THRESHOLD nebo ne.*/if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 pro 1st*/
treeifyBin(tab, hash);
break;}if (e.hash == hash &&((k = e.key) == key || (key != null &&key.equals(k))))
break;
p = e;
}}if (e != null) { /* existující mapování pro klíč*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;}
Více k přečtení
Klíčová neměnnost:
Proč jsou řetězce a celá čísla dobrou implementací klíčů pro HashMap? Především proto, že jsou neměnné! Pokud se rozhodnete vytvořit vlastní třídu klíče a neuděláte ji neměnnou, můžete uvnitř mapy HashMap ztratit data.
Rehashing:
Rehashing je proces přepočítávání hashkódu již uložených položek (dvojic klíč-hodnota), aby se při dosažení prahové hodnoty Load factor přesunuly do jiné hashmapy větší velikosti.
Když počet položek v mapě překročí hranici Load factor, hashmap v té době zdvojnásobí svou kapacitu a hashcode již uložených prvků se přepočítá pro rovnoměrné rozložení dvojic klíč-hodnota do nových bucketů.
Proč je to potřeba?
Po zdvojnásobení kapacity, co dělat s dvojicemi klíč-hodnota, které jsou již přítomny v bucketech?
Pokud ponecháme stávající dvojice klíč-hodnota tak, jak jsou, pak zdvojnásobení kapacity nemusí pomoci,protože složitosti O(1) dosáhneme pouze tehdy, pokud jsou prvky rovnoměrně rozděleny do všech bucketů.
Pro každou existující dvojici klíč-hodnota se tedy znovu vypočítá hashcode se zvýšenou kapacitou hashmap jako parametrem, což vede buď k umístění položky do stejného kbelíku, nebo do jiného kbelíku.
.