布隆过滤器系统及过滤方法

摘要

本发明提供了一种布隆过滤器系统及过滤方法，包括：初始化过滤器模块：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize。本发明极大节省了单次处理时间与降低实际滤误判概率，过滤器会达到更稳定更可靠。不会因为后期数据量大了之后过滤器处理时间长而拖累其它程序服务使用。在量化效果上用改造后的过滤器比现有过滤器的综合性能快100倍左右。

权利要求

1.一种布隆过滤器系统，其特征在于，包括：初始化过滤器模块：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize；

计算过滤器bit数组模块：根据初始化过滤器生成的numHashFunctions和bitSize以及传入的被计算的值key这三个数据生成一个value，所述value根据numHashFunctions生成多个long类型值，然后将多个long类型值根据bitSize生成多个int类型的bit数组，最终返回bit数组；

判重模块：根据返回的bit数组进行循环获得每一个bit值，在数据库Redis中查询每一个bit值在数据库Redis里面bit位的值：如果值为0，则表示没有任何一个值映射到这个bit位上，value这个值不存在，调用更新或存储过滤器模块；如果返回的值为1，这value这个值已经存在，调用删除过滤器模块；

更新或存储过滤器模块：如果判断value这个值不存在于过滤器中后，就把返回的bit数组分别指向到bit位置，存储到Redis中存储；

删除过滤器模块：如果判断value这个值已经存在于过滤器中，则传入的被计算的值key为需要删除的key值，根据单个bit位把删除过滤器的计数器Counter的值减1，逐个处理；

初始化的n与p值后就可以控制bitSize与numHashFunctions值的生成大小，从而实现把新增到Redis中的值分区，每个区段的值有长度限制从而达到相互不影响的目的；

所述numHashFunctions和bitSize决定过滤器bit位的长度；

过滤器bit位的长度会影响过滤器最终的查询与更新值的效率与错误率；

所述生成一个value的过程包括：

初始化value数组值，数组长度为numHashFunctions，用户使用过滤器时会传入需要被验证的值key，然后把key生成hash 64位的long类型值，把这个long类型值生成10位长度的int类型值hash1，再用这个long类型值无符号右移>>>32位生成10位长度的int类型值hash2；

然后按照numHashFunctions长度来循环，按照hash1+i*hash2的计算方法生成nextHash值，i是循环下标，判断nextHash值是否小于0，小于0就对nextHash值取反运算；

然后给value赋值，值生成方法为：bitSize对nextHash取余运算：bit＝nextHash％bitSize，bit值的大小不超过bitSize值；

通过采用把p与n两个参数变为动态，改造计算过滤器bit数组，包括初始化过滤器、计算过滤器bit数组、更新/存储过滤器；在更新/存储过滤器时创建一个新的key：countValue，用来存储统计过滤器存放过的value的数量，通过countValue知道已经存放的value总量，按照n等于2亿数据量来切分n，把n等分或按照比例分为100份，相当于划分100个区间，根据countValue大小当countValue每到达一个等份值时则更新p与n两个参数，使其根据实际数据量增大而改变从而改变numHashFunctions和bitSize；bitSize的大小在

100个区间里的每个区间中它的值是成倍数关系的，这样的倍数关系会改变过滤器bit数组中每个bit位大小的区间；当每个bit位大小的在100个区间中时相当于把过滤器所有的bit位划分了100份相对独立的空间存储；

countValue：记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存；

n值：表示预订的过滤值个数，初始化为2000000，以2000000为单位把目标值200000000分100个区段，在项目运行过程中单个区段固定不变；但当countValue值的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数扩增；

p值：表示可接受的数据过滤误判概率，这个值的生成方法跟n值相同，初始化为

0.0000001，在运行过程中单个区段固定不变；但当countValue值的值等于n时，p值就会被重新初始化，重新初始化的值为：p除2；

把p与n两个参数变为动态，删除过滤器的计数器Counter的值根据countValue值到达的区间而等比例增大Counter大小，使得过滤器的每一个阶段拥有自己Counter，实现平衡空间利用率与资源占用的矛盾，保证过滤器的使用效率；

当传入需要删除的value后，根据单个bit位把计数器Counter的值减1，逐个处理；

使numHashFunctions永远不会接近为1，控制到最小值接近或等于3，达到使过滤器的错误率不会降低。

2.根据权利要求1所述的布隆过滤器系统，其特征在于，所述传入的被计算的值key指用户传入的数据；

