Čo je hashovanie

Je to proces prevodu objektu na celočíselné hodnoty. Hodnota celého čísla pomáha pri indexovaní a rýchlejšom vyhľadávaní.

Čo je HashMap

HashMap je súčasťou kolekcie Java. Používa techniku ​​nazývanú hashovanie. Implementuje mapové rozhranie. Údaje ukladá do dvojice kľúč a hodnota. HashMap obsahuje pole uzlov a uzol je reprezentovaný ako trieda. Interne používa pole a dátovú štruktúru LinkedList na ukladanie kľúča a hodnoty. HashMap má štyri polia.

Predtým, ako pochopíte interné fungovanie HashMap, musíte poznať metódy hashCode() a equals().

reťazcový formát v jazyku Java

rovná sa():Kontroluje rovnosť dvoch objektov. Porovnáva kľúč, či sú si rovní alebo nie. Je to metóda triedy Object. Dá sa to prepísať. Ak prepíšete metódu equals(), potom je povinné prepísať metódu hashCode().hashCode():Toto je metóda triedy objektov. Vracia pamäťový odkaz objektu v celočíselnej forme. Hodnota získaná z metódy sa použije ako číslo segmentu. Číslo vedra je adresa prvku na mape. Hash kód nulového kľúča je 0.Vedrá:Pole uzla sa nazýva vedierka. Každý uzol má dátovú štruktúru ako LinkedList. Viac ako jeden uzol môže zdieľať rovnaký segment. Môže sa líšiť v kapacite.

Vložte kľúč, pár hodnôt do HashMap

Metódu put() používame na vloženie páru Kľúč a Hodnota do HashMap. Predvolená veľkosť HashMap je 16 (0 až 15).

Príklad

V nasledujúcom príklade chceme do HashMapu vložiť tri páry (kľúč, hodnota).

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

Pozrime sa, na ktorom indexe sa do HashMap uloží pár kľúč, hodnota. Keď zavoláme metódu put(), potom vypočíta hašovací kód kľúča 'Aman'. Predpokladajme, že hash kód 'Aman' je 2657860. Aby sme kľúč uložili do pamäte, musíme vypočítať index.

Výpočet indexu

Index minimalizuje veľkosť poľa. Vzorec na výpočet indexu je:

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

Kde n je veľkosť poľa. Hodnota indexu pre „Aman“ je teda:

mapy java

 Index = 2657860 & (16-1) = 4 

Hodnota 4 je vypočítaná hodnota indexu, kde sa kľúč a hodnota uložia v HashMap.

Hash Collision

Toto je prípad, keď je vypočítaná hodnota indexu rovnaká pre dva alebo viac kľúčov. Poďme vypočítať hash kód pre ďalší kľúč „Sunny“. Predpokladajme, že hash kód pre 'Sunny' je 63281940. Aby sme kľúč uložili do pamäte, musíme vypočítať index pomocou indexového vzorca.

 Index=63281940 & (16-1) = 4 

Hodnota 4 je vypočítaná hodnota indexu, kde bude kľúč uložený v HashMap. V tomto prípade metóda equals() skontroluje, či sú oba kľúče rovnaké alebo nie. Ak sú kľúče rovnaké, nahraďte hodnotu aktuálnou hodnotou. V opačnom prípade pripojte tento objekt uzla k existujúcemu objektu uzla prostredníctvom LinkedList. Preto budú oba kľúče uložené v indexe 4.

Podobne uložíme kľúč „Ritesh“. Predpokladajme, že kód hash pre kľúč je 2349873. Hodnota indexu bude 1. Tento kľúč bude teda uložený v indexe 1.

get() v HashMap

Metóda get() sa používa na získanie hodnoty pomocou jej kľúča. Ak nepoznáte kľúč, hodnotu nenačíta. Keď sa zavolá metóda get(K Key), vypočíta hash kód kľúča.

Herečka Rubina Dilaik

Predpokladajme, že musíme priniesť kľúč 'Aman'. Zavolá sa nasledujúca metóda.

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

Vygeneruje hash kód ako 2657860. Teraz vypočítajte hodnotu indexu 2657860 pomocou indexového vzorca. Hodnota indexu bude 4, ako sme vypočítali vyššie. Metóda get() hľadá hodnotu indexu 4. Porovnáva prvý prvok Key s daným kľúčom. Ak sú oba kľúče rovnaké, vráti hodnotu else check pre ďalší prvok v uzle, ak existuje. V našom scenári sa nájde ako prvý prvok uzla a vráti hodnotu 19.

Prinesme ďalší kľúč „Sunny“.

Hašovací kód kľúča 'Sunny' je 63281940. Vypočítaná hodnota indexu 63281940 je 4, ako sme vypočítali pre metódu put(). Prejdite na index 4 poľa a porovnajte Kľúč prvého prvku s daným kľúčom. Porovnáva aj Keys. V našom scenári je daný kľúč druhým prvkom a nasledujúci uzol je nulový. Porovná druhý prvok Key so zadaným kľúčom a vráti hodnotu 29. Ak ďalší uzol má hodnotu null, vráti hodnotu null.