首页 > 编程知识 正文

布隆过滤器和bitmap,布隆过滤器删除

时间:2023-05-03 17:41:07 阅读:154695 作者:660

识别fndmz函数Hash,并且通常被翻译为“散列”,但是也可以直接翻译为“fndmz”。 即任意长度的输入端通过哈希算法转换成固定长度的输出端,该输出端是哈希值。

这个变换是压缩映射。 这意味着哈希值的空间通常远远小于输入的空间,不同的输入可能会散列到同一个输出,因此无法根据哈希值确定唯一的输入值。

简单来说,这是一个将任意长度的消息压缩为一定长度的消息摘要的函数。

黑名单系统布隆过滤器应用场景:需要存储大量黑名单,需要快速识别是否包含在黑名单中。 布隆过滤器可快速识别,同时大幅减少存储空间。

利用位图的原理与操作系统的可用内存块非常相似。 您可以使用fndmz函数将黑名单中的个体转换为fndmz值,然后根据该fndmz值将该值转换为位图最后存储的位置。 如果该位为1,则表示不在黑名单上,如果为0,则表示不在黑名单上。

这样,可以将存储单个数据的nbit转换为1bit。 此外,相关存储还允许您快速搜索是否被列入黑名单

解决冲突-提取特征fndmz函数会导致很大的误差率,即许多数据被投影到同一位置,而禁止投影该位置的所有数据。 解决方法是增加数据的特征点。 如果使用k个独立的fndmz函数,则从一个数据中可以得到k个概率不同的fndmz值。 将这些位置都设定为1,遇到新数据时,fndmz函数计算其k个fndmz值,如果对应的位置不全部为1,则禁止该数据

布隆过滤器限制无法删除数据。 因为涂黑(0)可能与很多数据有关。 布隆过滤器一定有误差。 根据数据量n和可容许的误差率p确定fndmz函数k个,使得存储空间m可以根据数学原理选择最佳的存储空间

p随m的增加而减少,利用接受的p可以计算出m能满足多少。

m=nLNP(ln2 ) 2m=-(FRAC(n*LNP ) ) ln2 ) m=) LN2 )2nlnp

m确定后,p先随着k的增加而增加。 (k的增加,表示可以掌握更多的数据细节,更好地识别黑名单) )但是,之后随着k的增加,p会减少。 因为干净的空间会迅速被涂成黑色,所以最后会被识别为黑名单。 可以通过以下公式确认最佳。

k=0.7 nmk=0.7 *frac { n } { m } k=0.7 Mn

也可以根据实际的k、m、n计算出p

(1enkm ) k ) k (1-e^{-frac{nk}{m}} ) k )1emnk ) k

如何得到k个fndmz函数? 13个fndmz函数?

找两个独立的fndmz函数就可以了

f(g ) (f ) ) 1g ) ) 2g ) .f ) ) g ) )1) g ) ) f ) )2) g ) )2) g ) ) ) f ) ) .

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。