Hva er et assosiativt utvalg?
En assosiativ matrise, også kalt et hasjtabell eller hasjkart, ligner på en standard matrise bortsett fra indeksen til matrisen kan være en streng i stedet for et heltall.I mange databaseapplikasjoner og i andre programmer som omhandler store datamengder, er et assosiativt utvalg et viktig element i å bidra til å sortere og få tilgang til informasjon på en effektiv måte.Kjernen i et assosiativt utvalg er en standard matrise som indekseres med heltall, som normalt vil være tilfelle.En spesiell algoritme kalt en hasjfunksjon konverterer strengindeksen til en heltallindeks for å finne verdien.Dette er en konsekvent 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 en assosiativ matrise kan være litt annerledes enn det som brukes når du snakker omet normalt utvalg.Det som normalt vil bli kalt en indeks mdash;den numeriske plasseringen av et element inne i en matrise mdash;kalles nøkkelen.Dataene knyttet til nøkkelen kalles verdien.Dette betyr at en nøkkel i en assosiativ matrise er en nøkkel assosiert med en verdi, som korrelerer med en indeks som refererer til et element i en standard matrise i datastrukturen.
i hjertet av alle assosiative matriser er hashfunksjonen.Dette er en algoritme som brukes til å bestemme den numeriske indeksen for en verdi basert på nøkkelen.Det er flere typer hashfunksjoner, noen designet for å operere på nøkler som er heltall og noen designet for å fungere på nøkler som er strenger.Når detFor nøkler som er strenger.Noen metoder inkluderer å legge til den numeriske verdien av hvert tegn i strengen og deretter dele den med et antall, eller bare bruke de første par tegnene i strengen for å få et unikt tall.Det er mange måter å utlede et tall fra en rekke tegn.
Når du arbeider med en stor mengde nøkkelverdipar i et assosiativt utvalg, kalles et problem som kan oppstå.Kollisjon skjer når heltallindeksen avledet fra en nøkkel er identisk med heltallindeksen til en annen nøkkel.Disse to tastene peker deretter effektivt på den samme indeksen i verdistyret.Det er forskjellige løsninger på kollisjon, hovedsakelig fordi det har stor sannsynlighet for å skje i de fleste praktiske anvendelser.
En løsning på kollisjon er å ha hver verdiindeks faktisk være en koblet liste, slik at når mer enn en nøkkel løser seg til den indeksenPlassering, plasseringen kan inneholde mer enn en 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 det oppstår en kollisjon, fungerer lineær sondering ved å bevege seg gjennom verdistyret til en ubrukt indeks er funnet.Denne løsningen kan bidra til å holde dataene jevnt fordelt i det assosiative matrisen, men de kan også øke tiden som kreves for å slå opp en verdi.