Hvad er en associativ matrix?

En associativ matrix, også kaldet et hash -tabel eller hash -kort, svarer til 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 gemmes, men beregnes i stedet ud fra strengen efter behov hver gang.

Den terminologi, der bruges, når man henviser til en associativ matrix, kan være lidt anderledes end hvad der bruges, når man taler omEn normal matrix.Hvad ville normalt blive kaldt et indeks mdash;den numeriske placering af et element inde i en matrix mdash;kaldes nøglen.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.

I hjertet af 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 kompleksFor nøgler, der er strenge.Nogle metoder inkluderer tilføjelse af den numeriske værdi af hver karakter i strengen og derefter opdeling af det med et eller andet nummer eller kun ved hjælp af de første par tegn på strengen for at få et unikt tal.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 en 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, placeringen kan 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 fordelt i den associative array, men den kan også øge den tid, der kræves for at slå en værdi op.