Linearno popunjavanje

Linearno popunjavanje (енгл. Linear probing) je jedan od načina za obradu heš kolizija vrednosti heš funkcija. To je jednostavno rešenje koje podrazumeva da, u slučaju da je mesto u heš tabeli zauzeto, upisuje novu vrednost na prvu sledeću slobodnu lokaciju od ove određene heš funkcijom. Ovo se postiže korišćenjem dve vrednosti, one dobijene heš funkcijom za zadatu vrednost(ključ) i pomoćne. Pomoćna vrednost je početno 0 i predstavlja udaljenje do potencijalno slobodne lokacije. Ovo udaljenje zapravo predstavlja kretanje funkcije u tabeli, od vrednosti predviđene heš funkcijom do prve slobodne lokacije.

Ako je h1(x) heš funkcija za ključ x, n dimenzija heš tabele, a i udaljenje, tada funkcija linearnog popunjavanja h(x,i) ima oblik:

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

Deo %n je neophodan kako bi iza lokacije n-1 sledila lokacija 0. U ovoj formuli i se povećava za 1 kada je lokacija na koju trenutno pokazuje formula zauzeta.

Problemi i efikasnost

Linearno popunjavanje je efikasno ako je tabela relativno retko popunjena. U protivnom dolaziće do mnogo sekundarnih kolizija, odnosno kolizija prouzrokovanih slučajevima sa različitim vrednostima heš funkcije (a ne istim, kao u slučaju obične kolizije). Na primer, neka je lokacija i zauzeta, a lokacija i+1 slobodna. Novi ključ koji se preslikava u i prouzrokuje koliziju, i smešta se na lokaciju i+1. Do ovog trenutka problemi su rešeni efikasno, uz minimalni napor. Međutim, ako se novi ključ preslika u i+1, imamo slučaj sekundarne kolizije, a lokacija i+2 postaje zauzeta (ako već nije bila). Svaki novi ključ preslikan u i, i+1 ili i+2, ne samo da izaziva novu sekundarnu koliziju, nego i povećava veličinu ovog popunjenog odsečka, što kasnije izaziva još više sekundarnih kolizija. Ovo je tzv. efekat grupisanja. Kad je tabela skoro puna, broj sekundarnih kolizija pri linearnom popunjavnju je vrlo veliki,pa se pretraga degradira u linearnu.

Pri linearnom popunjavanju se brisanja ne mogu uvek izvesti korektno. Ako je pri upisu ključa došlo do kolizije i on je upisan linearnim popunjavanjem, u slučaju da se obriše neki od ključeva između tog kog želimo da obrišemo i njegove pozicije određene heš funkcijom, nije moguće doći do tog ključa, osim linearnom pretragom.

Vidi još

• Dvostruko heširanje

Литература

• Dale, Nell (2003). C++ Plus Data Structures. Sudbury, MA: Jones and Bartlett Computer Science. ISBN 978-0-7637-0481-0. 

Spoljašnje veze

• Algoritmi, Miodrag Živković
• How Caching Affects Hashing, Gregory L. Heileman and Wenbin Luo 2005.
• Open Data Structures - Section 5.2 - LinearHashTable: Linear Probing