一个数据对应一个key值，通过key值查询对应的数据在过滤器中是否存在。

3.根据权利要求1所述的布隆过滤器系统，其特征在于，所述生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize的具体算法如下：如果算出来的numHashFunctions值小于等于3，则numHashFunctions取固定值3，禁止其小于3。

4.一种布隆过滤器的过滤方法，其特征在于，包括：初始化过滤器步骤：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize；

计算过滤器bit数组步骤：根据初始化过滤器生成的numHashFunctions和bitSize以及传入的被计算的值key这三个数据生成一个value，所述value根据numHashFunctions生成多个long类型值，然后将多个long类型值根据bitSize生成多个int类型的bit数组，最终返回bit数组；

判重步骤：根据返回的bit数组进行循环获得每一个bit值，在数据库Redis中查询每一个bit值在数据库Redis里面bit位的值：如果值为0，则表示没有任何一个值映射到这个bit位上，value这个值不存在，调用更新或存储过滤器步骤；如果返回的值为1，这value这个值已经存在，调用删除过滤器步骤；

更新或存储过滤器步骤：如果判断value这个值不存在于过滤器中后，就可以把返回的bit数组分别指向到bit位置，存储到Redis中存储；

删除过滤器步骤：如果判断value这个值已经存在于过滤器中，则传入的被计算的值key为需要删除的key值，根据单个bit位把删除过滤器的计数器Counter的值减1，逐个处理；

初始化的n与p值后就可以控制bitSize与numHashFunctions值的生成大小，从而实现把新增到Redis中的值分区，每个区段的值有长度限制从而达到相互不影响的目的；

所述numHashFunctions和bitSize决定过滤器bit位的长度；

过滤器bit位的长度会影响过滤器最终的查询与更新值的效率与错误率；

所述传入的被计算的值key指用户传入的数据；

一个数据对应一个key值，通过key值查询对应的数据在过滤器中是否存在；

所述生成一个value的过程包括：

初始化value数组值，数组长度为numHashFunctions，用户使用过滤器时会传入需要被验证的值key，然后把key生成hash 64位的long类型值，把这个long类型值生成10位长度的int类型值hash1，再用这个long类型值无符号右移>>>32位生成10位长度的int类型值hash2；

然后按照numHashFunctions长度来循环，按照hash1+i*hash2的计算方法生成nextHash值，i是循环下标，判断nextHash值是否小于0，小于0就对nextHash值取反运算；

然后给value赋值，值生成方法为：bitSize对nextHash取余运算：bit＝nextHash％bitSize，bit值的大小不超过bitSize值；

通过采用把p与n两个参数变为动态，改造计算过滤器bit数组，包括初始化过滤器、计算过滤器bit数组、更新/存储过滤器；在更新/存储过滤器时创建一个新的key：countValue，用来存储统计过滤器存放过的value的数量，通过countValue知道已经存放的value总量，按照n等于2亿数据量来切分n，把n等分或按照比例分为100份，相当于划分100个区间，根据countValue大小当countValue每到达一个等份值时则更新p与n两个参数，使其根据实际数据量增大而改变从而改变numHashFunctions和bitSize；bitSize的大小在

100个区间里的每个区间中它的值是成倍数关系的，这样的倍数关系会改变过滤器bit数组中每个bit位大小的区间；当每个bit位大小的在100个区间中时相当于把过滤器所有的bit位划分了100份相对独立的空间存储；

countValue：记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存；

n值：表示预订的过滤值个数，初始化为2000000，以2000000为单位把目标值200000000分100个区段，在项目运行过程中单个区段固定不变；但当countValue的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数扩增；

p值：表示可接受的数据过滤误判概率，这个值的生成方法跟n值相同，初始化为

0.0000001，在运行过程中单个区段固定不变；但当countValue的值等于n时，p值就会被重新初始化，重新初始化的值为：p除2；

把p与n两个参数变为动态，删除过滤器的计数器Counter的值根据countValue值到达的区间而等比例增大Counter大小，使得过滤器的每一个阶段拥有自己Counter，实现平衡空间利用率与资源占用的矛盾，保证过滤器的使用效率；

当传入需要删除的value后，根据单个bit位把计数器Counter的值减1，逐个处理；

使numHashFunctions永远不会接近为1，控制到最小值接近或等于3，达到使过滤器的错误率不会降低。

