Линеарно попуњавање

Линеарно попуњавање (енгл. Linear probing) је један од начина за обраду хеш колизија вредности хеш функција. То је једноставно решење које подразумева да, у случају да је место у хеш табели заузето, уписује нову вредност на прву следећу слободну локацију од ове одређене хеш функцијом. Ово се постиже коришћењем две вредности, оне добијене хеш функцијом за задату вредност(кључ) и помоћне. Помоћна вредност је почетно 0 и представља удаљење до потенцијално слободне локације. Ово удаљење заправо представља кретање функције у табели, од вредности предвиђене хеш функцијом до прве слободне локације.

Ако је h1(x) хеш функција за кључ x, н димензија хеш табеле, а и удаљење, тада функција линеарног попуњавања х(x,и) има облик:

$h(x,i)=(h1(x)+i)\%n,i=0,1,...,n-1$

Део %н је неопходан како би иза локације н-1 следила локација 0. У овој формули i се повећава за 1 када је локација на коју тренутно показује формула заузета.

Проблеми и ефикасност

Линеарно попуњавање је ефикасно ако је табела релативно ретко попуњена. У противном долазиће до много секундарних колизија, односно колизија проузрокованих случајевима са различитим вредностима хеш функције (а не истим, као у случају обичне колизије). На пример, нека је локација i заузета, а локација i+1 слободна. Нови кључ који се пресликава у i проузрокује колизију, и смешта се на локацију i+1. До овог тренутка проблеми су решени ефикасно, уз минимални напор. Међутим, ако се нови кључ преслика у i+1, имамо случај секундарне колизије, а локација i+2 постаје заузета (ако већ није била). Сваки нови кључ пресликан у i, i+1 или i+2, не само да изазива нову секундарну колизију, него и повећава величину овог попуњеног одсечка, што касније изазива још више секундарних колизија. Ово је тзв. ефекат груписања. Кад је табела скоро пуна, број секундарних колизија при линеарном попуњавњу је врло велики,па се претрага деградира у линеарну.

При линеарном попуњавању се брисања не могу увек извести коректно. Ако је при упису кључа дошло до колизије и он је уписан линеарним попуњавањем, у случају да се обрише неки од кључева између тог ког желимо да обришемо и његове позиције одређене хеш функцијом, није могуће доћи до тог кључа, осим линеарном претрагом.

Види још

• Двоструко хеширање

Литература

• Дале, Нелл (2003). C++ Плус Дата Струцтурес. Судбурy, МА: Јонес анд Бартлетт Цомпутер Сциенце. ИСБН 978-0-7637-0481-0. 

Спољашње везе

• Алгоритми, Миодраг Живковић
• Хоw Цацхинг Аффецтс Хасхинг, Грегорy L. Хеилеман анд Wенбин Луо 2005.
• Опен Дата Струцтурес - Сецтион 5.2 - ЛинеарХасхТабле: Линеар Пробинг