布隆过滤器(Bloom Filter) Kotlin实现

布隆过滤器

适用范围

可以用来实现数据字典,进行数据的判重,或者集合求交集

原理

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。

原理:位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。

更详细的布隆过滤器原理,可以看这篇文章:Bloom Filter(布隆过滤器)的概念和原理

Kotlin实现

需要根据传入的哈希seed构造哈希函数(lambda),然后开一个maxSize的BitSet位数组。然后实现add和contains操作即可。

下面是kotlin实现的代码,只有10行,爽 = =

用法和测试

1 条评论

发表评论

电子邮件地址不会被公开。