Olen sitä mieltä, että on hyödyllisempää, jos selitän HashMapit englanniksi.

Mikä on HashMap?

HashMap on tietorakenne, joka kykenee kartoittamaan tietyt avaimet tiettyihin arvoihin. Avaimet ja arvot voivat olla mitä tahansa. Jos esimerkiksi tekisin peliä, voisin yhdistää jokaisen käyttäjänimen kaveriluetteloon, jota edustaa merkkijonojen lista.

Miksi käyttää HashMapia?

HashMapit ovat paljon nopeampia tietojen hakemisessa kuin matriisit ja linkitetyt listat. Lajiteltu array voisi löytää tietyn arvon O(log n):ssä binäärihaulla. HashMap voi kuitenkin tarkistaa, sisältääkö se tietyn avaimen O(1):ssä. Kaikkien avainten on oltava yksilöllisiä.

Miten HashMapit toimivat?

HashMapit käyttävät taustalla arraya. Jokainen array:n elementti on toinen tietorakenne (yleensä linkitetty lista tai binäärinen hakupuu). HashMap käyttää avaimeen kohdistuvaa funktiota määrittämään, mihin avaimen arvo sijoitetaan matriisissa. Jos esimerkiksi HashMapini hyväksyy merkkijonoja…mahdolliset hash-funktiot voivat olla:

A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.

Palautettu arvo määrittelee indeksin, jolla arvo menee matriisiin.

Mutta odota, tässä on ongelma!

On mahdollista, että palautettu arvo on matriisin rajojen ulkopuolella. Siksi meidän on tarkoitus muokata palautettua arvoa arrayjen pituudella.

return Math.abs(number%hashMapArray.length);

Kolariot:

Eikö ole mahdollista, että useat avaimet saavat hash-funktion tuottamaan saman indeksin? Kyllä. Jos esimerkiksi käytämme edellä esitettyä ensimmäistä hash-funktiota merkkijonojen hash-kartassa…kaikki kaksi samalla kirjaimella alkavaa merkkijonoa saavat saman array-indeksin.

Tätä kutsutaan törmäykseksi.

Miten käsittelemme törmäyksiä?

Yksi törmäysten käsittelytekniikaksi kutsutaan ketjuttamista. Koska matriisin jokainen elementti on linkitetty lista (tai vastaava tietorakenne), useat avaimet, joilla on sama hash-arvo, sijoitetaan samaan linkitettyyn listaan tai ”ämpäriin”. Tämän jälkeen hash map pystyy hakemaan arvoja laskemalla hash-koodin hash-funktiolla ja etsimällä tietystä linkitetystä listasta, sisältääkö se arvon, jolla on sama avain.

Hyvä hash-funktio on kirjoitettava törmäysten välttämiseksi.

Ketjuttamisen edut:

-muisti ei voi ylivuotaa

-tieto voidaan helposti poistaa

Ketjuttamisen haitat:

-mahdollisesti kärsii suorituskyvyn heikkenemisestä, jos ämpäreissä on hyvin pitkiä linkitettyjä listoja.

Tietueiden kokonaislukumäärän suhdetta ämpäreiden lukumäärään sanotaan kuormittavuuskertoimeksi. Jos kuormituskerroin on liian pieni, paljon tilaa menee hukkaan. Jos kuormituskerroin on liian suuri, hashingin etu menetetään. Hyvä kompromissi kuormituskertoimen suhteen on .75

.