Linjär hashing

Linjär hash ( LH ) är en dynamisk datastruktur som implementerar en hashtabell och växer eller krymper en hink i taget. Den uppfanns av Witold Litwin 1980. Den har analyserats av Baeza-Yates och Soza-Pollman. Det är det första i ett antal system som kallas dynamisk hashing som Larsons linjära hashing med partiella tillägg, linjär hashing med prioritetsdelning, linjär hashing med partiella expansioner och prioritetsdelning eller rekursiv linjär hashing.

Filstrukturen för en dynamisk hashdatastruktur anpassar sig själv till förändringar i filens storlek, så dyra periodiska filomorganiseringar undviks. En linjär hashingfil expanderar genom att dela en förutbestämd hink i två och drar ihop sig genom att slå samman två förutbestämda hinkar till en. Utlösaren för en rekonstruktion beror på schemats smak; det kan vara ett spill vid en skopa eller lastfaktor (antal poster dividerat med antalet skopor) som rör sig utanför ett förutbestämt område. I Linear Hashing finns det två typer av hinkar, de som ska delas och de som redan delas. Medan utdragbar hashning bara delar upp överfulla hinkar, spiralhashing (alias spirallagring) poster ojämnt över hinkarna så att hinkar med höga kostnader för insättning, radering eller hämtning är tidigast i kön för en delning.

Linear Hashing har också gjorts till en skalbar distribuerad datastruktur, LH* . I LH* finns varje hink på en annan server. LH* i sig har utökats för att tillhandahålla datatillgänglighet i närvaro av trasiga hinkar. Nyckelbaserade operationer (infogar, raderar, uppdaterar, läser) i LH och LH* tar maximal konstant tid oberoende av antalet hinkar och därmed av poster.

Algoritmdetaljer

Poster i LH eller LH* består av en nyckel och ett innehåll, det senare i princip alla postens övriga attribut. De förvaras i hinkar. Till exempel, i Ellis implementering är en hink en länkad lista med poster. Filen tillåter nyckelbaserade CRUD-operationer att skapa eller infoga, läsa, uppdatera och ta bort samt en skanningsoperation som skannar alla poster, till exempel för att göra en databasvalsoperation på ett icke-nyckelattribut. Poster lagras i hinkar vars numrering börjar med 0.

Hash-funktioner

För att komma åt en post med tangenten $c$ tillämpas en familj av hashfunktioner, som tillsammans kallas en dynamisk hashfunktion, på tangenten $c$ . När som helst används högst två hashfunktioner $h_{i}$ och ${\displaystyle h_{i+1}} .$ Ett typiskt exempel använder division modulo x-operationen. Om det ursprungliga antalet hinkar är $N$ så är familjen av hashfunktioner

$h_{i}(c)\mapsto c{\pmod {N\cdot 2^{i}}}$

Filexpansion

När filen växer genom insättningar expanderar den graciöst genom att en hink delas upp i två hinkar. Sekvensen av hinkar som ska delas är förutbestämd. Detta är den grundläggande skillnaden mot system som Fagins utdragbara hashing. ersätts hashfunktionen ${\displaystyle h_{i}} med$ $h_{i+1}$ . Numret på hinken som ska delas är en del av filtillståndet och kallas delad pekare $s$ .

Delad kontroll

En split kan utföras när en hink svämmar över. Detta är en okontrollerad splittring. Alternativt kan filen övervaka belastningsfaktorn och utföra en split när belastningsfaktorn överskrider en tröskel. Detta var kontrollerad klyvning.

Adressering

Adresseringen baseras på filtillståndet, som består av den delade pekaren $s$ och nivån $l$ . Om nivån är $l$ är hashfunktionerna som används $h_{l}$ och $h_{l+1}$ .

LH-algoritmen för hash-nyckel $c$ är

$a:=h_{l}(c)$

om $a<s:a:=h_{l+1}(c)$

Splittring

När en hink delas uppdateras split pointer och eventuellt nivån enligt

$s:=s+1$

om $s\geq N\ gånger 2^{l}$ : $l+=1,s=0$

Filsammandragning

Om under kontrollerad delning belastningsfaktorn sjunker under ett tröskelvärde utlöses en sammanfogningsoperation. Sammanfogningen ångrar den senaste uppdelningen och återställer också filtillståndet.

Filtillståndsberäkning

Filtillståndet består av delad pekare $s$ och nivå $l$ . Om originalfilen började med $N=1$ hinkar, så är antalet buckets $n$ och filtillståndet relaterade via

$n=2^{l}+s$

LH*

Det huvudsakliga bidraget från LH* är att låta en klient till en LH*-fil hitta den bucket där posten finns även om klienten inte känner till filtillståndet. Klienter lagrar faktiskt sin version av filtillståndet, vilket initialt bara är kunskapen om den första hinken, nämligen Bucket 0. Baserat på deras filtillstånd beräknar en klient adressen till en nyckel och skickar en begäran till den hinken. Vid hinken kontrolleras begäran och om posten inte finns vid hinken vidarebefordras den. I ett någorlunda stabilt system, det vill säga om det bara pågår en split eller merge medan begäran behandlas, kan det visas att det finns högst två forwards. Efter en forward skickar den sista hinken ett bildjusteringsmeddelande till klienten vars tillstånd nu är närmare tillståndet för den distribuerade filen. Även om forwards är relativt sällsynta för aktiva klienter, kan deras antal minskas ytterligare genom ytterligare informationsutbyte mellan servrar och klienter

Adoption i språksystem

Griswold och Townsend diskuterade antagandet av linjär hashing i Icon-språket . De diskuterade implementeringsalternativen för dynamisk arrayalgoritm som används i linjär hashning och presenterade prestandajämförelser med hjälp av en lista över Icon benchmark-applikationer.

Adoption i databassystem

Linjär hashning används i Berkeleys databassystem (BDB) , som i sin tur används av många programvarusystem, med en C-implementation härledd från CACM -artikeln och först publicerad på Usenet 1988 av Esmond Pitt.

externa länkar

Se även