Лењо брисање

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

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

Проблем са овом шемом је да број обрисаних/убачених операција повећава цену успешнг повећања претраге. Да би унапредили ово, када је елемент тражен и нађен у табели, елемент је реалоциран на прву локацију означеног брисања која је испитивана током претраге. Уместо тражења елемента за реалокацију када дође до брисања, реалокација се одвија лењо током следеће претраге.[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