Jeg tror, at det vil være mere nyttigt, hvis jeg forklarer HashMaps på engelsk.

Hvad er en HashMap?

En HashMap er en datastruktur, der er i stand til at mappe bestemte nøgler til bestemte værdier. Nøglerne og værdierne kan være hvad som helst. Hvis jeg f.eks. lavede et spil, kunne jeg knytte hvert brugernavn til en venneliste, repræsenteret ved en liste af strenge.

Hvorfor bruge en HashMap?

HashMaps er meget hurtigere til at hente data end arrays og linkede lister. Et sorteret array kan finde en bestemt værdi på O(log n) med binær søgning. Et HashMap kan imidlertid kontrollere, om det indeholder en bestemt nøgle på O(1). Alle nøgler skal være unikke.

Hvordan fungerer HashMaps?

HashMaps bruger et array i baggrunden. Hvert element i arrayet er en anden datastruktur (normalt en linket liste eller et binært søgetræ). HashMap bruger en funktion på nøglen til at bestemme, hvor nøglenes værdi skal placeres i arrayet. Hvis min HashMap f.eks. accepterer Strings … mulige hash-funktioner kan være:

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.

Den returnerede værdi bestemmer det indeks, hvor værdien skal placeres i arrayet.

Men vent! Der er et problem!

Det er muligt, at den returnerede værdi vil være uden for arrayets grænser. Derfor er det meningen, at vi skal modificere den returnerede værdi med arrayets længde.

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

Kollisioner:

Er det ikke muligt, at flere nøgler vil få hashfunktionen til at generere det samme indeks? Jo. Hvis vi f.eks. brugte den første hashfunktion, der er vist ovenfor, i et hashmap af strenge … vil to strenge, der begynder med det samme bogstav, få det samme arrayindeks.

Dette kaldes en kollision.

Hvordan håndterer vi kollisioner?

En teknik til håndtering af kollisioner kaldes Chaining. Da hvert element i arrayet er en linket liste (eller en lignende datastruktur), vil flere nøgler, der har den samme hash-værdi, blive placeret i den samme linkede liste eller “spand”. Herefter kan hashkortet hente værdier ved at beregne hashkoden med hashfunktionen og søge i den pågældende linkede liste for at se, om den indeholder en værdi med den samme nøgle.

En god hashfunktion skal skrives for at undgå kollisioner.

Fordelene ved Chaining:

-Arrayet kan ikke løbe over

-Data kan let fjernes

Nedlemmer ved Chaining:

-Kan lide et ydelsesmæssigt tab, hvis buckets indeholder meget lange linkede lister.

Det samlede antal poster i forhold til antallet af buckets kaldes belastningsfaktoren. Hvis belastningsfaktoren er for lav, spildes der meget plads. Hvis belastningsfaktoren er for høj, går fordelen ved hashing tabt. Et godt kompromis for belastningsfaktoren er .75