Kaj je zgoščevanje

Je proces pretvorbe predmeta v celoštevilsko vrednost. Vrednost celega števila pomaga pri indeksiranju in hitrejšem iskanju.

Kaj je HashMap

HashMap je del ogrodja zbirke Java. Uporablja tehniko, imenovano zgoščevanje. Izvaja vmesnik zemljevida. Podatke hrani v paru ključ in vrednost. HashMap vsebuje matriko vozlišč, vozlišče pa je predstavljeno kot razred. Interno uporablja matriko in podatkovno strukturo LinkedList za shranjevanje ključa in vrednosti. V HashMap so štiri polja.

Preden razumete notranje delovanje HashMap, se morate zavedati metod hashCode() in equals().

pretvorba niza v int v Javi

enako ():Preveri enakost dveh predmetov. Primerja ključ, ne glede na to, ali sta enaka ali ne. Je metoda razreda Object. Lahko se preglasi. Če preglasite metodo equals(), potem morate obvezno preglasiti metodo hashCode().hashCode():To je metoda razreda objektov. Vrne referenco pomnilnika objekta v obliki celega števila. Vrednost, prejeta iz metode, se uporabi kot številka vedra. Številka vedra je naslov elementa znotraj zemljevida. Zgoščevalna koda ničelnega ključa je 0.Vedra:Niz vozlišča se imenuje vedra. Vsako vozlišče ima podatkovno strukturo, kot je LinkedList. Več kot eno vozlišče lahko deli isto vedro. Lahko se razlikuje po zmogljivosti.

Vstavite par ključev in vrednosti v HashMap

Uporabimo metodo put(), da vstavimo par ključa in vrednosti v HashMap. Privzeta velikost HashMap je 16 (0 do 15).

Primer

V naslednjem primeru želimo v HashMap vstaviti tri pare (ključ, vrednost).

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

Poglejmo, pri katerem indeksu bo par ključ, vrednost shranjen v HashMap. Ko pokličemo metodo put(), izračuna zgoščeno kodo ključa 'Aman.' Recimo, da je zgoščena koda 'Aman' 2657860. Za shranjevanje ključa v pomnilniku moramo izračunati indeks.

Izračun indeksa

Indeks zmanjša velikost matrike. Formula za izračun indeksa je:

tretja normalna oblika

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

Kjer je n velikost polja. Zato je vrednost indeksa za 'Aman':

 Index = 2657860 & (16-1) = 4 

Vrednost 4 je izračunana vrednost indeksa, kamor bosta ključ in vrednost shranjena v HashMap.

Hash Collision

To je v primeru, ko je izračunana vrednost indeksa enaka za dva ali več ključev. Izračunajmo zgoščevalno kodo za drug ključ 'Sunny'. Recimo, da je zgoščevalna koda za 'Sunny' 63281940. Za shranjevanje ključa v pomnilnik moramo izračunati indeks z uporabo formule za indeks.

 Index=63281940 & (16-1) = 4 

Vrednost 4 je izračunana vrednost indeksa, kjer bo ključ shranjen v HashMap. V tem primeru metoda equals() preveri, ali sta oba ključa enaka ali ne. Če so ključi enaki, zamenjajte vrednost s trenutno vrednostjo. V nasprotnem primeru povežite ta objekt vozlišča z obstoječim objektom vozlišča prek LinkedList. Zato bosta oba ključa shranjena pod indeksom 4.

Podobno bomo shranili ključ 'Ritesh'. Recimo, da je zgoščena koda za ključ 2349873. Vrednost indeksa bo 1. Zato bo ta ključ shranjen pri indeksu 1.

java tuple

metoda get() v HashMap

metoda get() se uporablja za pridobivanje vrednosti po njenem ključu. Ne bo pridobil vrednosti, če ne poznate ključa. Ko se pokliče metoda get(K Key), izračuna zgoščeno kodo ključa.

Recimo, da moramo prinesti ključ 'Aman.' Poklicana bo naslednja metoda.

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

Ustvari zgoščeno kodo kot 2657860. Zdaj izračunajte vrednost indeksa 2657860 z uporabo formule indeksa. Vrednost indeksa bo 4, kot smo izračunali zgoraj. metoda get() išče vrednost indeksa 4. Primerja prvi element Key z danim ključem. Če sta oba ključa enaka, potem vrne vrednost sicer preveri za naslednji element v vozlišču, če obstaja. V našem scenariju je najden kot prvi element vozlišča in vrne vrednost 19.

Prinesimo še en ključ 'Sunny'.

Zgoščevalna koda ključa 'Sunny' je 63281940. Izračunana vrednost indeksa 63281940 je 4, kot smo izračunali za metodo put(). Pojdite na indeks 4 matrike in primerjajte ključ prvega elementa z danim ključem. Primerja tudi Keys. V našem scenariju je dani ključ drugi element, naslednji v vozlišču pa je nič. Primerja drugi element Ključ s podanim Ključem in vrne vrednost 29. Vrne ničelno vrednost, če je naslednje vozlišče ničelno.