Lineær lyd

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 9. februar 2022; verifikation kræver 1 redigering .

Lineær sondering  er et programmeringsskema til løsning af kollisioner i hashtabeller , datastrukturer til at manipulere sæt af nøgleværdi-par finde de værdier, der er forbundet med en given nøgle. Ordningen blev udtænkt i 1954 af Amdahl , Elaine McGraw og Arthur Samuel og analyseret i 1963 af Donald Knuth .

Sammen med kvadratisk sondering og dobbelt sondering , er lineær sondering en slags åben adressering . I disse skemaer indeholder hver celle i hash-tabellen ét nøgleværdi-par. Hvis hash-funktionen kolliderer ved at kortlægge værdien af ​​den nye nøgle til en hash-tabelcelle optaget af en anden nøgle, scanner lineær sondering tabellen til den nærmeste ledige næste celle og indsætter den nye nøgle der. Søgningen efter en værdi udføres på samme måde ved at scanne tabellen sekventielt, startende fra positionen bestemt af hash-funktionen, indtil den finder et nøglematch eller en tom celle.

Som Thorup og Zhang skrev: "Hash-tabeller gør stor brug af ikke-trivielle datastrukturer, og de fleste hardwareimplementeringer bruger lineær sondering, som er hurtig og nem at implementere" [1] . Lineær sondering kan give høj ydeevne på grund af metodens gode referencelokalitet men den er mere følsom over for kvaliteten af ​​hashfunktionen end andre kollisionsopløsningsskemaer. Den gennemsnitlige forventede opslagstid for en metode er konstant, det samme gælder for indsættelser og sletninger, hvis implementeringen bruger hash-randomisering, 5-uafhængig hashing , eller tabel-hashing . Men i praksis opnås gode resultater med andre hashing-funktioner såsom MurmurHash [2] .

Operationer

Lineær sondering er en komponent i åbne adresseringsskemaer til brug i hashtabeller til at løse ordforrådsproblemer . I en ordbogsopgave skal datastrukturen fungere på et sæt nøgle-værdi-par og skal tillade indsættelse og sletning af par, samt søgning efter den værdi, der er knyttet til nøglen. Ved åben adressering er datastrukturen et array T (hash-tabel), hvis celler T [ i ] (hvis ikke tomme) indeholder et enkelt nøgleværdi-par. En hash-funktion bruges til at tilknytte hver nøgle til en tabelcelle T , hvor denne nøgle skal placeres, typisk ved at kryptere nøglerne, så nøgler med tætte værdier ikke er tæt på i tabellen. En hash-kollision opstår, når hash-funktionen kortlægger en nøgle til en celle, der allerede er optaget af en anden nøgle. Lineær sondering er en strategi til at løse kollisioner ved at placere en ny nøgle i den nærmeste næste frie celle [3] [4] .

Søg

For at søge efter en given nøgle x , kontrolleres cellerne i tabel T , begyndende med cellen med indeks h ( x ) (hvor h  er en hash-funktion), derefter cellerne h ( x ) + 1 , h ( x ) + 2 , ..., indtil der findes en fri celle eller en celle, der indeholder nøglen x . Hvis cellen, der indeholder nøglen, findes, returnerer opslagsproceduren værdien fra den pågældende celle. Ellers, hvis en tom celle stødes på, kan nøglen ikke være i tabellen, og proceduren vender tilbage som et resultat af, at nøglen ikke blev fundet [3] [4]

Indsæt

For at indsætte et nøgle-værdi-par ( x , v ) i en tabel (eventuelt erstatte et eksisterende par med den samme nøgle), krydser indsættelsesalgoritmen den samme sekvens af celler som i søgningen, indtil den finder enten en tom celle eller en celle indeholdende nøgle x . Det nye nøgle-værdi-par placeres i denne celle [3] [4] .

Hvis tabellens belastningsfaktor (brøkdelen af ​​besatte celler) efter en indsættelse overstiger en tærskel, kan hele tabellen erstattes med en ny tabel, der vokser i størrelse med en konstant faktor, som i tilfældet med et dynamisk array , med en ny hash-tabel. At indstille denne tærskel tæt på nul og bruge en høj tabelspredningsfaktor resulterer i hurtige operationer, men er hukommelsesintensiv. Typisk fordobles bordstørrelsen, når en belastningsfaktor på 1/2 nås, så belastningen er mellem 1/4 og 1/2 [5]

Fjernelse

Du kan fjerne et nøgle-værdi-par fra en ordbog. Det er dog ikke nok blot at rydde cellen. Måske er der et andet par med den samme hashværdi, der blev placeret et sted efter den besatte celle. Efter at have ryddet cellen, vil søgning efter en anden værdi med samme hashværdi ramme en tom celle, og parret vil ikke blive fundet.