5.根据权利要求4所述的布隆过滤器的过滤方法，其特征在于，所述生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize的具体算法如下：如果算出来的numHashFunctions值小于等于3，则numHashFunctions取固定值3，禁止其小于3。

说明书

布隆过滤器系统及过滤方法

技术领域

[0001] 本发明涉及数据过滤技术领域，具体地，涉及布隆过滤器系统及过滤方法。

背景技术

[0002] 随着技术发展与数据量的增加，为了最求大数据量的准确性与可用性成为了发展很快的方向，不论在互联网大数据上还是在工业大数据场景中涉及的越来越多的应用场
景。

[0003] 目前相关领域存在着很多的过滤器插件，但在使用过程中发现有很多的弊端与瓶颈，如在过滤器过滤速度上与过滤错误率上随着数据量的增大而过滤速度呈曲线降低，错
误率也呈现曲线上升，很多公司在解决问题时采用投入更多硬件资源来集群，但是效果也
差强人意且比较耗费成本。

[0004] 如果不处理p与n两个参数的话会使numHashFunctions变的越来越小和bitSize在一开始就过大，而numHashFunctions变小和bitSize变大后会导致布隆过滤器效率低下，且
每个bit位都在同一个区间内，当数据量增大后后续生成value值生成相同bit值的概率变
的越来越大，当不同value值得单个bit值重复率变大时，过滤器生成的bit数组相同的概率
会同步增加，这种概率增加对过滤器来说是致命的，应为过滤的目的是处理大量数据的准
确性与可用性，如果过滤器失去了这个属性，则降低了过滤器的实际作用。bitSize的变大
会导致存储在过滤器中的空间更多，对资源占用更大，当存储的value越多时会造成过滤器
的更新/存储、读取的性能变的低下。

[0005] 如果因为内存庞大而造成在实际业务中使用过滤器时拖累性能，在高并发，高可用的应用场景中是非常危险的，会影响其它业务的处理能力。在过滤器很重要且性能也很
重要的情况下，提高过滤器的性能与高可用性变成是唯一的选择。

发明内容

[0006] 针对现有技术中的缺陷，本发明的目的是提供一种布隆过滤器系统及过滤方法。

[0007] 根据本发明提供的一种布隆过滤器系统，包括：

[0008] 初始化过滤器模块：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize；

[0009] 计算过滤器bit数组模块：根据初始化过滤器生成的numHashFunctions和bitSize以及传入的被计算的值key这三个数据生成一个value，所述value根据numHashFunctions
生成多个long类型值，然后将多个long类型值根据bitSize生成多个int类型的bit数组，最
终返回bit数组；

[0010] 判重模块：根据返回的bit数组进行循环获得每一个bit值，在数据库Redis中查询每一个bit值在数据库Redis里面bit位的值：如果值为0，则表示没有任何一个值映射到这
个bit位上，value这个值不存在，调用更新或存储过滤器模块；如果返回的值为1，这value
这个值已经存在，调用删除过滤器模块；

[0011] 更新或存储过滤器模块：如果判断value这个值不存在于过滤器中后，就可以把返回的bit数组分别指向到bit位置，存储到Redis中存储；

[0012] 删除过滤器模块：如果判断value这个值已经存在于过滤器中，则传入的被计算的值key为需要删除的key值，根据单个bit位把删除过滤器的计数器Counter的值减1，逐个处
理。

[0013] 优选地，所述numHashFunctions和bitSize决定过滤器bit位的长度；

[0014] 过滤器bit位的长度会影响过滤器最终的查询与更新值的效率与错误率。

[0015] 优选地，所述生成一个value的过程包括：

[0016] 初始化value数组值，数组长度为numHashFunctions，用户使用过滤器时会传入需要被验证的值key，然后把key生成hash 64位的long类型值，把这个long类型值生成10位长
度的int类型值hash1，再用这个long类型值无符号右移>>>32位生成10位长度的int类型值
hash2；

[0017] 然后按照numHashFunctions长度来循环，按照hash1+i*hash2的计算方法生成nextHash值，i是循环下标，判断nextHash值是否小于0，小于0就对nextHash值取反运算；

[0018] 然后给value赋值，值生成方法为：bitSize对nextHash取余运算：bit＝nextHash％bitSize，bit值的大小不超过bitSize值。

[0019] 优选地，所述传入的被计算的值key指用户传入的数据；

[0020] 一个数据对应一个key值，通过key值查询对应的数据在过滤器中是否存在。

