Hvad er en associativ matrix?
En associativ matrix, også kaldet et hash -tabel eller hash -kort, ligner en standardarray undtagen indekset for matrixen 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 en associativ matrix et vigtigt element i at hjælpe med at sortere og få adgang til information på en effektiv måde. Kernen i en associativ matrix er en standardarray, der er indekseret 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 konsekvent konvertering, så det faktiske heltalindeks behøver aldrig at blive gemt, men beregnes i stedet ud fra strengen efter behov hver gang.
Den anvendte terminologi, der bruges, når man henviser til en associativ matrix, kan være lidt anderledes end hvad der bruges, når man taler om en normal matrix. Hvad der normalt kaldes et indeks - den numeriske placering af et element inde i en matrix - kaldesnøgle. De data, der er knyttet til nøglen, kaldes værdien. Dette betyder, at en nøgle inden for en associativ matrix er forbundet med en værdi, der korrelerer med et indeks, der refererer til et element i en standardarray i datastrukturen.
Kernen i enhver associativ matrix 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 hashfunktioner, nogle designet til at fungere på nøgler, der er heltal og nogle designet til at arbejde på nøgler, der er strenge. I tilfælde af en heltalnøgle er en populær metode at opdele nøgleværdien med størrelsen på matrixen og bruge resten af divisionen til forhåbentlig at få en unik indeksværdi.
Hash -funktionen kan være meget mere kompleks for nøgler, der er strenge. Nogle metoder inkluderer at tilføje den numeriske værdi af hver karakter i strengen og derefter dele den med et eller andet nummer,Eller kun bruge de første par tegn på strengen for at få et unikt nummer. Der er mange måder at udlede et tal fra en række tegn.
Når man beskæftiger sig med en stor mængde nøgleværdipar i en associativ matrix, kaldes et problem, der kan opstå, kollision. Kollision sker, når heltalindekset, der stammer fra en nøgle, er identisk med heltalindekset for en anden nøgle. Disse to taster peger derefter effektivt på det samme indeks i værdienarrayet. Der er forskellige løsninger på kollision, hovedsageligt fordi det har stor sandsynlighed for at ske i de fleste praktiske anvendelser.
En løsning på kollision er at have hvert værdiindeks faktisk være en tilknyttet liste, så når mere end en nøgle løser det indeksplacering, kan placeringen indeholde mere end en værdi. Dette kaldes kæde og er en enkel måde at håndtere en kollision på, skønt det også kan bremse den tid, det tager at hente oplysningerne. En anden metode til håndtering af en kollision kaldes lineær sondering.Når der opstår en kollision, fungerer lineær sondering ved at bevæge sig gennem værdiens array, indtil der findes et ubrugt indeks. Denne løsning kan hjælpe med at holde dataene jævnt distribueret i den associative array, men den kan også øge den tid, der kræves for at slå en værdi op.