Linjärt klingande

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 9 februari 2022; verifiering kräver 1 redigering .

Linjär sondering  är ett programmeringsschema för att lösa kollisioner i hashtabeller , datastrukturer för att manipulera uppsättningar av nyckel-värdepar hitta de värden som är associerade med en given nyckel. Systemet skapades 1954 av Amdahl , Elaine McGraw och Arthur Samuel och analyserades 1963 av Donald Knuth .

Tillsammans med kvadratisk sondering och dubbel sondering , är linjär sondering en sorts öppen adressering . I dessa scheman innehåller varje cell i hashtabellen ett nyckel-värdepar. Om hashfunktionen kolliderar genom att mappa värdet på den nya nyckeln till en hashtabellcell som upptas av en annan nyckel, skannar linjär sondering tabellen till närmaste lediga nästa cell och infogar den nya nyckeln där. Sökningen efter ett värde utförs på samma sätt, genom att skanna tabellen sekventiellt, med början från positionen som bestäms av hashfunktionen, tills den hittar en nyckelmatchning, eller en tom cell.

Som Thorup och Zhang skrev, "Hash-tabeller använder mycket icke-triviala datastrukturer och de flesta hårdvaruimplementationer använder linjär sondering, vilket är snabbt och enkelt att implementera" [1] . Linjär sondering kan ge hög prestanda på grund av metodens goda referenslokalitet men den är mer känslig för kvaliteten på hashfunktionen än andra kollisionsupplösningsscheman. Den genomsnittliga förväntade uppslagstiden för en metod är konstant, detsamma gäller för infogningar och borttagningar om implementeringen använder hash-randomisering, 5-oberoende hashing , eller tabellhashning . Men i praktiken uppnås goda resultat med andra hashfunktioner som MurmurHash [2] .

Operationer

Linjär sondering är en komponent i öppna adresseringsscheman för användning i hashtabeller för att lösa ordförrådsproblem . I en ordboksuppgift måste datastrukturen fungera på en uppsättning nyckel-värdepar och måste tillåta infogning och radering av par, såväl som sökningen efter värdet som är associerat med nyckeln. Vid öppen adressering är datastrukturen en array T (hash-tabell) vars celler T [ i ] (om de inte är tomma) innehåller ett enda nyckel-värdepar. En hash-funktion används för att mappa varje nyckel till en tabellcell T där den nyckeln ska placeras, vanligtvis genom att förvränga nycklarna så att nycklar med nära värden inte är nära i tabellen. En hashkollision uppstår när hashfunktionen mappar en nyckel till en cell som redan är upptagen av en annan nyckel. Linjär sondering är en strategi för att lösa kollisioner genom att placera en ny nyckel i närmaste nästa fria cell [3] [4] .

Sök

För att söka efter en given nyckel x , kontrolleras cellerna i tabell T , med början med cellen med index h ( x ) (där h  är en hashfunktion), sedan cellerna h ( x ) + 1 , h ( x ) + 2 , ..., tills det hittas en fri cell eller en cell som innehåller nyckeln x . Om cellen som innehåller nyckeln hittas returnerar uppslagsproceduren värdet från den cellen. Annars, om en tom cell påträffas, kan nyckeln inte finnas i tabellen och proceduren returnerar som ett resultat av att nyckeln inte hittades [3] [4]

Infoga

För att infoga ett nyckel-värdepar ( x , v ) i en tabell (eventuellt ersätter ett befintligt par med samma nyckel), går infogningsalgoritmen genom samma sekvens av celler som i sökningen tills den hittar antingen en tom cell eller en cell som innehåller nyckel x . Det nya nyckel-värdeparet placeras i denna cell [3] [4] .

Om, efter en infogning , tabellens belastningsfaktor (andelen av celler som är upptagna) överstiger någon tröskel, kan hela tabellen ersättas med en ny tabell som växer i storlek med en konstant faktor, som i fallet med en dynamisk array , med ett nytt hashbord. Att sätta denna tröskel nära noll och använda en hög tabellspridningsfaktor resulterar i snabba operationer men är minneskrävande. Vanligtvis fördubblas bordets storlek när en belastningsfaktor på 1/2 uppnås, så belastningen är mellan 1/4 och 1/2 [5]

Borttagning

Du kan ta bort ett nyckel-värdepar från en ordbok. Det räcker dock inte att bara rensa cellen. Kanske finns det ett annat par med samma hashvärde som placerades någonstans efter den ockuperade cellen. Efter att ha rensat cellen, sökning efter ett andra värde med samma hashvärde kommer att träffa en tom cell och paret kommer inte att hittas.

