懶惰刪除

在計算機科學中,懶惰刪除(英文:lazy deletion)指的是從一個散列表(也稱哈希表)中刪除元素的一種方法。在這個方法中,刪除僅僅是指標記一個元素被刪除,而不是整個清除它。被刪除的位點在插入時被當作空元素,在搜尋之時被當作已占據。

基本介紹

  • 中文名:懶惰刪除
  • 外文名:lazy deletion
  • 類別:計算機
原理,示例,

原理

當刪除一個元素時,ISBF需要調整其他元素的片外索引值,並重新構建所有片上CBF,這將導致其刪除開銷高,難以支持動態變化的元素集.為了降低ISBF的刪除開銷,本文提出了一-種懶惰刪除(lazy deletion) 算法,其核心思想是:採用一個片,上刪除點陣圖,用於記錄片外元素的狀態,即0表示未刪除狀態, 1表示刪除狀態;當刪除元素x時,在刪除點陣圖中設定x的狀態位為1, 並從每組並行CBF中刪除r,保持其他元素的片外索引值不變。

示例

// javascript
var myarr=["frist","2nd","3rd","4th"];
delete myarr[2]; // 刪除第3個 "3rd"
console.info(myarr);// 輸出
0: "frist"
1: "2nd"
3: "4th"
注意1後面是3
這時,如果檢測數組長度,由於是懶惰刪除,因此
console.info(myarr.length);
結果為4。

相關詞條

熱門詞條

聯絡我們