Co je hashování

Je to proces převodu objektu na celočíselnou hodnotu. Hodnota celého čísla pomáhá při indexování a rychlejším vyhledávání.

Co je HashMap

HashMap je součástí kolekce Java. Využívá techniku ​​zvanou hashování. Implementuje mapové rozhraní. Ukládá data do dvojice Klíč a Hodnota. HashMap obsahuje pole uzlů a uzel je reprezentován jako třída. Interně používá pole a datovou strukturu LinkedList pro ukládání klíče a hodnoty. HashMap má čtyři pole.

Než pochopíte vnitřní fungování HashMap, musíte si být vědomi metod hashCode() a equals().

jak spustit skript

rovná se():Kontroluje rovnost dvou objektů. Porovnává Klíč, ať už jsou si rovni nebo ne. Je to metoda třídy Object. Dá se to přepsat. Pokud přepíšete metodu equals(), pak je povinné přepsat metodu hashCode().hashCode():Toto je metoda třídy objektů. Vrátí paměťový odkaz objektu v celočíselné podobě. Hodnota přijatá z metody se použije jako číslo segmentu. Číslo kbelíku je adresa prvku uvnitř mapy. Hash kód nulového klíče je 0.Kbelíky:Pole uzlu se nazývá buckets. Každý uzel má datovou strukturu jako LinkedList. Více než jeden uzel může sdílet stejný segment. Může se lišit v kapacitě.

Vložte klíč, pár hodnot do HashMap

K vložení páru Klíč a Hodnota do HashMapu používáme metodu put(). Výchozí velikost HashMap je 16 (0 až 15).

Příklad

V následujícím příkladu chceme do HashMapu vložit tři páry (klíč, hodnota).

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

Podívejme se, na kterém indexu se do HashMapu uloží pár Klíč, hodnota. Když zavoláme metodu put(), pak vypočítá hash kód klíče 'Aman'. Předpokládejme, že hash kód 'Aman' je 2657860. Abychom klíč uložili do paměti, musíme vypočítat index.

Java kolekce framework

Výpočet indexu

Index minimalizuje velikost pole. Vzorec pro výpočet indexu je:

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

Kde n je velikost pole. Hodnota indexu pro „Aman“ je tedy:

 Index = 2657860 & (16-1) = 4 

Hodnota 4 je vypočítaná hodnota indexu, kam se klíč a hodnota uloží v HashMap.

Hash Collision

To je případ, kdy je vypočítaná hodnota indexu stejná pro dva nebo více klíčů. Pojďme vypočítat hash kód pro další klíč „Sunny“. Předpokládejme, že hash kód pro 'Sunny' je 63281940. Abychom klíč uložili do paměti, musíme vypočítat index pomocí indexového vzorce.

 Index=63281940 & (16-1) = 4 

Hodnota 4 je vypočítaná hodnota indexu, kde bude klíč uložen v HashMap. V tomto případě metoda equals() zkontroluje, zda jsou oba klíče stejné nebo ne. Pokud jsou klíče stejné, nahraďte hodnotu aktuální hodnotou. V opačném případě připojte tento objekt uzlu k existujícímu objektu uzlu prostřednictvím LinkedList. Proto budou oba klíče uloženy na indexu 4.

obrázek jako pozadí v css

Podobně uložíme klíč „Ritesh“. Předpokládejme, že hash kód pro klíč je 2349873. Hodnota indexu bude 1. Tento klíč bude tedy uložen na indexu 1.

get() v HashMap

metoda get() se používá k získání hodnoty pomocí jejího klíče. Pokud neznáte klíč, hodnotu nenačte. Když je zavolána metoda get(K Key), vypočítá hash kód klíče.

Předpokládejme, že musíme získat klíč 'Aman'. Bude volána následující metoda.

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

Vygeneruje hash kód jako 2657860. Nyní vypočítejte hodnotu indexu 2657860 pomocí indexového vzorce. Hodnota indexu bude 4, jak jsme spočítali výše. Metoda get() hledá hodnotu indexu 4. Porovnává první prvek Key s daným Key. Pokud jsou oba klíče stejné, vrátí hodnotu else check pro další prvek v uzlu, pokud existuje. V našem scénáři je nalezen jako první prvek uzlu a vrací hodnotu 19.

Přinesme další klíč „Sunny“.

Hash kód klíče 'Sunny' je 63281940. Vypočtená hodnota indexu 63281940 je 4, jak jsme vypočítali pro metodu put(). Přejděte na index 4 pole a porovnejte Klíč prvního prvku s daným klíčem. Porovnává také Keys. V našem scénáři je daný klíč druhým prvkem a další z uzlu je null. Porovná druhý prvek Key se zadaným klíčem a vrátí hodnotu 29. Vrátí hodnotu null, pokud je další z uzlu null.