[0021] 优选地，所述生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize的具体算法如下：

[0022]

[0023]

[0024] 如果算出来的numHashFunctions值小于等于3，则numHashFunctions取固定值3，禁止其小于3。

[0025] 优选地，所述p与n两个参数为动态；

[0026] countValue值指记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存；

[0027] n值表示预订的过滤值个数，当countValue值的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数扩增

[0028] p值表示可接受的数据过滤误判概率，当countValue值的值等于n时，p值就会被重新初始化，重新初始化的值为：p除2。

[0029] 根据本发明提供的一种布隆过滤器的过滤方法，包括：

[0030] 初始化过滤器步骤：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize；

[0031] 计算过滤器bit数组步骤：根据初始化过滤器生成的numHashFunctions和bitSize以及传入的被计算的值key这三个数据生成一个value，所述value根据numHashFunctions
生成多个long类型值，然后将多个long类型值根据bitSize生成多个int类型的bit数组，最
终返回bit数组；

[0032] 判重步骤：根据返回的bit数组进行循环获得每一个bit值，在数据库Redis中查询每一个bit值在数据库Redis里面bit位的值：如果值为0，则表示没有任何一个值映射到这
个bit位上，value这个值不存在，调用更新或存储过滤器步骤；如果返回的值为1，这value
这个值已经存在，调用删除过滤器步骤；

[0033] 更新或存储过滤器步骤：如果判断value这个值不存在于过滤器中后，就可以把返回的bit数组分别指向到bit位置，存储到Redis中存储；

[0034] 删除过滤器步骤：如果判断value这个值已经存在于过滤器中，则传入的被计算的值key为需要删除的key值，根据单个bit位把删除过滤器的计数器Counter的值减1，逐个处
理。

[0035] 优选地，所述numHashFunctions和bitSize决定过滤器bit位的长度；

[0036] 过滤器bit位的长度会影响过滤器最终的查询与更新值的效率与错误率；

[0037] 所述传入的被计算的值key指用户传入的数据；

[0038] 一个数据对应一个key值，通过key值查询对应的数据在过滤器中是否存在。

[0039] 优选地，所述生成一个value的过程包括：

[0040] 初始化value数组值，数组长度为numHashFunctions，用户使用过滤器时会传入需要被验证的值key，然后把key生成hash 64位的long类型值，把这个long类型值生成10位长
度的int类型值hash1，再用这个long类型值无符号右移>>>32位生成10位长度的int类型值
hash2；

[0041] 然后按照numHashFunctions长度来循环，按照hash1+i*hash2的计算方法生成nextHash值，i是循环下标，判断nextHash值是否小于0，小于0就对nextHash值取反运算；

[0042] 然后给value赋值，值生成方法为：bitSize对nextHash取余运算：bit＝nextHash％bitSize，bit值的大小不超过bitSize值。

[0043] 优选地，所述生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize的具体算法如下：

[0044]

[0045]

[0046] 如果算出来的numHashFunctions值小于等于3，则numHashFunctions取固定值3，禁止其小于3；

[0047] 所述p与n两个参数为动态；

[0048] countValue值指记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存；

[0049] n值表示预订的过滤值个数，当countValue值的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数扩增

[0050] p值表示可接受的数据过滤误判概率，当countValue值的值等于n时，p值就会被重新初始化，重新初始化的值为：p除2。

[0051] 与现有技术相比，本发明具有如下的有益效果：

[0052] 本发明改造了初始化的n与p值后就可以控制bitSize与numHashFunctions值的生成大小，从而实现把新增到Redis中的值分区，每个区段的值有长度限制从而达到相互不影
响的目的。分区后就可以把公司200000000的数据量切分成100份，这样就相当于只用判定
2000000的小数据量而达到处理大数据量的好处，极大节省了单次处理时间与降低实际滤
误判概率，过滤器会达到更稳定更可靠。不会因为后期数据量大了之后过滤器处理时间长
而拖累其它程序服务使用。在量化效果上用改造后的过滤器比现有过滤器的综合性能快
100倍左右。

附图说明

[0053] 通过阅读参照以下附图对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显：

[0054] 图1为本发明提供的处理过滤数据重复性的过滤器的示意图。

具体实施方式

