海量数据处理之BloomFilter

一提到元素查找,我们会很自然的想到HashMap。通过将哈希函数作用于key上,我们得到了哈希值,基于哈希值我们可以去表里的相应位置获取对应的数据。除了存在哈希冲突问题之外,HashMap一个很大的问题就是空间效率低。引入Bloom Filter则可以很好的解决空间效率的问题。

原理

Bloom Filter是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对bit-map 的扩展,布隆过滤器被设计为一个具有N的元素的位数组A(bit array),初始时所有的位都置为0。

当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了。

如果这些点有任何一个 0,则被检索元素一定不在;

如果都是 1,则被检索元素很可能在。

添加元素

要添加一个元素,我们需要提供k个哈希函数。每个函数都能返回一个值,这个值必须能够作为位数组的索引(可以通过对数组长度进行取模得到)。然后,我们把位数组在这个索引处的值设为1。例如,第一个哈希函数作用于元素I上,返回x。类似的,第二个第三个哈希函数返回y与z,那么:

A[x]=A[y]=A[z] = 1

查找元素

查找的过程与上面的过程类似,元素将会被不同的哈希函数处理三次,每个哈希函数都返回一个作为位数组索引值的整数,然后我们检测位数组在x、y与z处的值是否为1。如果有一处不为1,那么就说明这个元素没有被添加到这个布隆过滤器中。如果都为1,就说明这个元素在布隆过滤器里面。当然,会有一定误判的概率。

算法优化

通过上面的解释我们可以知道,如果想设计出一个好的布隆过滤器,我们必须遵循以下准则:

  • 好的哈希函数能够尽可能的返回宽范围的哈希值。
  • 位数组的大小(用m表示)非常重要:如果太小,那么所有的位很快就都会被赋值为1,这样就增加了误判的几率。
  • 哈希函数的个数(用k表示)对索引值的均匀分配也很重要。

计算m的公式如下:

m = - nlog p / (log2)^2

这里p为可接受的误判率。

计算k的公式如下:

k = m/n log(2)

这里k=哈希函数个数,m=位数组个数,n=待检测元素的个数(后面会用到这几个字母)。

哈希算法

哈希算法是影响布隆过滤器性能的地方。我们需要选择一个效率高但不耗时的哈希函数,在论文《更少的哈希函数,相同的性能指标:构造一个更好的布隆过滤器》中,讨论了如何选用2个哈希函数来模拟k个哈希函数。首先,我们需要计算两个哈希函数h1(x)与h2(x)。然后,我们可以用这两个哈希函数来模仿产生k个哈希函数的效果:

gi(x) = h1(x) + ih2(x)

这里i的取值范围是1到k的整数。

Google Guava类库使用这个技巧实现了一个布隆过滤器,哈希算法的主要逻辑如下:

long hash64 = ...;
int hash1 = (int) hash64;
int hash2 = (int) (hash64 >>> 32);

for (int i = 1; i <= numHashFunctions; i++) {
  int combinedHash = hash1 + (i * hash2);
  // Flip all the bits if it's negative (guaranteed positive number)
  if (combinedHash < 0) {
    combinedHash = ~combinedHash;
  }
}

Guava中的Bloom Filter使用示例:

int expectedInsertions = ...; //待检测元素的个数
double fpp = 0.03; //误判率(desired false positive probability)
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), expectedInsertions,fpp);

优点

它的优点是空间效率和查询时间都远远超过一般的算法,布隆过滤器存储空间和插入/查询时间都是常数O(k)。另外, 散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点

布隆过滤器的缺点和优点一样明显,误算率是其中之一。

另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1,这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面,而这一点单凭这个过滤器是无法保证的。

其实,用java实现bloomfilter也是很简单的,主要思想是在java的BitSet的基础上扩展一下hash函数即可。代码如下:

package bigdata.spark.distinct;

import java.util.BitSet;

public class BloomFilter {
    /* BitSet初始分配2^25个bit */
    private static final int DEFAULT_SIZE = 1 << 25;
    /* 不同哈希函数的种子,一般应取质数 */
    private static final int[] seeds = new int[]{5, 7, 11, 13, 31, 37, 61};
    /* 存储海量数据使用bitset */
    private BitSet bits = new BitSet(DEFAULT_SIZE);
    /* 哈希函数对象用于判断元素是否存在于表中 */
    private SimpleHash[] func = new SimpleHash[seeds.length];

    //构造函数
    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    // 将字符串标记到bits中
    public void add(String value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    //判断字符串是否已经被bits标记
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }



    /* 哈希函数类 */
    public static class SimpleHash

    {
        //cap为hash函数的容量
        private int cap;
        //不同hash函数的种子
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        //hash函数,采用简单的加权和hash
        public int hash(String value) {
            int result = 0;
            /* 对Value的每个字符进行hash 获取每个Hash值 */
            int len = value.length();

            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }
            return (cap - 1) & result;
        }
    }
}

整理自网络:

https://blog.csdn.net/foreverling/article/details/79242968

https://blog.csdn.net/it_dx/article/details/71640504

原文发布于微信公众号 - Spark学习技巧(bigdatatip)

原文发表时间:2018-11-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习和数学

[编程经验]Python中的Lambda,Map, Reduce小结

今天要和大家分享的是Python匿名函数(anonymous functions),也叫lambda函数。匿名函数的意思就是说这个函数没有显式的函数名,因为一般...

33850
来自专栏赵俊的Java专栏

计算最大值

15430
来自专栏五分钟学算法

五分钟弄懂有点难度的排序:堆排序

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

16040
来自专栏赵俊的Java专栏

搜索插入位置

18210
来自专栏chenjx85的技术专栏

leetcode-58-Length of Last Word

22060
来自专栏猿人谷

C++ STL算法系列1---count函数

一.count函数 algorithm头文件定义了一个count的函数,其功能类似于find。这个函数使用一对迭代器和一个值做参数,返回这个值出现次数的统计结果...

26760
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

12320
来自专栏个人分享

替换空格

请实现一个函数,将一个字符串中的空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

10110
来自专栏赵俊的Java专栏

LeetCode 557 Reverse Words in a String III

首先按照空格对字符串进行分隔,然后将每个单词进行翻转后再拼接回字符串即可,需要注意拼接时记得加空格,但最后一个单词不需要加。

10410
来自专栏青青天空树

说反话(c++实现)

输入:测试输入包含一个测试用例,在一行内给出总长度不超过80的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词之间...

8720

扫码关注云+社区

领取腾讯云代金券