Hashing refererer til processen med at generere et output med fast størrelse fra et input af variabel størrelse ved hjælp af de matematiske formler kendt som hash-funktioner. Denne teknik bestemmer et indeks eller en placering for lagring af et element i en datastruktur.
java arv
Behov for Hash-datastruktur
Mængden af data på internettet vokser eksponentielt hver dag, hvilket gør det svært at gemme det hele effektivt. I den daglige programmering er denne mængde data måske ikke så stor, men alligevel skal den lagres, tilgås og behandles nemt og effektivt. En meget almindelig datastruktur, der bruges til et sådant formål, er Array-datastrukturen.
Nu opstår spørgsmålet, om Array allerede var der, hvad var behovet for en ny datastruktur! Svaret på dette ligger i ordet effektivitet. Selvom lagring i Array tager O(1) tid, at søge i det tager i hvert fald O(log n) tid. Denne tid ser ud til at være lille, men for et stort datasæt kan det forårsage en masse problemer, og det gør igen Array-datastrukturen ineffektiv.
Så nu leder vi efter en datastruktur, der kan gemme dataene og søge i dem i konstant tid, dvs O(1) tid. Sådan kom Hashing-datastrukturen ind i billedet. Med introduktionen af Hash-datastrukturen er det nu muligt nemt at gemme data i konstant tid og også hente dem i konstant tid.
Komponenter af hashing
Der er hovedsageligt tre komponenter af hashing:
- Nøgle: EN Nøgle kan være en hvilken som helst streng eller et heltal, der fødes som input i hash-funktionen, den teknik, der bestemmer et indeks eller en placering for lagring af et element i en datastruktur.
- Hash funktion: Det hash funktion modtager inputnøglen og returnerer indekset for et element i et array kaldet en hash-tabel. Indekset er kendt som hash-indeks .
- Hash tabel: Hash-tabel er en datastruktur, der kortlægger nøgler til værdier ved hjælp af en speciel funktion kaldet en hash-funktion. Hash gemmer dataene på en associativ måde i et array, hvor hver dataværdi har sit eget unikke indeks.
Komponenter af hashing
Hvad er kollision?
Hashing-processen genererer et lille tal for en stor nøgle, så der er mulighed for, at to nøgler kan producere den samme værdi. Situationen, hvor den nyligt indsatte nøgle kortlægger en allerede besat, og den skal håndteres ved hjælp af en eller anden kollisionshåndteringsteknologi.
Kollision i Hashing
webbrowserindstillinger
Fordele ved hashing i datastrukturer
- Nøgleværdi support: Hashing er ideel til implementering af nøgleværdidatastrukturer.
- Hurtig datahentning: Hashing giver mulighed for hurtig adgang til elementer med konstant tidskompleksitet.
- Effektivitet: Indsættelse, sletning og søgning er yderst effektive.
- Reduktion af hukommelsesforbrug: Hashing kræver mindre hukommelse, da det tildeler en fast plads til lagring af elementer.
- Skalerbarhed: Hashing fungerer godt med store datasæt og opretholder konstant adgangstid.
- Sikkerhed og kryptering: Hashing er afgørende for sikker datalagring og integritetsverifikation.
For at lære mere om Hashing, se venligst Introduktion til hashing – datastruktur og algoritmevejledninger