[0055] 下面结合具体实施例对本发明进行详细说明。以下实施例将有助于本领域的技术人员进一步理解本发明，但不以任何形式限制本发明。应当指出的是，对本领域的普通技术
人员来说，在不脱离本发明构思的前提下，还可以做出若干变化和改进。这些都属于本发明
的保护范围。

[0056] 根据本发明提供的一种布隆过滤器系统，包括：

[0057] 初始化过滤器模块：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize；

[0058] 计算过滤器bit数组模块：根据初始化过滤器生成的numHashFunctions和bitSize以及传入的被计算的值key这三个数据生成一个value，所述value根据numHashFunctions
生成多个long类型值，然后将多个long类型值根据bitSize生成多个int类型的bit数组，最
终返回bit数组；

[0059] 判重模块：根据返回的bit数组进行循环获得每一个bit值，在数据库Redis中查询每一个bit值在数据库Redis里面bit位的值：如果值为0，则表示没有任何一个值映射到这
个bit位上，value这个值不存在，调用更新或存储过滤器模块；如果返回的值为1，这value
这个值已经存在，调用删除过滤器模块；

[0060] 更新或存储过滤器模块：如果判断value这个值不存在于过滤器中后，就可以把返回的bit数组分别指向到bit位置，存储到Redis中存储；

[0061] 删除过滤器模块：如果判断value这个值已经存在于过滤器中，则传入的被计算的值key为需要删除的key值，根据单个bit位把删除过滤器的计数器Counter的值减1，逐个处
理。

[0062] 具体地，所述numHashFunctions和bitSize决定过滤器bit位的长度；

[0063] 过滤器bit位的长度会影响过滤器最终的查询与更新值的效率与错误率。

[0064] 具体地，所述生成一个value的过程包括：

[0065] 初始化value数组值，数组长度为numHashFunctions，用户使用过滤器时会传入需要被验证的值key，然后把key生成hash 64位的long类型值，把这个long类型值生成10位长
度的int类型值hash1，再用这个long类型值无符号右移>>>32位生成10位长度的int类型值
hash2；

[0066] 然后按照numHashFunctions长度来循环，按照hash1+i*hash2的计算方法生成nextHash值，i是循环下标，判断nextHash值是否小于0，小于0就对nextHash值取反运算；

[0067] 然后给value赋值，值生成方法为：bitSize对nextHash取余运算：bit＝nextHash％bitSize，bit值的大小不超过bitSize值。

[0068] 具体地，所述传入的被计算的值key指用户传入的数据；

[0069] 一个数据对应一个key值，通过key值查询对应的数据在过滤器中是否存在。

[0070] 具体地，所述生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize的具体算法如下：

[0071]

[0072]

[0073] 如果算出来的numHashFunctions值小于等于3，则numHashFunctions取固定值3，禁止其小于3。

[0074] 具体地，所述p与n两个参数为动态；

[0075] countValue值指记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存；

[0076] n值表示预订的过滤值个数，当countValue值的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数扩增

[0077] p值表示可接受的数据过滤误判概率，当countValue值的值等于n时，p值就会被重新初始化，重新初始化的值为：p除2。

[0078] 根据本发明提供的一种布隆过滤器的过滤方法，包括：

[0079] 初始化过滤器步骤：每个过滤器初始化时需要传入p与n两个参数，n为插入的元素个数，p为误报率，生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize；

[0080] 计算过滤器bit数组步骤：根据初始化过滤器生成的numHashFunctions和bitSize以及传入的被计算的值key这三个数据生成一个value，所述value根据numHashFunctions
生成多个long类型值，然后将多个long类型值根据bitSize生成多个int类型的bit数组，最
终返回bit数组；

[0081] 判重步骤：根据返回的bit数组进行循环获得每一个bit值，在数据库Redis中查询每一个bit值在数据库Redis里面bit位的值：如果值为0，则表示没有任何一个值映射到这
个bit位上，value这个值不存在，调用更新或存储过滤器步骤；如果返回的值为1，这value
这个值已经存在，调用删除过滤器步骤；

[0082] 更新或存储过滤器步骤：如果判断value这个值不存在于过滤器中后，就可以把返回的bit数组分别指向到bit位置，存储到Redis中存储；

[0083] 删除过滤器步骤：如果判断value这个值已经存在于过滤器中，则传入的被计算的值key为需要删除的key值，根据单个bit位把删除过滤器的计数器Counter的值减1，逐个处
理。

[0084] 具体地，所述numHashFunctions和bitSize决定过滤器bit位的长度；

