[發明專利]一種支持刪除的布隆過濾的設計方法

在審

• 申請號: 202010840232.3
• 申請日: 2020-08-19
• 公開（公告）號: CN112818188A
• 公開（公告）日: 2021-05-18
• 發明（設計）人: 趙星晨;張一帆;林芷竹
• 申請（專利權）人: 北京辰信領創信息技術有限公司
• 主分類號: G06F16/9035
• 分類號: G06F16/9035
• 代理公司: 上海氦閃專利代理事務所(普通合伙) 31354
• 代理人: 李明;袁媛

本發明涉及計算機信息處理領域，尤其是一種支持刪除的布隆過濾的設計方法，包括m字節的字節數組,初始時每個字節都初始化為0,增加一個元素時,k個字節位置至少有一個為0時，每個位置的值都在原來基礎上加1；刪除時，k個字節位置每個都大于0時，每個位置的值都在原來基礎上減1；查詢時，k個字節位置只要有一個位置的值為0，說明元素不在集合中；本發明稍微修改傳統的布隆過濾器的數據結構，可以實現布隆過濾器的刪除，并且，不影響查詢效率。

技術領域

本發明涉及計算機信息處理領域，尤其涉及一種支持刪除的布隆過濾的設計方法。

背景技術

在海量的數據中，需要高效的將數據添加到數據集中；并可以方便高效的查詢是否有數據在數據集，有時則需要刪除數據集中的數據；布隆過濾器是一種數據結構，比較巧妙的概率型數據結構，特點是高效地插入和查詢，可以用來告訴你“某樣東西一定不存在或者可能存在。

目前市場上的布隆過濾器存在的缺陷：傳統的布隆過濾器并不支持刪除操作，為了能夠消減數據集中無用的數據，就需要一種可以進行刪除操作的布隆過濾器，同時不能降低了現有布隆過濾器添加和查詢數據的效率。

發明內容

本發明的目的是為了解決現有技術中存在的缺點，而提出的一種支持刪除的布隆過濾的設計方法。

為達到以上目的，本發明采用的技術方案為：一種支持刪除的布隆過濾的設計方法，包括以下方法：

(i)將一個布隆過濾器中設有的m字節的字節數組初始化為0；

(ii)定義k個不同的哈希函數，并將k個哈希函數每一個都以均勻隨機分布的方式映射到m字節的字節數組不同位置中的一個，取用外部元素時，用k個哈希函數將元素經由散列函數處理得到布隆過濾器中k個字節；

(iii)增加一個元素時，k個字節位置至少有一個為0時，每個位置的值都在原來基礎上加1；如果k個位置均大于0，那么元素可能已經設置于集合中；

(iv)刪除一個元素時，k個字節位置每個都大于0時，每個位置的值都在原來基礎上減1；

(v)查詢一個元素時，k個字節位置只要有一個位置的值為0，說明元素不在集合中。

進一步的，一種支持刪除的布隆過濾器的設計方法，還包括以下方法：

(i)將一個布隆過濾器中設有的m個整型數據的int數組初始化為0；

(ii)定義k個不同的哈希函數，并將k個哈希函數每一個都以均勻隨機分布的方式映射到m個整型數據的int數組不同位置中的一個，取用外部元素時，用k個哈希函數將元素經由散列函數處理得到布隆過濾器中k個位置；

(iii)增加一個元素時，k個字節位置至少有一個為0時，每個位置的值都在原來基礎上加1；如果k個位置均大于0，那么元素可能已經設置于集合中；

(iv)刪除一個元素時，k個字節位置每個都大于0時，每個位置的值都在原來基礎上減1；

(v)查詢一個元素時，k個字節位置只要有一個位置的值為0，說明元素不在集合中。

與現有技術相比，本發明具有以下有益效果：可以高效的支持布隆過濾器的刪除操作，且并不影響添加和查詢數據的效率。

本發明的其他優點、目標和特征在某種程度上將在隨后的說明書中進行闡述，并且在某種程度上，基于對下文的考察研究對本領域技術人員而言將是顯而易見的，或者可以從本發明的實踐中得到教導。本發明的目標和其他優點可以通過下面的說明書來實現和獲得。

具體實施方式

為使本發明實施例的目的、技術方案和優點更加清楚，下面將對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例是本發明一部分實施例，而不是全部的實施例。