1.基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,包括基于先进先出及最小活跃数策略的集合成员插入方法,所述基于先进先出及最小活跃数策略的集合成员插入方法包括以下步骤:
步骤1、预先建立用于存储集合成员指纹信息的布谷鸟过滤器,并统一划分出存储区和缓存区,其中存储区用于存储重定位标志值为0或1的指纹信息,而缓存区用于存储重定位标志值为2的指纹信息,其中,重定位标志值为0的指纹信息是指该集合成员的指纹信息未发生重定位操作,重定位标志值为1的指纹信息是指该集合成员的指纹信息最近发生过一次重定位操作,重定位标志值为0的指纹信息是指该集合成员的指纹信息最近发生2次重定位操作,同时分别为布谷鸟过滤器中的每一个哈希候选桶中维护一个记录区,每一个哈希候选桶对应的记录区中包括存储区活跃数计数值、存储区异常空白槽位计数、缓存区指纹计数值、交换位地址信息及插入位地址信息,且针对每一个哈希候选桶,其槽位存储单位为由集合成员的指纹信息和重定位标志值两个元素构成的指纹信息标签;
步骤2、插入时,采用集合成员判定方法判断待插入集合成员的指纹信息标签是否存在于对应哈希候选桶中,若不存在则插入操作结束,若存在则选择两个哈希候选桶中存储区活跃计数值最少的那一个哈希候选桶进行插入操作,插入操作时,根据该哈希候选桶的插入位地址信息计算所插入槽位插入,若此时所插入槽位并不为空白槽位,则根据该哈希候选桶的存储区异常空白槽位计数判断该哈希候选桶是否还有空白槽位,若没有则进入重定位操作,否则随机插入空白槽位。
2.如权利要求1所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤1中,所述存储区活跃数计数值记为ACI、存储区异常空白槽位计数记为ERI、缓存区指纹计数值记为HFN、交换位地址信息记为EXC及插入位地址信息记为INS;
所述步骤2包括以下具体步骤:
步骤201、插入时,通过哈希函数计算得到待插入集合成员ξX的指纹信息 以及对应的两个哈希候选桶 ;
步骤202、采用集合成员判定方法判断 对应的指纹信息标签是否存在于两个哈希候选桶 中,如果存在则插入操作结束,否则进入步骤203;
步骤203、通过读取两个哈希候选桶各自的存储区活跃计数值ACI做比较并选择一个活跃计数值最少的哈希候选桶作为插入桶标记为minWB;
步骤204、定义一个中间变量TINS,读取minWB记录区的 值,然后计算;若TINS所指的槽位为空白槽位,则进入步骤205,否则进入步骤206,其中,L0表示对应哈希候选桶minWB的起始地址,m表示存储区最大承载指纹标签数;
步骤205、将指纹信息为 且重定位标志为0的指纹信息标签插入 所指的空白槽位中,在 minWB的记录区中令
及 ,插入操作结束;
步骤206、判断minWB记录区中存储区异常空白槽位计数 的值是否为0,若是则进入重定位操作步骤,否则进入步骤207;
步骤207、将指纹信息为 且重定位标志值为0的指纹信息标签随机插入minWB的异常空白槽位中,并在minWB的记录区中令及 ,插入操作结束。
3.如权利要求2所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤2中,所述通过哈希函数计算得到待插入集合成员ξX的指纹信息 以及对应的两个哈希候选桶 具体为:
其中, 为哈希函数。
4.如权利要求2或3所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤206中,所述重定位操作包括以下步骤:步骤206A、将minWB中待插入指纹信息标签赋值给中间变量Temp,将EXC所指的指纹信息标签赋值给另一中间变量Temp1;
步骤206B、将Temp中的指纹信息标签的重定位标志值置为1,并插入EXC所指的槽位中;
步骤206C、在minWB的记录区中令 ,和 ;
步骤206D、判断Temp1中的指纹信息标签的重定位标志值是否为1,如果为1,则进入步骤206E,否则进入步骤206G;
步骤206E、计算中间变量 ,然后将Temp1中的指纹信息标签的重定位标志值置为2并插入addf所指的空槽位中即minWB的缓存区中;
步骤206F、在minWB的记录区中令及 ,重定位操作结束;
步骤206G、计算Temp1的另一个哈希候选桶并标记为BUTemp1;
步骤206H、读取BUTemp1记录区的的INS值,然后计算;
步骤206I、判断TINS所指的槽位是否为空白槽位,若是则进入步骤206L,否则进入步骤
206J;
步骤206J、读取并判断BUTemp1记录区的ERI值是否为0,若是则将Temp1作为待插入指纹信息标签回到步骤206A,否则进入步骤206K;
步骤206K、将Temp1中的指纹信息标签的重定位标志值置为1,并随机插入BUTemp1的异常空白槽位中,在BUTemp1的记录区中令及 ,重定位操作结束;
步骤206L、将Temp1中的指纹信息标签的重定位标志值置为1,并插入TINS所指的空白槽位中,在BUTemp1的记录区中令及 ,重定位操作结束。
5.基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,包括基于先进先出及最小活跃数策略的集合成员判定方法,所述基于先进先出及最小活跃数策略的集合成员判定方法包括以下步骤:
步骤I、预先建立用于存储集合成员指纹信息的布谷鸟过滤器,并统一划分出存储区和缓存区,其中存储区用于存储重定位标志值为0或1的指纹信息,而缓存区用于存储重定位标志值为2的指纹信息,其中,重定位标志值为0的指纹信息是指该集合成员的指纹信息未发生重定位操作,重定位标志值为1的指纹信息是指该集合成员的指纹信息最近发生过一次重定位操作,重定位标志值为0的指纹信息是指该集合成员的指纹信息最近发生2次重定位操作,同时分别为布谷鸟过滤器中的每一个哈希候选桶中维护一个记录区,每一个哈希候选桶对应的记录区中包括存储区活跃数计数值、存储区异常空白槽位计数、缓存区指纹计数值、交换位地址信息及插入位地址信息,且针对每一个哈希候选桶,其槽位存储单位为由集合成员的指纹信息和重定位标志值两个元素构成的指纹信息标签;
步骤II、判定时,比较两个哈希候选桶的存储区活跃计数值,先遍历查询待判定集合成员的指纹信息标签是否存在于存储区活跃计数值较小的那一个哈希候选桶中,若存在则查询成功,否则再遍历查询待判定集合成员的指纹信息标签是否存在于另一个哈希候选桶中,若存在则查询成功,否则查询失败。
6.如权利要求5所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤I中,所述存储区活跃数计数值记为ACI、存储区异常空白槽位计数记为ERI、缓存区指纹计数值记为HFN、交换位地址信息记为EXC及插入位地址信息记为INS;
所述步骤II包括以下具体步骤:
步骤II.1、判定时,通过哈希函数计算得到待判定集合成员ξY的指纹信息 以及对应的两个哈希候选桶 ;
步骤II.2、通过读取两个哈希候选桶的存储区活跃计数值ACI做比较并选择一个活跃计数值最少的哈希候选桶标记为minWB,另一个哈希候选桶标记为maxWB;
步骤II.3、对minWB进行traverse步骤,遍历查询 所属的指纹信息标签是否在minWB中,若是则查询成功,查询操作结束,否则进入步骤II.4;
步骤II.4、对maxWB进行traverse步骤,遍历查询 所属的指纹信息标签是否在maxWB中,若是则查询成功,查询操作结束,否则查询失败,查询操作结束。
7.如权利要求6所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤II中,所述通过哈希函数计算得到待判定集合成员ξY的指纹信息 以及对应的两个哈希候选桶 具体为:
其中, 为哈希函数。
8.如权利要求5或6所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤II.3及步骤II.4中,所述traverse步骤包括以下具体步骤:步骤III.1、读取被traverse步骤操作的哈希候选桶记录区中的EXC值,并将EXC值赋值给中间变量Temp;
步骤III.2、将待查指纹信息与Temp所指的槽位中存储的指纹信息标签中的指纹信息做匹配,若匹配,则返回查询成功,退出traverse步骤,否则进入步骤III.3;
步骤III.3、读取被traverse步骤操作的哈希候选桶记录区中的INS值,判断Temp与INS值信息是否相同,若是则进入步骤III.4,否则进入步骤III.9;
步骤III.4、读取被traverse步骤操作的哈希候选桶记录区中的HFN值,判断HFN值是否等于0,若是则查询失败,退出traverse步骤,否则进入步骤III.5;
步骤III.5、将HFN值赋值给中间变量Temp1,并计算另一中间变量,其中,L0表示对应被traverse步骤操作的哈希候选桶的起始地址,m表示存储区最大承载指纹标签数;
步骤III.6、将待查指纹信息与Temp2所指的槽位中存储的指纹信息标签中的指纹信息做匹配,若匹配则返回查询成功,退出traverse步骤,否则进入步骤III.7;
步骤III.7、令Temp1=Temp1‑1,判断Temp1是否等于0,若是则查询失败,退出traverse步骤,否则进入步骤III.8;
步骤III.8、令Temp2=Temp2‑1,然后回到步骤III.6;
步骤III.9、令Temp=L0+{m+(Temp‑L0)‑1}mod m,并回到步骤III.2。
9.基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,包括基于先进先出及最小活跃数策略的集合成员删除方法,所述基于先进先出及最小活跃数策略的集合成员删除方法包括以下步骤:
步骤A、预先建立用于存储集合成员指纹信息的布谷鸟过滤器,并统一划分出存储区和缓存区,其中存储区用于存储重定位标志值为0或1的指纹信息,而缓存区用于存储重定位标志值为2的指纹信息,其中,重定位标志值为0的指纹信息是指该集合成员的指纹信息未发生重定位操作,重定位标志值为1的指纹信息是指该集合成员的指纹信息最近发生过一次重定位操作,重定位标志值为0的指纹信息是指该集合成员的指纹信息最近发生2次重定位操作,同时分别为布谷鸟过滤器中的每一个哈希候选桶中维护一个记录区,每一个哈希候选桶对应的记录区中包括存储区活跃数计数值、存储区异常空白槽位计数、缓存区指纹计数值、交换位地址信息及插入位地址信息,且针对每一个哈希候选桶,其槽位存储单位为由集合成员的指纹信息和重定位标志位两个元素构成的指纹信息标签;
步骤B、删除时,采用集合成员判定方法判断待删除集合成员的指纹信息标签是否存在于对应两个哈希候选桶中,若不存在则删除失败,删除操作结束,若存在则删除该指纹信息标签,且根据该哈希候选桶的缓存区计数值判断其缓存区中是否有集合成员,若没有则删除操作完成,若有则将缓存区中存在的第一个集合成员迁移至被删除指纹信息对应的空白槽位,删除操作结束。
10.如权利要求9所述的基于先进先出及最小活跃数策略的集合成员管理方法,其特征在于,步骤A中,所述存储区活跃数计数值记为ACI、存储区异常空白槽位计数记为ERI、缓存区指纹计数值记为HFN、交换位地址信息记为EXC及插入位地址信息记为INS;
所述步骤B包括以下具体步骤:
步骤B1、删除时,通过哈希函数计算得到待删除集合成员ξZ的指纹信息 以及对应的两个哈希候选桶 ;
步骤B2、通过集合成员判定方法判定指纹信息 所属的指纹信息标签是否储存在两个哈希候选桶 的存储区中,若存在则转入步骤B3,否则进入步骤B15;
步骤B3、将存储指纹信息 所属的指纹信息标签的哈希候选桶标记为bucketZ,然后读取bucketZ记录区中的HFN值,判断该HFN值是否等于0,若是则进入步骤B7,否则进入步骤B4;
步骤B4、计算中间变量 ,然后将addfDEL所指槽位中存储的指纹信息标签赋值给另一中间变量Temp2,其中,L0表示对应哈希候选桶bucketZ的起始地址,m表示存储区最大承载指纹标签数;
步骤B5、删除addfDEL所指槽位中存储的指纹信息标签,将Temp2中的指纹信息标签的重定位标志值置为1,并插入覆盖指纹信息 所属的指纹信息标签;
步骤B6、在bucketZ记录区中令ACI=ACI‑1及HFN=HFN‑1,删除成功,删除操作结束;
步骤B7、删除 所属的指纹信息标签;
步骤B8、读取bucketZ记录区中的INS值,判断存储 所属的指纹信息标签的槽位的地址信息是否等于INS,若是则进入步骤B12,否则进入步骤B9;
步骤B9、读取bucketZ记录区中的EXC值,判断存储 所属的指纹信息标签的槽位的地址信息是否等于EXC,若是则进入步骤B10,否则进入步骤B11;
步骤B10、在bucketZ记录区中令ACI=ACI‑1及EXC=L0+{m+(EXC‑L0)‑1}mod m,删除成功,删除操作结束;
步骤B11、在bucketZ记录区中计算ACI=ACI‑1及ERI=ERI+1,删除成功,删除操作结束;
步骤B12、读取bucketZ记录区中的EXC值,判断存储 所属的指纹信息标签的槽位的地址信息是否等于EXC,若是则进入步骤B13,否则进入步骤B14;
步骤B13、在bucketZ记录区中令ACI=ACI‑1、EXC=L0+{m+(EXC‑L0)‑1}mod m及INS=L0+{m+(INS‑L0)+1}mod m,删除成功,删除操作结束;
步骤B14、在bucketZ记录区中令ACI=ACI‑1及INS=L0+{m+(INS‑L0)+1}mod m,删除成功,删除操作结束;
步骤B15、通过集合成员判定方法判定指纹信息 所属的指纹信息标签是否储存在两个哈希候选桶 的缓存区中,若存在则转入步骤B16,否则删除失败,删除操作结束;
步骤B16、将缓存区存储指纹信息 所属的指纹信息标签的哈希候选桶标记为bucketZ,计算中间变量addfDEL=L0+m+HFN‑1,然后将addfDEL所指槽位中存储的指纹信息标签覆盖指纹信息 所属的指纹信息标签,同时删除addfDEL所指槽位中存储的指纹信息标签并置空,其中,L0表示对应哈希候选桶bucketZ的起始地址,HFN为对应哈希候选桶bucketZ的HFN值,m表示存储区最大承载指纹标签数;
步骤B17、在bucketZ记录区中令ACI=ACI‑1及HFN=HFN‑1,删除成功,删除操作结束。