Пређи на садржај

Лењо брисање

С Википедије, слободне енциклопедије

У рачунарским наукама, лењо брисање се односи на метод брисања из хеш табела које користе отворено адресирање. Овом методом, брисање се обавља означавањем елемената, уместо потпуним брисањем. Обрисане локације се третирају као празне када се убацују нове и заузете приликом претраге.

Проблем са овом шемом је да број обрисаних/убачених операција повећава цену успешног повећања претраге. Да би унапредили ово, када је елемент тражен и нађен у табели, елемент је реалоциран на прву локацију означеног брисања која је испитивана током претраге. Уместо тражења елемента за реалокацију када дође до брисања, реалокација се одвија лењо током следеће претраге.[1][2]

Референце

[уреди | уреди извор]
  1. ^ Celis, Pedro; Franco, John (1995), The Analysis of Hashing with Lazy Deletions, Computer Science Department, Indiana University, Technical Report CS-86-14 
  2. ^ Celis, Pedro; Franco, John (1992), „The analysis of hashing with lazy deletions”, Information Sciences, 62: 13, doi:10.1016/0020-0255(92)90022-Z