Hva er en assosiert matrise?
Et assosiativt array, også kalt en hasjtabell eller hasjkart, ligner en standard matrise bortsett fra at indeksen til arrayen kan være en streng i stedet for et heltall. I mange databaseapplikasjoner og i andre programmer som håndterer store datamengder, er et assosiativt utvalg et viktig element i å hjelpe til med å sortere og få tilgang til informasjon på en effektiv måte. Kjernen i et assosiativt utvalg er en standardgruppe som er indeksert med heltall, som normalt vil være tilfelle. En spesiell algoritme kalt en hasjfunksjon konverterer strengindeksen til et heltallindeks for å finne verdien. Dette er en jevn konvertering, så den faktiske heltallindeksen trenger aldri å lagres, men beregnes i stedet fra strengen etter behov hver gang.
Terminologien som brukes når du refererer til et assosiativt utvalg, kan være litt annerledes enn det som brukes når du snakker om en normal matrise. Det som normalt vil bli kalt en indeks - den numeriske plasseringen av et element i en matrise - kalles nøkkelen. Dataene som er knyttet til nøkkelen kalles verdien. Dette betyr at i en assosiativ matrise er en nøkkel assosiert med en verdi, som korrelerer med en indeks som refererer til et element i en standardgruppe i datastrukturen.
Innerst i hvert assosiativt utvalg er hasjfunksjonen. Dette er en algoritme som brukes til å bestemme den numeriske indeksen for en verdi basert på nøkkelen. Det er flere typer hasjfunksjoner, noen designet for å fungere på taster som er heltall, og noen er designet for å fungere på taster som er strenger. Når det gjelder en heltallsnøkkel, er en populær metode å dele nøkkelverdien på størrelsen på matrisen og bruke resten av divisjonen for å forhåpentligvis få en unik indeksverdi.
Hashfunksjonen kan være mye mer kompleks for taster som er strenger. Noen metoder inkluderer å legge til den numeriske verdien for hvert tegn i strengen og deretter dele den med noe nummer, eller bare bruke de første tegnene i strengen for å få et unikt tall. Det er mange måter å hente et nummer fra en streng med tegn.
Når du arbeider med en stor mengde nøkkelverdipar i et assosiativt utvalg, kalles et kollisjon. Kollisjon skjer når heltalindeksen avledet fra en nøkkel er identisk med heltallindeksen til en annen nøkkel. Disse to tastene peker da effektivt på den samme indeksen i verdisamlingen. Det er forskjellige løsninger på kollisjon, hovedsakelig fordi det er stor sannsynlighet for å skje i de fleste praktiske bruksområder.
En løsning på kollisjon er å ha hver verdiindeks til å være en koblet liste, slik at når mer enn en nøkkel løser seg til den indeksposisjonen, kan plasseringen inneholde mer enn én verdi. Dette kalles kjetting og er en enkel måte å håndtere en kollisjon på, selv om det også kan bremse tiden det tar å hente informasjonen. En annen metode for å håndtere en kollisjon kalles lineær sondering. Når en kollisjon oppstår, fungerer lineær sondering ved å bevege seg gjennom verdisamlingen til en ubrukt indeks blir funnet. Denne løsningen kan bidra til å holde dataene jevnt fordelt i den tilknyttede matrisen, men den kan også øke tiden som kreves for å slå opp en verdi.