[0085] 过滤器bit位的长度会影响过滤器最终的查询与更新值的效率与错误率；

[0086] 所述传入的被计算的值key指用户传入的数据；

[0087] 一个数据对应一个key值，通过key值查询对应的数据在过滤器中是否存在。

[0088] 具体地，所述生成一个value的过程包括：

[0089] 初始化value数组值，数组长度为numHashFunctions，用户使用过滤器时会传入需要被验证的值key，然后把key生成hash 64位的long类型值，把这个long类型值生成10位长
度的int类型值hash1，再用这个long类型值无符号右移>>>32位生成10位长度的int类型值
hash2；

[0090] 然后按照numHashFunctions长度来循环，按照hash1+i*hash2的计算方法生成nextHash值，i是循环下标，判断nextHash值是否小于0，小于0就对nextHash值取反运算；

[0091] 然后给value赋值，值生成方法为：bitSize对nextHash取余运算：bit＝nextHash％bitSize，bit值的大小不超过bitSize值。

[0092] 具体地，所述生成哈希函数个数numHashFunctions和布隆过滤器长度bitSize的具体算法如下：

[0093]

[0094]

[0095] 如果算出来的numHashFunctions值小于等于3，则numHashFunctions取固定值3，禁止其小于3；

[0096] 所述p与n两个参数为动态；

[0097] countValue值指记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存；

[0098] n值表示预订的过滤值个数，当countValue值的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数扩增

[0099] p值表示可接受的数据过滤误判概率，当countValue值的值等于n时，p值就会被重新初始化，重新初始化的值为：p除2。

[0100] 下面通过优选例，对本发明进行更为具体地说明。

[0101] 优选例1：

[0102] 本发明中解决了在大量数据下保证数据唯一性不重复的目的及高可用性，包括初始化过滤器阶段、计算过滤器bit数组、判断Redis中是否已经包含了过滤器bit数组、更新/
存储过滤器value值、删除数据后删除过滤器value值，各阶段是一个独立机制，但是相互组
成一个闭环整体。

[0103] 如图1所示，在大数据量背景下处理过滤数据重复性的过滤器，包括：

[0104] 初始化过滤器模块：每个过过滤器初始化时需要传入p与n两个参数(n为插入的元素个数，p为误报率)，生成哈希函数个数(numHashFunctions)和布隆过滤器长度
(bitSize)。初始化过滤器是重要步骤，是生成numHashFunctions和bitSize的基础，
numHashFunctions和bitSize是决定过滤器bit位的长度。而过滤器bit位的长度会影响过
滤器最终的查询与更新值的效率与错误率；

[0105] 计算过滤器bit数组模块：根据初始化过滤器生成的numHashFunctions、bitSize以及传入的被计算的值key(这个值是使用者传入的数据，也就是key值，一般来说一个数据
都会对应一个key值，使用者如果想知道某个数据时候在过滤器中存在时是需要用这个key
值去过滤器查询的，查询出来true就认为存在，如果为false则认为该值不存在)这三个数
据生成一个value：所述value根据numHashFunctions生成多个long类型值(Long是一个数
据类型,long关键字表示一种长整型数据，是编程语言中的一种基本数据类型，为long int
的缩写，默认为有符号长整型)，然后把多个long类型值根据bitSize生成多个int类型的
bit数组，最终返回bit数组；

[0106] 判重模块：根据返回的bit数组在Redis中查询每一个bit值在里面bit位的值，如果值为0则表示说明没有任何一个值映射到这个bit位上，因此我们可以很确定地说value
这个值不存在，如果返回的都为1，这value这个值可能已经存在；所述Redis就是一个存储/
查询数据的一个数据库(也可参考：https://baike.baidu.com/item/Redis/6549233？fr＝
aladdin)

[0107] 更新/存储过滤器模块：如果判断value这个值不存在于过滤器中后，就可以把返回的bit数组分别指向到bit位置，存储到Redis中存储；

[0108] 删除过滤器模块：当传入需要删除的value后，根据单个bit位把计数器(Counter)的值减1，逐个处理。

[0109] 本发明的发明点包括：

