게으름 삭제
Lazy deletion컴퓨터 공학에서 게으른 삭제는 오픈 어드레싱을 사용하는 해시 테이블에서 요소를 삭제하는 방법을 말한다.이 방법에서는 요소를 완전히 지우기보다는 삭제된 것으로 표시하여 삭제한다.삭제된 위치는 삽입할 때 비어 있는 것으로 처리되고 검색 중에 점유된 것으로 처리된다.
이 계획의 문제는 삭제/삽입 작업의 수가 증가함에 따라 성공적인 검색의 비용이 증가한다는 것이다.이를 개선하기 위해 표에서 요소를 검색하여 찾으면 검색 중에 검색한 첫 번째 삭제 표시 위치로 요소를 재배치한다.삭제가 발생했을 때 재배치할 요소를 찾는 대신 다음 검색 과정에서 느리게 재배치가 이뤄진다.[1][2]
참조
- ^ Celis, Pedro; Franco, John (1995), The Analysis of Hashing with Lazy Deletions, Computer Science Department, Indiana University, CiteSeerX 10.1.1.39.9637, Technical Report CS-86-14
- ^ Celis, Pedro; Franco, John (1992), "The analysis of hashing with lazy deletions", Information Sciences, 62 (1–2): 13–26, CiteSeerX 10.1.1.39.9637, doi:10.1016/0020-0255(92)90022-Z
