Hashing er en grunnleggende datastruktur som effektivt lagrer og henter data på en måte som gir rask tilgang. Det innebærer å kartlegge data til en spesifikk indeks i en hash-tabell ved hjelp av en hash-funksjon som muliggjør rask gjenfinning av informasjon basert på nøkkelen. Denne metoden brukes ofte i databaser, c verkende systemer og ulike programmeringsapplikasjoner for å optimere søke- og gjenfinningsoperasjoner.

Datastrukturer – Hashing

Innholdsfortegnelse

java streng til int konvertering

• Hash funksjon
• Hva er en Hash-kollisjon?
• Teknikker for kollisjonsløsning
• Applikasjoner av hashing
• Enkelt problem med hashing
• Middels problem med hashing
• Vanskelig problem med hashing

Hvordan det fungerer:

1. Hash funksjon: Du oppgir dataelementene dine i hash-funksjonen.
2. Hash-kode: Hash-funksjonen knuser dataene og gir en unik hash-kode.
3. Hash-tabell: Hash-koden peker deg deretter til et bestemt sted i hash-tabellen.

Hash funksjon

De hash-funksjon er en funksjon som tar en nøkkel og returnerer en indeks inn i det hasjtabell . Målet med en hash-funksjon er å fordele nøkler jevnt over hash-tabellen, og minimere kollisjoner (når to nøkler tilordnes samme indeks).

Vanlige hashfunksjoner inkluderer:

• Divisjonsmetode: Nøkkel % Hash-tabellstørrelse
• Multiplikasjonsmetode: (Nøkkel * Konstant) % Hash-tabellstørrelse
• Universal hashing: En familie med hash-funksjoner designet for å minimere kollisjoner

Hva er en Hash-kollisjon?

En hash-kollisjon oppstår når to forskjellige nøkler tilordnes den samme indeksen i en hash-tabell. Dette kan skje selv med en god hash-funksjon, spesielt hvis hash-tabellen er full eller tastene er like.

returnerer arrays i java

Årsaker til hasjkollisjoner:

• Dårlig Hash-funksjon: En hash-funksjon som ikke fordeler nøkler jevnt over hash-tabellen kan føre til flere kollisjoner.
• Høy belastningsfaktor: En høy belastningsfaktor (forholdet mellom nøkler og hashtabellstørrelse) øker sannsynligheten for kollisjoner.
• Lignende nøkler: Nøkler som er like i verdi eller struktur er mer sannsynlig å kollidere.

Teknikker for kollisjonsløsning

Det er to typer kollisjonsoppløsningsteknikker:

1. Åpen adressering:
   • Lineær sondering: Søk etter et tomt spor sekvensielt
   • Kvadratisk sondering: Søk etter et tomt spor ved hjelp av en kvadratisk funksjon
2. Lukket adressering:
   • Kjede: Lagre kolliderende nøkler i en koblet liste eller binært søketre ved hver indeks
   • Cuckoo Hashing: Bruk flere hash-funksjoner for å distribuere nøkler

Applikasjoner av hashing

Hash-tabeller brukes i en lang rekke applikasjoner, inkludert:

• Databaser: Lagre og hente data basert på unike nøkler
• Buffer: Lagre ofte brukte data for raskere gjenfinning
• Symboltabeller: Kartlegge identifikatorer til deres verdier i programmeringsspråk
• Nettverksruting: Bestemme den beste banen for datapakker

Hva er Hashing?

Indekskartlegging (eller trivial hashing)

Separat kjetting for kollisjonshåndtering

Åpne adressering for kollisjonshåndtering

Dobbel hashing

Load Factor og Rehashing

Enkelt problem med hashing

• Finn om en matrise er delmengde av en annen matrise
• Union og skjæringspunkt mellom to sammenkoblede lister
• Gitt en matrise A[] og et tall x, se etter par i A[] med sum som x
• Maksimal avstand mellom to forekomster av samme element i array
• Tell maksimalpoeng på samme linje
• Hyppigste element i en matrise
• Finn det eneste repeterende elementet mellom 1 til n-1
• Hvordan sjekke om to gitte sett er usammenhengende?
• Ikke-overlappende sum av to sett
• Sjekk om to matriser er like eller ikke
• Finn manglende elementer i et område
• Minimum antall undersett med distinkte elementer
• Fjern minimum antall elementer slik at det ikke finnes noe felles element i begge arrayene
• Finn par med gitt sum slik at elementer av par er i forskjellige rader
• Tell par med gitt sum
• Tell firedobler fra fire sorterte matriser hvis sum er lik en gitt verdi x
• Sorter elementer etter frekvens
• Finn alle parene (a, b) i en matrise slik at a % b = k
• Grupper ord med samme sett med tegn
• k-te distinkte (eller ikke-repeterende) element i en matrise.

Middels problem med hashing

• Finn reiserute fra en gitt liste over billetter
• Finn antall ansatte under hver ansatt
• Lengste undergruppe med sum delelig med k
• Finn den største undergruppen med 0 sum
• Lengst Økende påfølgende etterfølge
• Tell forskjellige elementer i hvert vindu av størrelse k
• Finn undergruppe med gitt sum | Sett 2 (håndterer negative tall)
• Implementering av vår egen Hash-tabell med Separat Chaining i Java
• Implementering av egen Hash-tabell med Open Addressing Linear Probing i C++
• Minimumsinnsettinger for å danne et palindrom med permutasjoner tillatt
• Maksimal mulig forskjell på to delsett av en matrise
• Sortering ved hjelp av triviell hash-funksjon
• Minste undergruppe med k distinkte tall

Vanskelig problem med hashing

• Klon et binært tre med tilfeldige pekere
• Største undergruppe med like mange 0-ere og 1-ere
• Alle unike trillinger som summerer til en gitt verdi
• Palindrome-substrengspørringer
• Range Queries for frekvenser av matriseelementer
• Elementer som skal legges til slik at alle elementene i et område er tilstede i matrise
• Cuckoo Hashing – Worst case O(1) Lookup!
• Tell undermatriser som har totalt distinkte elementer som er det samme som den opprinnelige matrisen
• Maksimal array fra to gitte arrays holder samme rekkefølge
• Finn summen av alle unike sub-array-sum for en gitt matrise.
• Recamans sekvens
• Lengde på lengste strenge bitoniske undersekvens
• Finn alle dupliserte undertrær
• Finn om det er et rektangel i binær matrise med hjørner som 1

Hurtigkoblinger :

• «Øvningsproblemer» på hashing
• Topp 20 Hashing-teknikk-baserte intervjuspørsmål
• «Videoer» på Hashing