Hiszem, hogy hasznosabb lesz, ha a HashMapokat magyarul magyarázom el.

Mi az a HashMap?

A HashMap egy olyan adatszerkezet, amely képes bizonyos kulcsokat bizonyos értékekhez rendelni. A kulcsok és az értékek bármi lehet. Például, ha egy játékot készítenék, akkor minden felhasználónevet összekapcsolhatnék egy barátlistával, amelyet egy List of Strings képvisel.

Miért használjunk HashMapot?

A HashMapok sokkal gyorsabbak az adatok visszakeresésében, mint a tömbök és a linkelt listák. Egy rendezett tömb bináris kereséssel O(log n) alatt találhat meg egy adott értéket. Egy HashMap azonban O(1) alatt tudja ellenőrizni, hogy tartalmaz-e egy adott kulcsot. Minden kulcsnak egyedinek kell lennie.

Hogyan működnek a HashMapok?

A HashMapok egy tömböt használnak a háttérben. A tömb minden eleme egy másik adatszerkezet (általában egy összekapcsolt lista vagy bináris keresőfa). A HashMap egy függvényt használ a kulcson annak meghatározására, hogy a kulcs értékét hol helyezze el a tömbben. Például, ha a HashMapom stringeket fogad el…a lehetséges hash függvények a következők lehetnek:

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.

A visszaadott érték fogja meghatározni az indexet, amelyben az érték a tömbbe kerül.

De várj! Van egy probléma!

Ez lehetséges, hogy a visszaadott érték a tömb határain kívül esik. Ezért a visszaadott értéket a tömb hosszával kell módosítanunk.

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

Kollíziók:

Nem lehetséges, hogy több kulcs miatt a hash függvény ugyanazt az indexet generálja? Igen. Például, ha a fentebb bemutatott első hash függvényt használnánk egy stringekből álló hash térképben…bármely két, azonos betűvel kezdődő string ugyanazt a tömbindexet fogja kapni.

Ezt hívjuk ütközésnek.

Hogyan kezeljük az ütközéseket?

Az egyik ütközéskezelési technika az úgynevezett láncolás. Mivel a tömb minden eleme egy összekapcsolt lista (vagy hasonló adatszerkezet), több olyan kulcs, amelynek ugyanaz a hash-értéke, ugyanabba az összekapcsolt listába vagy “vödörbe” kerül. Ezután a hash-térkép úgy tudja visszakeresni az értékeket, hogy a hash-függvénnyel kiszámítja a hash-kódot, és megkeresi az adott összekapcsolt listában, hogy van-e benne azonos kulcsú érték.

A jó hash-függvényt úgy kell megírni, hogy elkerüljük az ütközéseket.

A láncolás előnyei:

-A tömb nem tud túlcsordulni

-Az adatok könnyen eltávolíthatók

A láncolás hátrányai:

-Teljesítménycsökkenést szenvedhet, ha a vödrök nagyon hosszú kapcsolt listákat tartalmaznak.

A bejegyzések teljes száma a vödrök számához képest az úgynevezett terhelési tényező. Ha a terhelési tényező túl alacsony, sok helyet pazarolunk el. Ha a terhelési tényező túl magas, a hashing előnye elvész. A terhelési tényezőre vonatkozó jó kompromisszum a .75

.