En associativ matris, även kallad en hashtabell eller hashkarta, liknar en standardmatris förutom att matrisens index 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 associativ array en viktig del för att hjälpa till att sortera och komma åt information på ett effektivt sätt. Kärnan i en associativ matris är en standardmatris som är indexerad med heltal, vilket normalt skulle vara fallet. En speciell algoritm som kallas en hashfunktion omvandlar strängindexet till ett heltalsindex för att hitta värdet. Detta är en konsekvent konvertering, så det faktiska heltalsindexet 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 refererar till en associativ array kan vara något annorlunda än vad som används när man talar om en normal array. Det som normalt skulle kallas ett index – den numeriska platsen för ett element i en array – kallas nyckeln. Data som är associerade med nyckeln kallas värdet. Detta betyder att inom en associativ array är en nyckel associerad med ett värde, som korrelerar med ett index som refererar till ett element i en standardarray i datastrukturen.
I hjärtat av varje associativ array ä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 hash-funktioner, några utformade för att fungera på nycklar som är heltal och några utformade för att fungera på tangenter som är strängar. När det gäller en heltalsnyckel är en populär metod att dividera nyckelvärdet med storleken på arrayen och använda resten av divisionen för att förhoppningsvis få ett unikt indexvärde.
Hashfunktionen kan vara mycket mer komplex för nycklar som är strängar. Vissa metoder inkluderar att lägga till det numeriska värdet för varje tecken i strängen och sedan dividera det med något nummer, eller att bara använda de första tecknen i strängen för att få ett unikt nummer. Det finns många sätt att härleda ett tal från en teckensträng.
När man hanterar en stor mängd nyckel-värdepar i en associativ array, kallas ett problem som kan uppstå kollision. Kollision inträffar när heltalsindexet som härrör från en nyckel är identiskt med heltalsindexet för en annan nyckel. Dessa två nycklar pekar sedan effektivt mot samma index i värdematrisen. Det finns olika lösningar på kollision, främst för att det har stor sannolikhet att inträffa i de flesta praktiska tillämpningar.
En lösning på kollision är att ha varje värdeindex faktiskt vara en länkad lista så att, när mer än en nyckel löser sig till den indexplatsen, kan platsen innehålla mer än ett värde. Detta kallas chaining och är ett enkelt sätt att hantera en kollision, men det kan också sakta ner tiden det tar att hämta informationen. En annan metod för att hantera en kollision kallas linjär sondering. När en kollision inträffar fungerar linjär sondering genom att flytta genom värdematrisen tills ett oanvänt index hittas. Denna lösning kan hjälpa till att hålla data jämnt fördelade i den associativa arrayen, men den kan också öka den tid som krävs för att slå upp ett värde.