Линеарно хеширање

Линеарно хеширање је динамичка хеш табела. Алгоритам који је измислио Витолд Литвин (1980), а касније популаризовао Паул Ларсон. Линеарно хеширање омогућава проширење једног слота хеш табеле у исто време. Често се засебним слотом за проширење могу веома ефикасно контролисати дужине ланаца судара. Трошкови хеш табеле експанзије се шири преко сваке операције хеш табела уметања, за разлику од оних које настану одједном. Линеарно хеширање је стога погодно за интерактивне апликације.

Детаљи алгоритма

Прво почетна хеш табела је постављена са неким произвољним почетним бројем кофи(енгл. buckets). Следеће вредности треба да буду праћење:

• $N$: : Почетни број кофи.
• $L$: Садашњи ниво који је цео број који указује на логаритамску скалу,отприлике колико је сто порастао у броју. То је у почетку $0$.
• $S$: Показивач који указује на корпу. То указује на почетак првог сегмента у табели.

Кофа судари могу се решавати на различите начине, али је типично да имају простор за два предмета у сваком сегменту и да додате још кофи кад год прелива. Више од две ставке могу да се користе када је имплементација отклањања грешака. Адресе се израчунава на следећи начин:

• Примените хеш функцију кључа и позвати резултат $H$.
• Ако $H{\bmod {N}}\times 2^{L}$ је адреса која долази пре $S$, адреса је $H{\bmod {N}}\times 2^{L+1}$.
• Ако $H{\bmod {N}}\times 2^{L}$ је $S$ или адреса која долази након $S$,адреса је $H{\bmod {N}}\times 2^{L}$.

Да бисте додали кофу:

• Додати нову канту на крај стола.
• Ако $S$ указује на $N\times 2^{L}$ канту у табели, ресетовати(поставити на 0) $S$ и повећати $L$.
• Иначе повећати $S$.

Ефекат свега овога је да табела је подељена у три дела;одељак пре $S$, деоница од $S$ to $N\times 2^{L}$, и деоница после $N\times 2^{L}$. Прва и последња секције су ускладиштене коришћењем $H{\bmod {N}}\times 2^{L+1}$ и и средњи део који се чува користећи $H{\bmod {N}}\times 2^{L}$. Сваки пут $S$достигне $N\times 2^{L}$ њто је дупло увећан сто.

Поени за пренос

• Пуне кофе није хеопходно да буду подељене,и потребан простор за прекорачења. У спољне меморије, то би могло да значи други фајл.
• Кофе нису пуне.
• Свака кофа би била пре или касније подељена i враћено прекорачење.
• Сплит показивач указује која ће бити подељена
  • s је независна од пуне кофе
  • На нивоу i, s је између 0 и 2^i
  • s се повећава и на крају,враћена на 0.
  • пошто кашика s је подељена онда s се повећава,само кашике пре имају дупли удвостручени хеш простор.
  • велики добар псеудо случајни број се добија прво, а затим је битно-маскиран са (2^i) - 1 или (2^(i+1)) -1, али касније примењује само ако је к, случајни број, битно-маскиран са (2^i) - 1, који је мањи од С, па већи распон хеш вредности односе само на сегменте који су већ подељени.

За битовско-маскирање броја користи се x & 0111 , где је & AND операција, 111 је бинарно 7 , где је 7 = 8 - 1 и 8 је 2^3 и i = 3.

• h_i (k)= h(k) mod(2^i n)
• h_i+1 удвостручује домет h_i

Алгоритам за уметање 'к' и провере стање прекорачења

• b = h₀(k)
• ако b < показивача онда
• b = h₁(k)

Претраживање у хеш табели за 'к'

• b = h₀(k)
• Ако b < показивача
• b = h₁(k)

Усвајање у језичким системима

Грисволд и Товнсенд су разговарали о усвајању линеарног хеширање у језику Иконица. Они су разговарали о алтернативама динамичког низа алгоритма који се користи у имплементацији линеарног хеширања,и представио поређења перформанси коришћења листа у аплкикацији за Иконице.

Усвајање у системима база података

Линеарно хеширање се користи у систему базе података БДБ Беркли, који заузврат користи од стране многих софтверских система, као што су ОпенЛДАП, користећи имплементацију Ц изведен из ЦАЦМ чланка и први објављен у Усенет у 1988 од стране Есмонд Питт.

Додатни линкови

• 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

Види још

• Проширено хеширање
• Конзистентан хеш