Hashing refererer til prosessen med å generere en utdata med fast størrelse fra en inngang av variabel størrelse ved å bruke de matematiske formlene kjent som hash-funksjoner. Denne teknikken bestemmer en indeks eller plassering for lagring av et element i en datastruktur.

java arv

Behov for Hash-datastruktur

Mengden data på internett vokser eksponentielt hver dag, noe som gjør det vanskelig å lagre alt effektivt. I dag-til-dag programmering er kanskje ikke denne mengden data så stor, men likevel må den lagres, få tilgang til og behandles enkelt og effektivt. En veldig vanlig datastruktur som brukes til et slikt formål er Array-datastrukturen.

Nå oppstår spørsmålet om Array allerede var der, hva var behovet for en ny datastruktur! Svaret på dette ligger i ordet effektivitet. Selv om lagring i Array tar O(1) tid, å søke i det tar i det minste O(log n) tid. Denne tiden ser ut til å være liten, men for et stort datasett kan det forårsake mange problemer, og dette gjør igjen Array-datastrukturen ineffektiv.

Så nå ser vi etter en datastruktur som kan lagre dataene og søke i dem i konstant tid, dvs. i O(1) tid. Slik kom hashing-datastrukturen inn i bildet. Med introduksjonen av Hash-datastrukturen er det nå mulig å enkelt lagre data i konstant tid og også hente dem i konstant tid.

Komponenter av hashing

Det er hovedsakelig tre komponenter av hashing:

1. Nøkkel: EN Nøkkel kan være hva som helst streng eller heltall som mates som input i hash-funksjonen, teknikken som bestemmer en indeks eller plassering for lagring av et element i en datastruktur.
2. Hash funksjon: De hash-funksjon mottar inngangsnøkkelen og returnerer indeksen til et element i en matrise kalt en hash-tabell. Indeksen er kjent som hasj-indeks .
3. Hash-tabell: Hash-tabell er en datastruktur som tilordner nøkler til verdier ved hjelp av en spesiell funksjon kalt en hash-funksjon. Hash lagrer dataene på en assosiativ måte i en matrise der hver dataverdi har sin egen unike indeks.

Komponenter av hashing

Hva er kollisjon?

Hashing-prosessen genererer et lite tall for en stor nøkkel, så det er en mulighet for at to nøkler kan produsere samme verdi. Situasjonen der den nylig innsatte nøkkelen kartlegger en allerede opptatt, og den må håndteres ved hjelp av en eller annen kollisjonshåndteringsteknologi.

Kollisjon i Hashing

git rebase

Fordeler med hashing i datastrukturer

• Nøkkelverdistøtte: Hashing er ideell for å implementere nøkkelverdi-datastrukturer.
• Rask datainnhenting: Hashing gir rask tilgang til elementer med konstant kompleksitet.
• Effektivitet: Innsetting, sletting og søkeoperasjoner er svært effektive.
• Minnebruk reduksjon: Hashing krever mindre minne da det tildeler en fast plass for lagring av elementer.
• Skalerbarhet: Hashing fungerer bra med store datasett, og opprettholder konstant tilgangstid.
• Sikkerhet og kryptering: Hashing er avgjørende for sikker datalagring og integritetsverifisering.

For å lære mer om hashing, se Introduksjon til hashing – veiledninger for datastruktur og algoritme