En guide til foldeteknikken i Java

1. Introduktion

I denne vejledning overvejer vi hashing-teknikker, der anvendes i forskellige datastrukturer, der giver konstant tidsadgang til deres elementer.

Vi diskuterer mere detaljeret den såkaldte foldeteknik og give en kort introduktion til mellem-kvadrat og binning-teknikker.

2. Oversigt

Når vi vælger datastrukturer til lagring af objekter, er en af ​​overvejelserne, om vi har brug for hurtig adgang til dem.

Java-hjælpepakken tilbyder os en hel del datastrukturer til lagring af vores objekter. For mere information om datastrukturer henvises til vores Java-samling-kompilationsside, der indeholder guider om flere af dem.

Som vi ved, nogle af disse datastrukturer giver os mulighed for at hente deres elementer i konstant tid, uafhængigt af antallet af elementer, de indeholder.

Det enkleste er sandsynligvis arrayet. Faktisk får vi adgang til elementer i arrayet ved hjælp af deres indeks. Adgangstiden afhænger naturligvis ikke af arrayets størrelse. Faktisk bag scenen bruger mange datastrukturer stærkt arrays.

Problemet er, at matrixindekserne skal være numeriske, mens vi ofte foretrækker at manipulere disse datastrukturer med objekter.

For at løse dette problem forsøger mange datastrukturer at tildele en numerisk værdi, der kan fungere som et matrixindeks til objekter. Vi kalder denne værdi a hash-værdi eller simpelthen en hash.

3. Hashing

Hashing er en transformation af et objekt til en numerisk værdi. Funktioner, der udfører disse transformationer kaldes hash-funktioner.

Af hensyn til enkelheden skal vi overveje hash-funktioner, der omdanner strenge til array-indekser, det vil sige til heltal fra området [0, N] med et endeligt N.

Naturligt, en hash-funktion anvendes til en lang række strenge. Derfor bliver dets “globale” egenskaber vigtige.

Desværre er det ikke muligt, at en hash-funktion altid omdanner forskellige strenge til forskellige tal.

Vi kan overbevise os selv ganske let om, at antallet af strenge er meget større end antallet af heltal i ethvert område [0, N]. Derfor er det uundgåeligt, at der er et par ikke-lige strenge, for hvilke en hash-funktion producerer lige store værdier. Dette fænomen kaldes kollision.

Vi vil ikke dykke ned i de tekniske detaljer bag hash-funktioner, men det er klart, at en god hash-funktion skal forsøge at kortlægge de strenge, som den er defineret i tal, ensartet.

Et andet åbenlyst krav er, at en god hash-funktion skal være hurtig. Hvis det tager for lang tid at beregne en hash-værdi, kan vi ikke få adgang til elementer hurtigt.

I denne vejledning betragter vi en af ​​de teknikker, der forsøger at gøre kortlægningen ensartet og samtidig opretholde det hurtigt.

4. Foldeteknik

Vores mål er at finde en funktion, der omdanner strenge til array-indekser. Bare for at illustrere ideen antager vi, at vi ønsker, at dette array skal have kapacitet til 105 elementer, og lad os bruge streng Java-sprog som et eksempel.

4.1. Beskrivelse

Lad os starte med at konvertere strengens tegn til tal. ASCII er en god kandidat til denne operation:

Nu arrangerer vi de tal, vi lige har fået, i grupper af en eller anden størrelse. Generelt vælger vi gruppestørrelsesværdien baseret på størrelsen på vores array, der er 105. Da tallene, hvor vi omdannede tegnene til, indeholder fra to til tre cifre uden tab af generalitet, kan vi indstille gruppestørrelsen til to:

Det næste trin er at sammenkæde tallene i hver gruppe som om de var strenge og finde deres sum:

Nu skal vi tage det sidste trin. Lad os kontrollere, om antallet 348933 kan tjene som et indeks for vores matrix af størrelse 105. Det overgår naturligvis den maksimalt tilladte værdi 99999. Vi kan let løse dette problem ved at anvende modulo-operatøren for at finde det endelige resultat:

348933 % 10000 = 48933

4.2. Afsluttende bemærkninger

Vi ser, at algoritmen ikke inkluderer nogen tidskrævende operationer, og derfor er den ret hurtig. Hvert tegn i inputstrengen bidrager til det endelige resultat. Denne kendsgerning hjælper bestemt med at reducere kollisioner, men ikke helt at undgå dem.

For eksempel, hvis vi ønskede at springe foldningen over og anvendte modulo-operatøren direkte på den ASCII-transformerede inputstreng (ignorerer overløbsproblemet)

749711897321089711010311797103101 % 100000 = 3101

så vil en sådan hash-funktion producere den samme værdi for alle strenge, der har de samme sidste to tegn som vores inputstreng: age, salder, large, og så videre.

Fra beskrivelsen af ​​algoritmen kan vi let se, at den ikke er fri for kollisionerne. For eksempel producerer algoritmen den samme hash-værdi for Java-sprog og vaJa sprog strenge.

5. Andre teknikker

Foldeteknikken er ret almindelig, men ikke den eneste. Nogle gange, den binning eller midt på pladsen teknikker kan også være nyttige.

Vi illustrerer deres idé ved ikke at bruge strenge, men tal (antag, at vi allerede på en eller anden måde har omdannet strengene til tal). Vi diskuterer ikke deres fordele og svagheder, men du kan danne en mening efter at have set algoritmerne.

5.1. Binning-teknik

Antag, at vi har 100 heltal, og at vores hash-funktion skal kortlægge dem i en matrix på 10 elementer. Så kan vi bare arrangere disse 100 heltal i ti grupper på en sådan måde, at de første ti heltal ender i den første bin, de anden ti heltal ender i den anden bin osv .:

5.2. Mid-Square-teknik

Denne algoritme blev foreslået af John von Neumann, og det giver os mulighed for at generere pseudo-tilfældige tal startende fra et givet nummer.

Lad os illustrere det på et konkret eksempel. Antag, vi har et firecifret tal 1111. Ifølge algoritmen kvadrerer vi den og opnår således 1234321‬. Nu udtrækker vi fire cifre fra midten, for eksempel 2343. Algoritmen giver os mulighed for at gentage denne proces, indtil vi er tilfredse med resultatet.

6. Konklusion

I denne vejledning overvejede vi flere hashing-teknikker. Vi beskrev i detaljer foldeteknikken og gav en flashbeskrivelse af, hvordan binning og midterkant kan opnås.

Som altid finder vi muligvis de tilsvarende kodestykker på vores GitHub-lager.


$config[zx-auto] not found$config[zx-overlay] not found