Linearno heširanje

Linearno heširanje je dinamička heš tabela. Algoritam koji je izmislio Vitold Litvin (1980), a kasnije popularizovao Paul Larson. Linearno heširanje omogućava proširenje jednog slota heš tabele u isto vreme. Često se zasebnim slotom za proširenje mogu veoma efikasno kontrolisati dužine lanaca sudara. Troškovi heš tabele ekspanzije se širi preko svake operacije heš tabela umetanja, za razliku od onih koje nastanu odjednom. Linearno heširanje je stoga pogodno za interaktivne aplikacije.

Detalji algoritma

Prvo početna heš tabela je postavljena sa nekim proizvoljnim početnim brojem kofi(engl. buckets). Sledeće vrednosti treba da budu praćenje:

• $N$: : Početni broj kofi.
• $L$: Sadašnji nivo koji je ceo broj koji ukazuje na logaritamsku skalu,otprilike koliko je sto porastao u broju. To je u početku $0$.
• $S$: Pokazivač koji ukazuje na korpu. To ukazuje na početak prvog segmenta u tabeli.

Kofa sudari mogu se rešavati na različite načine, ali je tipično da imaju prostor za dva predmeta u svakom segmentu i da dodate još kofi kad god preliva. Više od dve stavke mogu da se koriste kada je implementacija otklanjanja grešaka. Adrese se izračunava na sledeći način:

• Primenite heš funkciju ključa i pozvati rezultat $H$.
• Ako $H{\bmod {N}}\times 2^{L}$ je adresa koja dolazi pre $S$, adresa je $H{\bmod {N}}\times 2^{L+1}$.
• Ako $H{\bmod {N}}\times 2^{L}$ je $S$ ili adresa koja dolazi nakon $S$,adresa je $H{\bmod {N}}\times 2^{L}$.

Da biste dodali kofu:

• Dodati novu kantu na kraj stola.
• Ako $S$ ukazuje na $N\times 2^{L}$ kantu u tabeli, resetovati(postaviti na 0) $S$ i povećati $L$.
• Inače povećati $S$.

Efekat svega ovoga je da tabela je podeljena u tri dela;odeljak pre $S$, deonica od $S$ to $N\times 2^{L}$, i deonica posle $N\times 2^{L}$. Prva i poslednja sekcije su uskladištene korišćenjem $H{\bmod {N}}\times 2^{L+1}$ i i srednji deo koji se čuva koristeći $H{\bmod {N}}\times 2^{L}$. Svaki put $S$dostigne $N\times 2^{L}$ njto je duplo uvećan sto.

Poeni za prenos

• Pune kofe nije heophodno da budu podeljene,i potreban prostor za prekoračenja. U spoljne memorije, to bi moglo da znači drugi fajl.
• Kofe nisu pune.
• Svaka kofa bi bila pre ili kasnije podeljena i vraćeno prekoračenje.
• Split pokazivač ukazuje koja će biti podeljena
  • s je nezavisna od pune kofe
  • Na nivou i, s je između 0 i 2^i
  • s se povećava i na kraju,vraćena na 0.
  • pošto kašika s je podeljena onda s se povećava,samo kašike pre imaju dupli udvostručeni heš prostor.
  • veliki dobar pseudo slučajni broj se dobija prvo, a zatim je bitno-maskiran sa (2^i) - 1 ili (2^(i+1)) -1, ali kasnije primenjuje samo ako je k, slučajni broj, bitno-maskiran sa (2^i) - 1, koji je manji od S, pa veći raspon heš vrednosti odnose samo na segmente koji su već podeljeni.

Za bitovsko-maskiranje broja koristi se x & 0111 , gde je & AND operacija, 111 je binarno 7 , gde je 7 = 8 - 1 i 8 je 2^3 i i = 3.

• h_i (k)= h(k) mod(2^i n)
• h_i+1 udvostručuje domet h_i

Algoritam za umetanje 'k' i provere stanje prekoračenja

• b = h₀(k)
• ako b < pokazivača onda
• b = h₁(k)

Pretraživanje u heš tabeli za 'k'

• b = h₀(k)
• Ako b < pokazivača
• b = h₁(k)

Usvajanje u jezičkim sistemima

Grisvold i Tovnsend su razgovarali o usvajanju linearnog heširanje u jeziku Ikonica. Oni su razgovarali o alternativama dinamičkog niza algoritma koji se koristi u implementaciji linearnog heširanja,i predstavio poređenja performansi korišćenja lista u aplkikaciji za Ikonice.

Usvajanje u sistemima baza podataka

Linearno heširanje se koristi u sistemu baze podataka BDB Berkli, koji zauzvrat koristi od strane mnogih softverskih sistema, kao što su OpenLDAP, koristeći implementaciju C izveden iz CACM članka i prvi objavljen u Usenet u 1988 od strane Esmond Pitt.

Dodatni linkovi

• Sorted Linear Hash Table, C++ implementation of a Linear Hashtable
• TommyDS, C implementation of a Linear Hashtable
• An in Memory Go Implementation with Explanation
• Paul E. Black, linear hashing at the National Institute of Standards and Technology, Dictionary of Algorithms and Data Structures.
• A C++ Implementation of Linear Hashtable which Supports Both Filesystem and In-Memory Storage

Vidi još

• Prošireno heširanje
• Konzistentan heš