Jag tror att det kommer att vara till större hjälp om jag förklarar HashMaps på engelska.

Vad är en HashMap?

En HashMap är en datastruktur som kan mappa vissa nycklar till vissa värden. Nycklarna och värdena kan vara vad som helst. Om jag till exempel skulle göra ett spel skulle jag kunna koppla varje användarnamn till en vänlista, som representeras av en lista med strängar.

Varför använda en HashMap?

HashMaps är mycket snabbare när det gäller att hämta data än arrayer och länkade listor. En sorterad array kan hitta ett visst värde på O(log n) med binär sökning. En HashMap kan dock kontrollera om den innehåller en viss nyckel på O(1). Alla nycklar måste vara unika.

Hur fungerar HashMaps?

HashMaps använder en array i bakgrunden. Varje element i matrisen är en annan datastruktur (vanligtvis en länkad lista eller ett binärt sökträd). HashMap använder en funktion på nyckeln för att bestämma var nyckelns värde ska placeras i matrisen. Om min HashMap till exempel accepterar strängar … kan möjliga hash-funktioner vara:

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.

Det returnerade värdet bestämmer i vilket index värdet placeras i matrisen.

Men vänta, det finns ett problem!

Det är möjligt att det returnerade värdet kommer att ligga utanför matrisens gränser. Därför är det meningen att vi ska modifiera det returnerade värdet med arrayens längd.

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

Kollisioner:

Är det inte möjligt att flera nycklar gör att hashfunktionen genererar samma index? Jo. Om vi till exempel använder den första hashfunktionen som visas ovan i en hashkarta med strängar… kommer två strängar som börjar med samma bokstav att få samma arrayindex.

Detta kallas för en kollision.

Hur hanterar vi kollisioner?

En teknik för hantering av kollisioner kallas Chaining. Eftersom varje element i matrisen är en länkad lista (eller liknande datastruktur) kommer flera nycklar som har samma hashvärde att placeras i samma länkade lista eller ”hink”. Därefter kan hashkartan hämta värden genom att beräkna hashkoden med hashfunktionen och söka i den särskilda länkade listan för att se om den innehåller ett värde med samma nyckel.

En bra hashfunktion måste skrivas för att undvika kollisioner.

Fördelar med Chaining:

-Array kan inte svämma över

-Data kan enkelt tas bort

Nackdelar med Chaining:

-Kan drabbas av en prestandaskada om hinkar innehåller mycket långa länkade listor.

Det totala antalet poster i förhållande till antalet hinkar kallas belastningsfaktor. Om belastningsfaktorn är för låg slösas mycket utrymme bort. Om belastningsfaktorn är för hög går fördelen med hashing förlorad. En bra kompromiss för belastningsfaktorn är 0,75

.