Hvad er en associerende matrix?

Et associativt array, også kaldet en hash-tabel eller hash-kort, ligner en standard array, bortset fra at indekset for arrayet kan være en streng i stedet for et heltal. I mange databaseapplikationer og i andre programmer, der beskæftiger sig med store mængder data, er et tilknyttet array et vigtigt element i at hjælpe med at sortere og få adgang til oplysninger på en effektiv måde. I kernen af ​​et associativt array er en standardgruppe, der indekseres med heltal, som normalt ville være tilfældet. En speciel algoritme kaldet en hash-funktion konverterer strengindekset til et heltalindeks for at finde værdien. Dette er en konsistent konvertering, så det faktiske heltalindeks behøver aldrig at gemmes, men beregnes i stedet ud fra strengen efter behov hver gang.

Terminologien, der bruges, når der henvises til et tilknyttet array, kan være lidt anderledes end det, der bruges, når man taler om et normalt array. Det, der normalt kaldes et indeks - den numeriske placering af et element i en matrix - kaldes nøglen. De data, der er knyttet til nøglen, kaldes værdien. Dette betyder, at en nøgle i en tilknyttet matrix er knyttet til en værdi, der korrelerer med et indeks, der refererer til et element i en standardgruppe i datastrukturen.

I hjertet af enhver tilknyttet række er hash-funktionen. Dette er en algoritme, der bruges til at bestemme det numeriske indeks for en værdi baseret på nøglen. Der er flere typer hash-funktioner, nogle er designet til at fungere på taster, der er heltal, og nogle er designet til at arbejde på taster, der er strenge. I tilfælde af en heltalstast er en populær metode at opdele nøgleværdien med størrelsen på matrixen og bruge resten af ​​opdelingen til forhåbentlig at få en unik indeksværdi.

Hashfunktionen kan være meget mere kompleks for taster, der er strenge. Nogle metoder inkluderer at tilføje den numeriske værdi af hvert tegn i strengen og derefter dele den med et vist antal eller kun bruge de første par tegn i strengen for at få et unikt tal. Der er mange måder at udlede et nummer fra en streng med tegn.

Når man beskæftiger sig med en stor mængde nøgleværdipar i en tilknyttet matrix, kaldes et problem, der kollisioner. Kollision sker, når heltalindekset fra en nøgle er identisk med heltalets indeks for en anden nøgle. Disse to nøgler peger derefter effektivt på det samme indeks i værdierrayet. Der er forskellige løsninger på kollision, hovedsageligt fordi det er meget sandsynligt, at det sker i de fleste praktiske anvendelser.

En løsning på kollision er, at hvert værdiindeks faktisk skal være en sammenkoblet liste, så når mere end en nøgle løser den indeksplacering, kan placeringen indeholde mere end en værdi. Dette kaldes chaining og er en enkel måde at håndtere en kollision på, selvom det også kan bremse den tid det tager at hente informationen. En anden metode til at håndtere en kollision kaldes lineær sondering. Når der opstår en kollision, fungerer lineær sondering ved at bevæge sig gennem værdisættet, indtil der findes et ubrugt indeks. Denne løsning kan hjælpe med at holde dataene jævnt fordelt i det associerende array, men det kan også øge den tid, der kræves for at finde en værdi.