[0110] (1)通过采用改造numHashFunctions和bitSize生成算法，这个包括初始化阶段，根据初始化阶段传入p与n两个参数，生成numHashFunctions和bitSize，根据以前的算法，
numHashFunctions生成的法则为： 可
知，当bitSize在缓慢变大时，numHashFunctions的值是在变小的，直到小于1，但是如果
numHashFunctions的值在接近1或等于1时，计算过滤器bit数组也会越来越小甚至数组长
度为1.这个结果就会导致过滤器的错误率越来越高，失去过滤的意义。改造
numHashFunctions和bitSize生成算法后，使numHashFunctions永远不会接近为1，控制到
最小值接近或等于3，达到使过滤器的错误率不会降低。

[0111] (2)通过采用把p与n两个参数变为动态，改造计算过滤器bit数组，包括初始化过滤器、计算过滤器bit数组、更新/存储过滤器。在更新/存储过滤器时创建一个新的key：
countValue，用来存储统计过滤器存放过的value的数量，通过countValue可以知道已经存
放的value总量，按照n等于2亿数据量来切分n，把n等分或按照比例分为100份，相当于划分
100个区间，根据countValue大小当countValue每到达一个等份值时则更新p与n两个参数，
使其根据实际数据量增大而改变从而改变numHashFunctions和bitSize。bitSize的大小在
100个区间里的每个区间中它的值是成倍数关系的，这样的倍数关系会改变过滤器bit数组
中每个bit位大小的区间。当每个bit位大小的在100个区间中时相当于把过滤器所有的bit
位划分了100份相对独立的空间存储达到相互干涉非常少。这样就解决了在公司2亿数据量
甚至更多数据量时，p与n两个参数需要设置非常大，极大影响实际使用过滤器的速度与错
误率攀升的难题，改造后可以实现只用处理200万的数据量的速度与错误率，极大的增加了
在使用过滤器的处理时间，与大大降低了实际错误率，达到实现高可用处理高数据量的能
力。

[0112] countValue：记录项目实际过滤或存储的值，初始化为0，根据实际使用数量递增，存放在Redis中保存(改造新增参数)

[0113] n值：表示预订的过滤值个数，初始化为2000000，本项目中以2000000为单位把公司目标值200000000分100个区段，在项目运行过程中单个区段固定不变。但当countValue
值的值等于n时，n值就会被重新初始化，重新初始化的值为：n乘2，也就是以n值为基础倍数
扩增

[0114] p值：表示可接受的数据过滤误判概率，这个值的生成方法跟n值相同，初始化为0.0000001，在项目运行过程中单个区段固定不变。但当countValue值的值等于n时，p值就
会被重新初始化，重新初始化的值为：p除2

[0115] (3)通过采用改造删除过滤器的Counter大小设置，Counter的大小定位问题也是一个两难的问题：考虑到空间利用率的问题，从使用的角度来看，希望Counter越大越好，
Counter越大就能记录越多的信息。但是越大的Counter需要占用更多的资源，而且在很多
时候会造成极大的空间浪费。但是把p与n两个参数变为动态后，Counter的值可以改造成根
据countValue值到达的区间而等比例增大Counter大小，这样在过滤器的每一个阶段可以
拥有自己Counter，可以实现平衡空间利用率与资源占用的矛盾，保证过滤器的使用效率。

[0116] 在本申请的描述中，需要理解的是，术语“上”、“下”、“前”、“后”、“左”、“右”、“竖直”、“水平”、“顶”、“底”、“内”、“外”等指示的方位或位置关系为基于附图所示的方位或位
置关系，仅是为了便于描述本申请和简化描述，而不是指示或暗示所指的装置或元件必须
具有特定的方位、以特定的方位构造和操作，因此不能理解为对本申请的限制。

[0117] 本领域技术人员知道，除了以纯计算机可读程序代码方式实现本发明提供的系统、装置及其各个模块以外，完全可以通过将方法步骤进行逻辑编程来使得本发明提供的
系统、装置及其各个模块以逻辑门、开关、专用集成电路、可编程逻辑控制器以及嵌入式微
控制器等的形式来实现相同程序。所以，本发明提供的系统、装置及其各个模块可以被认为
是一种硬件部件，而对其内包括的用于实现各种程序的模块也可以视为硬件部件内的结
构；也可以将用于实现各种功能的模块视为既可以是实现方法的软件程序又可以是硬件部
件内的结构。

[0118] 以上对本发明的具体实施例进行了描述。需要理解的是，本发明并不局限于上述特定实施方式，本领域技术人员可以在权利要求的范围内做出各种变化或修改，这并不影
响本发明的实质内容。在不冲突的情况下，本申请的实施例和实施例中的特征可以任意相
互组合。