Back

ⓘ Linearno popunjavanje




Linearno popunjavanje
                                     

ⓘ Linearno popunjavanje

Linearno popunjavanje 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 odredene heš funkcijom. Ovo se postiže korišćenjem dve vrednosti, one dobijene heš funkcijom za zadatu vrednost 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 predvidene heš funkcijom do prve slobodne lokacije.

Ako je h1x heš funkcija za ključ x, n dimenzija heš tabele, a i udaljenje, tada funkcija linearnog popunjavanja hx,i ima oblik:

h x, i = h 1 x + i) % n, i = 0, 1., n − 1 {\displaystyle hx,i=h1x+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.

                                     

1. 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. Medutim, 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 izmedu tog kog želimo da obrišemo i njegove pozicije odredene heš funkcijom, nije moguće doći do tog ključa, osim linearnom pretragom.

                                     

2. Spoljašnje veze

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