[發(fā)明專利]基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)及方法

在審

• 申請?zhí)枺?/td>: 202010630817.2
• 申請日: 2020-07-02
• 公開（公告）號: CN111930924A
• 公開（公告）日: 2020-11-13
• 發(fā)明（設(shè)計）人: 方賢斌;曠黎明;師文慶
• 申請（專利權(quán)）人: 上海微億智造科技有限公司;常州微億智造科技有限公司
• 主分類號: G06F16/335
• 分類號: G06F16/335
• 代理公司: 上海段和段律師事務(wù)所 31334
• 代理人: 李佳俊;郭國中

1.一種基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)，其特征在于，包括：

初始化過濾器模塊：每個過濾器初始化時需要傳入p與n兩個參數(shù)，n為插入的元素個數(shù)，p為誤報率，生成哈希函數(shù)個數(shù)numHashFunctions和布隆過濾器長度bitSize；

計算過濾器bit數(shù)組模塊：根據(jù)初始化過濾器生成的numHashFunctions和bitSize以及傳入的被計算的值key這三個數(shù)據(jù)生成一個value，所述value根據(jù)numHashFunctions生成多個long類型值，然后將多個long類型值根據(jù)bitSize生成多個int類型的bit數(shù)組，最終返回bit數(shù)組；

判重模塊：根據(jù)返回的bit數(shù)組進行循環(huán)獲得每一個bit值，在數(shù)據(jù)庫Redis中查詢每一個bit值在數(shù)據(jù)庫Redis里面bit位的值：如果值為0，則表示沒有任何一個值映射到這個bit位上，value這個值不存在；如果返回的值為1，這value這個值已經(jīng)存在。

2.根據(jù)權(quán)利要求1所述的基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)，其特征在于，所述numHashFunctions和bitSize決定過濾器bit位的長度；

過濾器bit位的長度會影響過濾器最終的查詢與更新值的效率與錯誤率。

3.根據(jù)權(quán)利要求1所述的基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)，其特征在于，所述生成一個value的過程包括：

初始化value數(shù)組值，數(shù)組長度為numHashFunctions，用戶使用過濾器時會傳入需要被驗證的值key，然后把key生成hash 64位的long類型值，把這個long類型值生成10位長度的int類型值hash1，再用這個long類型值無符號右移32位生成10位長度的int類型值hash2；

然后按照numHashFunctions長度來循環(huán)，按照hash1+i*hash2的計算方法生成nextHash值，i是循環(huán)下標(biāo)，判斷nextHash值是否小于0，小于0就對nextHash值取反運算；

然后給value賦值，值生成方法為：bitSize對nextHash取余運算：bit＝nextHash％bitSize，bit值的大小不超過bitSize值。

4.根據(jù)權(quán)利要求1所述的基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)，其特征在于，所述傳入的被計算的值key指用戶傳入的數(shù)據(jù)；

一個數(shù)據(jù)對應(yīng)一個key值，通過key值查詢對應(yīng)的數(shù)據(jù)在過濾器中是否存在。

5.根據(jù)權(quán)利要求1所述的基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)，其特征在于，所述生成哈希函數(shù)個數(shù)numHashFunctions和布隆過濾器長度bitSize的具體算法如下：

如果算出來的numHashFunctions值小于等于3，則numHashFunctions取固定值3，禁止其小于3。

6.根據(jù)權(quán)利要求1所述的基于布隆過濾器的數(shù)據(jù)查重系統(tǒng)，其特征在于，所述p與n兩個參數(shù)為動態(tài)；

countValue值指記錄項目實際過濾或存儲的值，初始化為0，根據(jù)實際使用數(shù)量遞增，存放在Redis中保存；

n值表示預(yù)訂的過濾值個數(shù)，當(dāng)countValue值的值等于n時，n值就會被重新初始化，重新初始化的值為：n乘2，也就是以n值為基礎(chǔ)倍數(shù)擴增

p值表示可接受的數(shù)據(jù)過濾誤判概率，當(dāng)countValue值的值等于n時，p值就會被重新初始化，重新初始化的值為：p除2。