Hashing er en grundlæggende datastruktur, der effektivt gemmer og henter data på en måde, der giver mulighed for hurtig adgang. Det involverer at kortlægge data til et specifikt indeks i en hash-tabel ved hjælp af en hash funktion der muliggør hurtig genfinding af information baseret på dens nøgle. Denne metode er almindeligt anvendt i databaser, c ømme systemer og forskellige programmeringsapplikationer for at optimere søge- og genfindingsoperationer.

Datastrukturer – Hashing

Indholdsfortegnelse

java streng til int konvertering

• Hash funktion
• Hvad er en Hash-kollision?
• Teknikker til løsning af kollisioner
• Anvendelser af hashing
• Let problem med hashing
• Medium problem med hashing
• Svært problem med hashing

Hvordan det virker:

1. Hash funktion: Du angiver dine dataelementer i hash-funktionen.
2. Hash kode: Hash-funktionen knuser dataene og giver en unik hash-kode.
3. Hash tabel: Hash-koden peger dig derefter til en bestemt placering i hash-tabellen.

Hash funktion

Det hash funktion er en funktion, der tager en nøgle og returnerer en indeks ind i hash tabel . Målet med en hash-funktion er at fordele nøgler jævnt over hash-tabellen, hvilket minimerer kollisioner (når to nøgler er knyttet til det samme indeks).

Almindelige hash-funktioner omfatter:

• Opdelingsmetode: Nøgle % Hash tabelstørrelse
• Multiplikationsmetode: (Nøgle * Konstant) % Hash-tabelstørrelse
• Universal hashing: En familie af hash-funktioner designet til at minimere kollisioner

Hvad er en Hash-kollision?

En hash-kollision opstår, når to forskellige nøgler er knyttet til det samme indeks i en hash-tabel. Dette kan ske selv med en god hash-funktion, især hvis hash-tabellen er fuld, eller tasterne ligner hinanden.

java input streng

Årsager til hashkollisioner:

• Dårlig hash-funktion: En hash-funktion, der ikke fordeler nøgler jævnt over hash-tabellen, kan føre til flere kollisioner.
• Høj belastningsfaktor: En høj belastningsfaktor (forholdet mellem nøgler og hash-tabelstørrelse) øger sandsynligheden for kollisioner.
• Lignende nøgler: Nøgler, der ligner hinanden i værdi eller struktur, er mere tilbøjelige til at støde sammen.

Teknikker til løsning af kollisioner

Der er to typer kollisionsopløsningsteknikker:

1. Åbn adressering:
   • Lineær sondering: Søg efter en tom plads sekventielt
   • Kvadratisk sondering: Søg efter en tom plads ved hjælp af en kvadratisk funktion
2. Lukket adresse:
   • Kædning: Gem kolliderende nøgler i en sammenkædet liste eller binært søgetræ ved hvert indeks
   • Gøg hashing: Brug flere hash-funktioner til at distribuere nøgler

Anvendelser af hashing

Hash-tabeller bruges i en lang række applikationer, herunder:

• Databaser: Lagring og hentning af data baseret på unikke nøgler
• Caching: Lagring af ofte anvendte data for hurtigere hentning
• Symboltabeller: Kortlægning af identifikatorer til deres værdier i programmeringssprog
• Netværksrouting: Bestemmelse af den bedste vej til datapakker

Hvad er Hashing?

Index Mapping (eller Trivial Hashing)

Separat kæde til kollisionshåndtering

Åbn adressering for kollisionshåndtering

Dobbelt hashing

Load Factor og Rehashing

Let problem med hashing

• Find, om et array er en delmængde af et andet array
• Forening og skæring af to forbundne lister
• Givet en matrix A[] og et tal x, tjek for par i A[] med sum som x
• Maksimal afstand mellem to forekomster af samme element i array
• Tæl maksimale point på samme linje
• Hyppigste element i et array
• Find det eneste gentagne element mellem 1 til n-1
• Hvordan kontrollerer man, om to givne sæt er usammenhængende?
• Ikke-overlappende sum af to sæt
• Tjek, om to arrays er ens eller ej
• Find manglende elementer i et område
• Minimum antal delmængder med forskellige elementer
• Fjern minimumsantallet af elementer, således at der ikke findes et fælles element i begge array
• Find par med given sum, således at elementer af par er i forskellige rækker
• Tæl par med given sum
• Tæl firdobler fra fire sorterede arrays, hvis sum er lig med en given værdi x
• Sorter elementer efter frekvens
• Find alle par (a, b) i en matrix, således at a % b = k
• Grupper ord med samme sæt tegn
• k-te distinkte (eller ikke-gentagende) element i en matrix.

Medium problem med hashing

• Find rejseplan fra en given liste over billetter
• Find antallet af medarbejdere under hver medarbejder
• Længste underarray med sum delelig med k
• Find den største subarray med 0 sum
• Længst Stigende på hinanden følgende efterfølger
• Tæl forskellige elementer i hvert vindue af størrelse k
• Find subarray med given sum | Sæt 2 (håndterer negative tal)
• Implementering af vores egen Hash-tabel med Separat Chaining i Java
• Implementering af egen Hash-tabel med Open Addressing Linear Probing i C++
• Minimumsindsættelser for at danne et palindrom med permutationer tilladt
• Maksimal mulig forskel på to delmængder af et array
• Sortering ved hjælp af triviel hash-funktion
• Mindste underarray med k distinkte tal

Svært problem med hashing

• Klon et binært træ med tilfældige pointere
• Største underarray med lige mange 0'ere og 1'ere
• Alle unikke trillinger, der summerer op til en given værdi
• Palindrom-understrengsforespørgsler
• Range Queries for frekvenser af array-elementer
• Elementer, der skal tilføjes, så alle elementer i et område er til stede i array
• Cuckoo Hashing – Worst case O(1) Opslag!
• Tæl subarrays med totalt forskellige elementer som det oprindelige array
• Maksimal array fra to givne arrays holder samme rækkefølge
• Find summen af ​​alle unikke sub-array-sum for en given matrix.
• Recamans sekvens
• Længden af ​​den længste strenge bitoniske undersekvens
• Find alle duplikerede undertræer
• Find om der er et rektangel i binær matrix med hjørner som 1

Hurtige links :

• 'Practice Problemer' på Hashing
• Top 20 Hashing-teknik-baserede interviewspørgsmål
• 'Videoer' på Hashing