När vi rensar cell i måste vi alltså titta på efterföljande celler tills vi hittar en tom cell, eller en nyckel som kan överföras till cell i (det vill säga en nyckel vars hashvärde är lika med eller mindre än i ). Om en tom cell hittas kan du rensa cell i och stoppa raderingsprocessen. Om en nyckel hittas som kan flyttas till cell i , flytta den. Detta kommer att öka sökhastigheten för den överförda nyckeln, och även radera en annan cell i blocket med ockuperade celler. Det är nödvändigt att fortsätta sökningen efter en nyckel som kan överföras till detta fria utrymme. Sökandet efter en nyckel att överföra utförs till en tom cell, tills vi når den cell som ursprungligen var tom. Sålunda är exekveringstiden för hela raderingsprocessen proportionell mot längden på blocket som innehåller den raderade nyckeln [3] .

Alternativt kan en lat raderingsstrategi [ användas , där nyckel-värdeparet tas bort genom att ersätta värdet med en speciell flagga som indikerar att nyckeln har tagits bort. Sådana flaggor resulterar emellertid i en ökning av belastningsfaktorn för hashtabellen. I den här strategin kan det bli nödvändigt att ta bort flaggorna från arrayen och beräkna hashvärdena för alla återstående nyckel-värdepar när för många värden tas bort [3] [4] .

Egenskaper

Linjär sondering ger bra referenslokalitet , vilket innebär att endast ett fåtal icke-cachade minnesåtkomster behövs per operation. Med tanke på detta, med bibehållen låg belastningsfaktor, kan algoritmen ge en hög grad av prestanda. Men jämfört med vissa andra öppna adresseringsstrategier försämras prestandan snabbare när den laddas på grund av primär klustring , tendensen hos en enda kollision att orsaka många nära kollisioner [3] . Dessutom kräver denna metod en hashfunktion av högre kvalitet än andra kollisionsupplösningssystem [6] för att få bra prestanda . Om algoritmen är implementerad med en hashfunktion av dålig kvalitet som inte eliminerar heterogenitet i ingångsfördelningen, kan linjär sondering vara långsammare än andra öppna adresseringsstrategier, såsom dubbel sondering , som försöker en sekvens av celler vars separation bestäms genom en andra hashfunktion, eller kvadratisk sondering , när storleken på varje steg ändras beroende på positionen i sekvensen av sonder [7] .

Analys

När linjär sondering används kan ordboksoperationer implementeras med en konstant förväntad åtkomsttid. Med andra ord kan infoga, ta bort och slå upp operationer implementeras i O(1) , förutsatt att hashtabellens belastningsfaktor är en konstant strikt mindre än en [8] .

Mer specifikt är tiden för varje enskild operation (sökning, infogning eller radering) proportionell mot längden på det angränsande blocket av upptagna celler från vilket operationen börjar. Om alla startceller är lika sannolika i en hashtabell med N celler, så har ett maximalt block av k upptagna celler en k / N sannolikhet att innehålla startsökningspositionen och tar O ( k ) tid , var startcellen än är. Sålunda kan den förväntade exekveringstiden för operationen beräknas som produkten av dessa två termer, O ( k2 / N ) , summerade över alla de maximala blocken av angränsande celler i tabellen. En liknande summa av kvadraterna på blockens längder ger kantmattan. väntetid för en slumpmässig hashfunktion (snarare än en slumpmässig startposition i hashtabellen) genom att summera alla block som kan existera (snarare än de som faktiskt existerar i tabellens nuvarande tillstånd) och multiplicera termerna för varje potentiellt block av sannolikheten att blocket är upptaget. Det vill säga, om vi definierar Block( i , k ) som händelsen att det finns ett maximalt angränsande block av upptagna celler med längden k som börjar vid index i , mat. väntetiden för operationen är

Formeln kan förenklas genom att ersätta Block( i , k ) med ett enklare nödvändigt villkor Full( k ) , händelsen att minst k element har hashvärden som ligger inom ett block av celler med längden k . Efter denna ersättning beror värdet inom summan inte längre på i och 1/ N -faktorn upphäver N - termerna för den yttre summeringen. Dessa förenklingar leder till gränsen

Men enligt den multiplikativa formen av Chernoff-gränsen , om belastningsfaktorn är strikt mindre än en, är sannolikheten att blocklängden k innehåller minst k hashade värden exponentiellt liten som en funktion av k , vilket betyder att summan begränsas av en konstant oberoende av n [3] . Man kan också göra samma analys med hjälp av Stirling-formeln istället för Chernoff-gränsen för att uppskatta sannolikheten att ett block innehåller exakt k hashade värden [4] [9] .

När det gäller belastningsfaktorn α är den förväntade tiden för en lyckad uppslagning O (1 + 1/(1 − α )) , och den förväntade tiden för en misslyckad uppslagning (eller infogning av en ny nyckel) är O (1 + 1/(1 − α ) 2 ) [10] . För en konstant lastfaktor, med hög sannolikhet, har den längsta sonderingssekvensen (bland sonderingssekvenserna för alla nycklar i tabellen) en logaritmisk längd [11] .

Välja en hashfunktion

Eftersom linjär sondering är mycket känslig för ojämnt fördelade hashvärden [7] är det viktigt att kombinera metoden med en högkvalitativ hashfunktion som inte ger sådana ojämnheter.

Analysen ovan antar att hash för varje nyckel är ett slumptal oberoende av hash för andra nycklar. Detta antagande är orealistiskt för de flesta hashapplikationer. Däremot kan slumpmässiga eller pseudo-slumpmässiga hashvärden användas när objekt hashas av deras id snarare än efter värde. Detta görs till exempel med linjär sondering med klassen IdentityHashMap i Java collections framework [12] uppsättning klasser och gränssnitt . Hashvärdet som denna klass associerar med varje objekt, dess identityHashCode, är garanterat detsamma för objektet under hela dess livstid, men hashvärdet för samma objekt under andra omständigheter kommer att vara annorlunda [13] . Eftersom identityHashCode bara byggs en gång per objekt och inte behöver associeras med objektets värde eller adress, kan dess konstruktion använda långsammare beräkningsmetoder, som att anropa slumpmässiga eller pseudoslumptalsgeneratorer. Till exempel använder Java 8 den pseudo-slumpmässiga numeriska generatorn Xorshift [14] för att konstruera sådana värden .

För de flesta hashapplikationer är det nödvändigt att beräkna hashfunktionen för varje värde varje gång en hash krävs, inte bara när objektet har skapats. I sådana applikationer kan slumpmässiga eller pseudoslumpmässiga tal inte användas som hashvärden, eftersom då olika objekt med samma värde kan ha olika hashvärden. Och kryptografiska hashfunktioner (som är designade för att inte kunna skiljas från sanna slumpmässiga funktioner) är vanligtvis för långsamma för att användas i hashtabeller [15] . Istället används andra metoder för att konstruera hashfunktioner. Dessa metoder beräknar hashfunktionen snabbt och kan bevisas fungera bra med linjär sondering. Speciellt har linjär sondering analyserats i termer av k -oberoende hash , en klass av hashfunktioner som initieras med ett litet slumpmässigt tal och mappar vilken k -tuppel av distinkta nycklar som helst till vilken k -tupel av index som helst med lika sannolikhet. Parametern k kan ses som ett mått på kvaliteten på hashfunktionen - ju större k desto mer tid tar det att beräkna hashfunktionen, men den kommer att bete sig närmare helt slumpmässiga funktioner. För linjär sondering är 5-oberoende tillräckligt för att garantera en konstant förväntad tid per operation [16] , medan vissa 4-oberoende hashfunktioner fungerar dåligt och kräver logaritmisk tid per operation [6] .

En annan metod för att bygga hashfunktioner med hög kvalitet och acceptabel hastighet är table hashing . I denna metod beräknas hashvärdet för nyckeln genom att för varje byte av nyckeln välja ett index i en tabell med slumptal (med en annan tabell för varje byteposition). Siffrorna från cellerna i dessa tabeller kombineras sedan bit för bit med XOR -operationen . Hashfunktioner konstruerade på detta sätt är endast 3-oberoende. Linjära sonder som använder dessa hashfunktioner kräver dock en konstant förväntad tid per operation [4] [17] . Både tabellhashning och standardmetoder för att generera 5-oberoende hashfunktioner är begränsade till nycklar som har ett fast antal bitar. För att arbeta med strängar eller andra typer av nycklar med variabel längd kan man kombinera den enklare universella hashtekniken , som mappar nycklar till mellanliggande värden, med en högkvalitativ (5-oberoende eller tabulering ) hashfunktion, som mappar mellanvärden att hasha index -tabeller [1] [18] .

I experimentella jämförelser fann Richter et al. att fold-shift-familjen av hashfunktioner (definierad som ) var "den snabbaste hashfunktionen när den används i alla hashscheman, dvs. ger den högsta genomströmningen såväl som god kvalitet", i while-tabellen hashing gav "den lägsta genomströmningen" [2] . De påpekade att titta på varje tabell kräver flera cykler, vilket är dyrare än enkla aritmetiska operationer. De fann också att MurmurHash är bättre än tabellhashning: "Efter att ha undersökt resultaten som presenteras av Mult och Murmur, tycker vi att tabulering (...) är mindre attraktivt i praktiken."

Historik

Idén med en associativ array , som gör att data kan nås genom dess värde snarare än dess adress, går tillbaka till mitten av 1940-talet av Konrad Zuse och Vanivar Busch [19] , men hashtabeller beskrevs inte förrän de beskrevs Lun i ett IBM -memorandum 1953. Lun använde en annan metod för att lösa kollisioner, kedja snarare än linjär sondering [ 20] .

Donald Knuth [8] sammanfattade linjärt ljuds tidiga historia. Detta var den första metoden för öppen adressering och var till en början synonym med öppen adressering. Enligt Knuth användes metoden först av Jean Amdahl , McGraw, Elani M. och Arthur Samuel 1954 i ett assemblerprogram för IBM 701 [8] . Den första publicerade beskrivningen av linjärt ljud gavs av Peterson [21] [8] , som också nämnde Samuel, Amdahl och McGraw, men tillade att "systemet är så naturligt att det är ganska troligt att det kunde ha skapats oberoende av andra före eller samtidigt" [22] . En annan tidig publikation av denna metod tillhör den sovjetiske forskaren Andrey Petrovich Ershov , publicerad 1958 [23] .

Den första teoretiska analysen av linjär sondering som visar att metoden fungerar i en konstant förväntad tid per operation på en slumpmässig hashfunktion gavs av Knuth [8] . Sedgwick kallade Knuths arbete "en milstolpe i analysen av algoritmer" [10] . Betydligt senare ledde studier till en mer detaljerad analys av sannolikhetsfördelningen av arbetstiden [24] [25] och beviset att linjär sondering fungerar i konstant tid per operation med en bekväm hashfunktion för praktiska beräkningar, och inte med den ideala slumpmässig funktion antagen i tidigare analyser [16] [17] .

Anteckningar

  1. ↑ 1 2 Thorup, Zhang, 2012 , sid. 293–331.
  2. ↑ 1 2 Richter, Alvarez, Dittrich, 2015 , sid. 293–331.
  3. ↑ 1 2 3 4 5 6 7 Goodrich, Tamassia, 2015 , sid. 200–203.
  4. ↑ 1 2 3 4 5 6 Morin, 2014 , sid. 108–116.
  5. ↑ Sedgewick, Wayne, 2011 ; Sedgwick och Wayne halverar storleken på bordet om bordsbelastningen blir för låg i en division, vilket resulterar i ett bredare område [1/8,1/2] av möjliga lastfaktorer.
  6. ↑ 1 2 Pătraşcu, Thorup, 2010 , sid. 715–726.
  7. ↑ 1 2 Heileman, Luo, 2005 , sid. 141–154.
  8. ↑ 1 2 3 4 5 Knuth, 1963 .
  9. ↑ Eppstein, 2011 .
  10. ↑ 12 Sedgewick , 2003 .
  11. ↑ Pittel, 1987 , sid. 236–249.
  12. ↑ Dokumentation för Java SE 7 .
  13. ↑ Friesen, 2012 , sid. 376.
  14. ↑ Kabutz, 2014 .
  15. ↑ Weiss, 2014 , sid. 3-11.
  16. ↑ 1 2 Pagh, Pagh, Ružić, 2009 , sid. 1107–1120.
  17. ↑ 1 2 Pătrașcu, Thorup, 2011 , sid. 1–10.
  18. ↑ Thorup, 2009 , sid. 655–664.
  19. ↑ Parhami, 2006 , sid. 67.
  20. ↑ Morin, 2004 , sid. 9-15.
  21. ↑ Peterson, 1957 .
  22. ↑ Peterson, 1957 , sid. 130–146.
  23. ↑ Ershov, 1958 , sid. 3–6.
  24. ↑ Flajolet, Poblete, Viola, 1998 , sid. 490–515.
  25. ↑ Knuth, 1998 , sid. 561–568.

Litteratur