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.^[1] 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:

${\displaystyle 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.

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