Vad är en associerande grupp?
En associativ matris, även kallad hash-tabell eller hash-karta, liknar en standardmatris förutom att indexet för matrisen kan vara en sträng istället för ett heltal. I många databasapplikationer och i andra program som hanterar stora datamängder är en associerande grupp en viktig del för att hjälpa till att sortera och få tillgång till information på ett effektivt sätt. I kärnan i en associerande grupp finns en standardgrupp som är indexerad med heltal, som normalt skulle vara fallet. En speciell algoritm som kallas en hash-funktion konverterar strängindex till ett heltalindex för att hitta värdet. Detta är en konsekvent konvertering, så det faktiska heltalindexet behöver aldrig lagras utan beräknas istället från strängen efter behov varje gång.
Terminologin som används när man hänvisar till en associativ matris kan vara något annorlunda än vad som används när man talar om en normal matris. Det som normalt skulle kallas ett index - det numeriska läget för ett element i en matris - kallas nyckeln. Data som är associerade med nyckeln kallas värdet. Detta innebär att en nyckel i en associerande matris är associerad med ett värde, som korrelerar med ett index som refererar till ett element i en standardmatris i datastrukturen.
Kärnan i varje associerande grupp är hashfunktionen. Detta är en algoritm som används för att bestämma det numeriska indexet för ett värde baserat på nyckeln. Det finns flera typer av hashfunktioner, vissa är utformade för att fungera på nycklar som är heltal och andra utformade för att arbeta med tangenter som är strängar. När det gäller en heltalsknapp är en populär metod att dela nyckelvärdet med storleken på matrisen och använda resten av divisionen för att förhoppningsvis få ett unikt indexvärde.
Hashfunktionen kan vara mycket mer komplex för tangenter som är strängar. Vissa metoder inkluderar att lägga till det numeriska värdet för varje tecken i strängen och sedan dela det med något nummer, eller använda bara de första tecknen i strängen för att få ett unikt nummer. Det finns många sätt att härleda ett nummer från en rad tecken.
När man hanterar en stor mängd nyckelvärdespar i en associativ matris kallas ett problem som kan uppstå kollision. Kollision inträffar när heltalindexet härrörande från en nyckel är identiskt med heltalindexet för en annan nyckel. Dessa två tangenter pekar sedan effektivt på samma index i värdearrayen. Det finns olika lösningar på kollision, främst för att det är mycket troligt att det sker i de flesta praktiska tillämpningar.
En lösning på kollision är att varje värdeindex faktiskt ska vara en länkad lista så att när mer än en nyckel löser den indexplatsen kan platsen innehålla mer än ett värde. Detta kallas kedja och är ett enkelt sätt att hantera en kollision, även om det också kan bromsa tiden det tar att hämta informationen. En annan metod för att hantera en kollision kallas linjär sond. När en kollision inträffar fungerar linjär sondning genom att röra sig genom värdesystemet tills ett oanvänt index hittas. Denna lösning kan hjälpa till att hålla informationen jämnt fördelad i den associerande matrisen, men den kan också öka den tid som krävs för att slå upp ett värde.