Vad är en associerande matris?

En associerande matris, även kallad en hashtabell eller hashkarta, liknar en standarduppsättning 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 mängder data är en associerande matris ett viktigt inslag i att hjälpa till att sortera och få tillgång till information på ett effektivt sätt.Kärnan i en associativ matris är en standarduppsättning som är indexerad med heltal, som normalt skulle vara fallet.En speciell algoritm som kallas en hashfunktion omvandlar strängindexet till ett heltal för att hitta värdet.Detta är en konsekvent omvandling, så det faktiska heltalindexet behöver aldrig lagras utan beräknas istället utifrån strängen efter behov varje gång.

Den terminologi som används när man hänvisar till en associerande matris kan vara något annorlunda än vad som används när du pratar omen normal matris.Vad som normalt skulle kallas ett index mdash;det numeriska läget för ett element inuti en array mdash;kallas nyckeln.Uppgifterna som är associerade med nyckeln kallas värdet.Detta innebär att en nyckel inom en associerande matris är associerad med ett värde, som korrelerar med ett index som hänvisar till ett element i en standarduppsättning i datastrukturen.

i hjärtat av 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, några utformade för att arbeta på nycklar som är heltal och några som är utformade för att arbeta på nycklar som är strängar.När det gäller en heltalsnyckel är en populär metod att dela upp nyckelvärdet efter storleken på matrisen och använda resten av divisionen för att förhoppningsvis få ett unikt indexvärde.

Hash -funktionen kan vara mycket mer komplexFö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 dela det med ett antal eller 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 nummer från en rad tecken.

När man hanterar en stor mängd nyckelvärde i en associerande matris kallas ett problem som kan uppstå kollision.Kollision inträffar när heltalindexet härrör från en nyckel är identisk med heltalindexet för en annan nyckel.Dessa två nycklar pekar sedan effektivt på samma index i värdet.Det finns olika lösningar på kollision, främst för att den har en stor sannolikhet att hända i de flesta praktiska tillämpningar.

En lösning på kollision är att varje värdeindex faktiskt är en länkad lista så att när mer än en nyckel löser sig till det indexetPlats kan platsen ha 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ära sondverk genom att röra sig 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 associerande arrayen, men den kan också öka den tid som krävs för att leta upp ett värde.