[發(fā)明專(zhuān)利]一種支持刪除的布隆過(guò)濾的設(shè)計(jì)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010840232.3
• 申請(qǐng)日: 2020-08-19
• 公開(kāi)（公告）號(hào): CN112818188A
• 公開(kāi)（公告）日: 2021-05-18
• 發(fā)明（設(shè)計(jì)）人: 趙星晨;張一帆;林芷竹
• 申請(qǐng)（專(zhuān)利權(quán)）人: 北京辰信領(lǐng)創(chuàng)信息技術(shù)有限公司
• 主分類(lèi)號(hào): G06F16/9035
• 分類(lèi)號(hào): G06F16/9035
• 代理公司: 上海氦閃專(zhuān)利代理事務(wù)所(普通合伙) 31354
• 代理人: 李明;袁媛

1.一種支持刪除的布隆過(guò)濾的設(shè)計(jì)方法，其特征在于，包括以下方法：

(i)將一個(gè)布隆過(guò)濾器中設(shè)有的m字節(jié)的字節(jié)數(shù)組初始化為0；

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

(iii)增加一個(gè)元素時(shí)，k個(gè)字節(jié)位置至少有一個(gè)為0時(shí)，每個(gè)位置的值都在原來(lái)基礎(chǔ)上加1；如果k個(gè)位置均大于0時(shí)，那么元素可能已經(jīng)設(shè)置于集合中；

(iv)刪除一個(gè)元素時(shí)，k個(gè)字節(jié)位置每個(gè)都大于0時(shí)，每個(gè)位置的值都在原來(lái)基礎(chǔ)上減1；

(v)查詢(xún)一個(gè)元素時(shí)，k個(gè)字節(jié)位置只要有一個(gè)位置的值為0，說(shuō)明元素不在集合中。

2.一種支持刪除的布隆過(guò)濾器的設(shè)計(jì)方法，其特征在于，還包括以下方法：

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

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

(iii)增加一個(gè)元素時(shí)，k個(gè)int位置至少有一個(gè)為0時(shí)，每個(gè)位置的值都在原來(lái)基礎(chǔ)上加1；如果k個(gè)位置均大于0，那么元素可能已經(jīng)設(shè)置于集合中；

(iv)刪除一個(gè)元素時(shí)，k個(gè)int位置每個(gè)都大于0時(shí)，每個(gè)位置的值都在原來(lái)基礎(chǔ)上減1；

(v)查詢(xún)一個(gè)元素時(shí)，k個(gè)int位置只要有一個(gè)位置的值為0，說(shuō)明元素不在集合中。