Når vi rydder celle i , skal vi således se på efterfølgende celler, indtil vi finder en tom celle, eller en nøgle, der kan overføres til celle i (det vil sige en nøgle, hvis hashværdi er lig med eller mindre end i ). Hvis der findes en tom celle, kan du rydde celle i og stoppe sletningsprocessen. Hvis der findes en nøgle, der kan flyttes til celle i , skal du flytte den. Dette vil øge søgehastigheden for den overførte nøgle og også rydde en anden celle i blokken af ​​besatte celler. Det er nødvendigt at fortsætte søgningen efter en nøgle, der kan overføres til dette frigjorte rum. Søgningen efter en nøgle til at overføre udføres til en tom celle, indtil vi når den celle, der oprindeligt var tom. Udførelsestiden for hele sletningsprocessen er således proportional med længden af ​​blokken, der indeholder den slettede nøgle [3] .

Alternativt kan en doven sletningsstrategi [ bruges , hvor nøgle-værdi-parret fjernes ved at erstatte værdien med et særligt flag , der angiver, at nøglen er blevet fjernet. Sådanne flag resulterer dog i en stigning i belastningsfaktoren for hashtabellen. I denne strategi kan det blive nødvendigt at fjerne flagene fra arrayet og genberegne hash-værdierne for alle resterende nøgleværdi-par, når for mange værdier er fjernet [3] [4] .

Egenskaber

Lineær sondering giver god referencelokalitet , hvilket betyder, at der kun er behov for nogle få ikke-cachelagrede hukommelsesadgange pr. operation. I lyset af dette kan algoritmen, mens den opretholder en lav belastningsfaktor, give en høj grad af ydeevne. Men sammenlignet med nogle andre åbne adresseringsstrategier forringes ydeevnen hurtigere, når den indlæses på grund af primær clustering , en enkelt kollisions tendens til at forårsage mange tætte kollisioner [3] . Derudover kræver denne metode en hashfunktion af højere kvalitet end andre kollisionsopløsningsskemaer [6] for at opnå god ydeevne . Hvis algoritmen er implementeret med en hashfunktion af dårlig kvalitet, der ikke eliminerer heterogenitet i inputfordelingen, kan lineær sondering være langsommere end andre åbne adresseringsstrategier, såsom dobbelt sondering , som forsøger en sekvens af celler, hvis adskillelse bestemmes ved en anden hash-funktion, eller kvadratisk sondering , når størrelsen af ​​hvert trin ændres afhængigt af positionen i sekvensen af ​​sonder [7] .

Analyse

Ved brug af lineær sondering kan ordbogsoperationer implementeres med en konstant forventet adgangstid. Med andre ord kan indsætnings-, sletnings- og opslagsoperationer implementeres i O(1) , forudsat at hash-tabellens belastningsfaktor er en konstant strengt mindre end én [8] .

Mere specifikt er tiden for hver enkelt operation (søgning, indsættelse eller sletning) proportional med længden af ​​den sammenhængende blok af besatte celler, hvorfra operationen starter. Hvis alle startceller er lige sandsynlige i en hash-tabel med N celler, så har en maksimal blok af k besatte celler en k / N -sandsynlighed for at indeholde startsøgningspositionen og tager O ( k ) tid , uanset hvor startcellen er. Den forventede udførelsestid for operationen kan således beregnes som produktet af disse to led, O ( k 2 / N ) , summeret over alle de maksimale blokke af sammenhængende celler i tabellen. En tilsvarende sum af kvadraterne af blokkenes længder giver kantmåtten. ventetid på en tilfældig hash-funktion (i stedet for en tilfældig startposition i hash-tabellen) ved at summere over alle blokke, der måtte eksistere (i stedet for dem, der faktisk eksisterer i den aktuelle tilstand af tabellen) og gange vilkårene for hver potentiel blok med sandsynligheden for, at blokken er optaget. Det vil sige, hvis vi definerer Blok( i , k ) som den hændelse, at der er en maksimal sammenhængende blok af besatte celler med længden k startende ved indeks i , mat. ventetiden på operationen er

Formlen kan forenkles ved at erstatte Block( i , k ) med en enklere nødvendig betingelse Full( k ) , den hændelse, at mindst k elementer har hashværdier, der ligger inden for en blok af celler med længden k . Efter denne udskiftning afhænger værdien inden for summen ikke længere af i , og 1/ N -faktoren annullerer N - leddene i den ydre summering. Disse forenklinger fører til grænsen

Men ifølge den multiplikative form af Chernoff -grænsen , hvis belastningsfaktoren er strengt mindre end én, er sandsynligheden for, at bloklængden k indeholder mindst k hash-værdier, eksponentielt lille som en funktion af k , hvilket betyder, at summen er afgrænset af en konstant uafhængig af n [3] . Man kan også lave den samme analyse ved at bruge Stirling-formlen i stedet for Chernoff-bindingen for at estimere sandsynligheden for, at en blok indeholder præcis k hash-værdier [4] [9] .

Med hensyn til belastningsfaktoren α er den forventede tid for et vellykket opslag O (1 + 1/(1 − α )) , og den forventede tid for et mislykket opslag (eller indsættelse af en ny nøgle) er O (1 + 1/(1 − α ) 2 ) [10] . For en konstant belastningsfaktor med høj sandsynlighed har den længste sonderingssekvens (blandt sonderingssekvenserne for alle taster i tabellen) en logaritmisk længde [11] .

Valg af en hash-funktion

Da lineær sondering er meget følsom over for ujævnt fordelte hashværdier [7] , er det vigtigt at kombinere metoden med en hashfunktion af høj kvalitet, der ikke giver sådanne ujævnheder.

Analysen ovenfor antager, at hver nøgles hash er et tilfældigt tal, der er uafhængig af hasherne for andre nøgler. Denne antagelse er urealistisk for de fleste hashing-applikationer. Tilfældige eller pseudo-tilfældige hash-værdier kan dog bruges, når objekter hash efter deres id snarere end efter værdi. For eksempel gøres dette ved hjælp af lineær sondering med IdentityHashMap-klassen i Java collections framework [12] sæt klasser og grænseflader . Den hashværdi, som denne klasse forbinder med hvert objekt, dets identitetHashCode, er garanteret den samme for objektet gennem hele dets levetid, men hashværdien for det samme objekt under andre omstændigheder vil være anderledes [13] . Da identityHashCode kun bygges én gang pr. objekt og ikke behøver at være forbundet med værdien eller adressen på objektet, kan dens konstruktion bruge langsommere beregningsmidler, såsom at kalde tilfældige eller pseudo-tilfældige talgeneratorer. For eksempel bruger Java 8 den pseudo-tilfældige numeriske generator Xorshift [14] til at konstruere sådanne værdier .

For de fleste hashapplikationer er det nødvendigt at beregne hashfunktionen for hver værdi, hver gang der kræves en hash, ikke kun når objektet er oprettet. I sådanne applikationer kan tilfældige eller pseudo-tilfældige tal ikke bruges som hashværdier, for så kan forskellige objekter med samme værdi have forskellige hashværdier. Og kryptografiske hash-funktioner (som er designet til ikke at kunne skelnes fra ægte tilfældige funktioner) er normalt for langsomme til at blive brugt i hashtabeller [15] . I stedet bruges andre metoder til at konstruere hashfunktioner. Disse metoder beregner hash-funktionen hurtigt og kan bevises at fungere godt med lineær sondering. Især er lineær sondering blevet analyseret i form af k - uafhængig hashing , en klasse af hash-funktioner, der initialiseres med et lille tilfældigt tal og mapper enhver k -tuple af distinkte nøgler til enhver k -tuple af indekser med lige store sandsynlighed. K -parameteren kan opfattes som et mål for kvaliteten af ​​hash-funktionen - jo større k er , jo længere tid tager det at beregne hash-funktionen, men den vil opføre sig tættere på helt tilfældige funktioner. Til lineær sondering er 5-uafhængighed tilstrækkelig til at garantere en konstant forventet tid pr. operation [16] , mens nogle 4-uafhængige hash-funktioner fungerer dårligt, hvilket kræver logaritmisk tid pr. operation [6] .

En anden metode til at opbygge hashfunktioner med høj kvalitet og acceptabel hastighed er table hashing . I denne metode beregnes hashværdien for nøglen ved for hver byte af nøglen at vælge et indeks i en tabel med tilfældige tal (med en forskellig tabel for hver byteposition). Tallene fra cellerne i disse tabeller kombineres derefter bit for bit ved hjælp af XOR- operationen . Hash-funktioner konstrueret på denne måde er kun 3-uafhængige. Lineære prober, der bruger disse hash-funktioner, kræver dog en konstant forventet tid pr. operation [4] [17] . Både tabelhashing og standardmetoder til generering af 5-uafhængige hashfunktioner er begrænset til nøgler, der har et fast antal bits. For at arbejde med strenge eller andre typer af nøgler med variabel længde, kan man kombinere den mere simple universelle hashing -teknik , som kortlægger nøgler til mellemværdier, med en hashfunktion af høj kvalitet (5-uafhængighed eller tabulering ), som kortlægger mellemværdier at hash-indekser -tabeller [1] [18] .

I eksperimentelle sammenligninger fandt Richter et al., at fold-shift-familien af ​​hash-funktioner (defineret som ) var "den hurtigste hash-funktion, når den blev brugt i alle hash-skemaer, dvs. giver den højeste gennemstrømning samt god kvalitet", i while-tabellen hashing gav "den laveste gennemstrømning" [2] . De påpegede, at det kræver flere cyklusser at se på hver tabel, hvilket er dyrere end simple aritmetiske operationer. De fandt også ud af, at MurmurHash er bedre end tabelhashing: "Efter at have undersøgt resultaterne præsenteret af Mult og Murmur, synes vi, at tabulering (...) er mindre attraktivt i praksis."

Historie

Ideen om et associativt array , som gør det muligt at få adgang til data ved hjælp af dens værdi frem for dens adresse, dateres tilbage til midten af ​​1940'erne af Konrad Zuse og Vanivar Busch [19] , men hashtabeller blev ikke beskrevet, før de blev beskrevet Lun [ i et IBM -memorandum i 1953. Lun brugte en anden metode til at løse kollisioner, kæde i stedet for lineær sondering [20] .

Donald Knuth [8] opsummerede den tidlige historie om lineær lyd. Dette var den første metode til åben adressering og var først synonymt med åben adressering. Ifølge Knuth blev metoden første gang brugt af Jean Amdahl , McGraw, Elani M. og Arthur Samuel i 1954 i et assembler -program til IBM 701 [8] . Den første publicerede beskrivelse af lineær lyd blev givet af Peterson [21] [8] , som også nævnte Samuel, Amdahl og McGraw, men tilføjede, at "systemet er så naturligt, at det er ret sandsynligt, at det kunne være blevet uafhængigt skabt af andre før eller på samme tid" [22] . En anden tidlig udgivelse af denne metode tilhører den sovjetiske forsker Andrey Petrovich Ershov , udgivet i 1958 [23] .

Den første teoretiske analyse af lineær sondering, der viser, at metoden virker i en konstant forventet tid pr. operation på en tilfældig hashfunktion, blev givet af Knuth [8] . Sedgwick kaldte Knuths arbejde "en milepæl i analysen af ​​algoritmer" [10] . Væsentlig senere førte undersøgelser til en mere detaljeret analyse af sandsynlighedsfordelingen af ​​arbejdstiden [24] [25] og beviset for, at lineær sondering fungerer i konstant tid pr. operation med en bekvem hash-funktion til praktiske beregninger, og ikke med den ideelle tilfældig funktion antaget i tidligere analyser [16] [17] .

Noter

  1. ↑ 1 2 Thorup, Zhang, 2012 , s. 293-331.
  2. ↑ 1 2 Richter, Alvarez, Dittrich, 2015 , s. 293-331.
  3. ↑ 1 2 3 4 5 6 7 Goodrich, Tamassia, 2015 , s. 200-203.
  4. ↑ 1 2 3 4 5 6 Morin, 2014 , s. 108-116.
  5. ↑ Sedgewick, Wayne, 2011 ; Sedgwick og Wayne halverer bordets størrelse, hvis bordbelastningen bliver for lav i en division, hvilket resulterer i et bredere udvalg [1/8,1/2] af mulige belastningsfaktorer.
  6. ↑ 1 2 Pătraşcu, Thorup, 2010 , s. 715-726.
  7. ↑ 1 2 Heileman, Luo, 2005 , s. 141-154.
  8. ↑ 1 2 3 4 5 Knuth, 1963 .
  9. ↑ Eppstein, 2011 .
  10. ↑ 12 Sedgewick , 2003 .
  11. ↑ Pittel, 1987 , s. 236-249.
  12. ↑ Java SE 7 dokumentation .
  13. ↑ Friesen, 2012 , s. 376.
  14. ↑ Kabutz, 2014 .
  15. ↑ Weiss, 2014 , s. 3-11.
  16. ↑ 1 2 Pagh, Pagh, Ružić, 2009 , s. 1107-1120.
  17. ↑ 1 2 Pătrașcu, Thorup, 2011 , s. 1-10.
  18. ↑ Thorup, 2009 , s. 655-664.
  19. ↑ Parhami, 2006 , s. 67.
  20. ↑ Morin, 2004 , s. 9-15.
  21. ↑ Peterson, 1957 .
  22. ↑ Peterson, 1957 , s. 130-146.
  23. ↑ Ershov, 1958 , s. 3-6.
  24. ↑ Flajolet, Poblete, Viola, 1998 , s. 490-515.
  25. ↑ Knuth, 1998 , s. 561-568.

Litteratur