懒惰删除
懒惰删除
在计算机科学中,懒惰删除(英文:lazy deletion)指的是从一个散列表(也称哈希表)中删除元素的一种方法。在这个方法中,删除仅仅是指标记一个元素被删除,而不是整个清除它。被删除的位点在插入时被当作空元素,在搜索之时被当作已占据。
原理
当删除一个元素时,ISBF需要调整其他元素的片外索引值,并重新构建所有片上CBF,这将导致其删除开销高,难以支持动态变化的元素集.为了降低ISBF的删除开销,本文提出了一-种懒惰删除(lazy deletion) 算法,其核心思想是:采用一个片,上删除位图,用于记录片外元素的状态,即0表示未删除状态, 1表示删除状态;当删除元素x时,在删除位图中设置x的状态位为1, 并从每组并行CBF中删除r,保持其他元素的片外索引值不变。
示例
// javascript
console.info(myarr);// 输出
注意1后面是3
这时,如果检测数组长度,由于是懒惰删除,因此
console.info(myarr.length);
结果为4。
参考资料
懒惰删除.course.2010-06-02
最新修订时间:2022-08-25 16:55
目录
概述
原理
示例
参考资料