布隆过滤器(Bloom Filter)的原理和实现-阿里云开发者社区

开发者社区> 技术小甜> 正文

布隆过滤器(Bloom Filter)的原理和实现

简介:
+关注继续查看

什么情况下需要布隆过滤器?

先来看几个比较常见的例子

  • 字处理软件中,需要检查一个英语单词是否拼写正确

  • 在 FBI,一个嫌疑人的名字是否已经在嫌疑名单上

  • 在网络爬虫里,一个网址是否被访问过

  • yahoo, gmail等邮箱垃圾邮件过滤功能

这几个例子有一个共同的特点: 如何判断一个元素是否存在一个集合中?

常规思路

  • 数组

  • 链表

  • 树、平衡二叉树、Trie

  • Map (红黑树)

  • 哈希表

虽然上面描述的这几种数据结构配合常见的排序、二分搜索可以快速高效的处理绝大部分判断元素是否存在集合中的需求。但是当集合里面的元素数量足够大,如果有500万条记录甚至1亿条记录呢?这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容,一旦数据量过大,消耗的内存也会呈现线性增长,最终达到瓶颈。有的同学可能会问,哈希表不是效率很高吗?查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很高。使用哈希表存储一亿 个垃圾 email 地址的消耗?哈希表的做法:首先,哈希函数将一个email地址映射成8字节信息指纹;考虑到哈希表存储效率通常小于50%(哈希冲突);因此消耗的内存:8 * 2 * 1亿 字节 = 1.6G 内存,普通计算机是无法提供如此大的内存。这个时候,布隆过滤器(Bloom Filter)就应运而生。在继续介绍布隆过滤器的原理时,先讲解下关于哈希函数的预备知识。

哈希函数

哈希函数的概念是:将任意大小的数据转换成特定大小的数据的函数,转换后的数据称为哈希值或哈希编码。下面是一幅示意图:

1030776-20170106142012816-1867044021.png

可以明显的看到,原始数据经过哈希函数的映射后称为了一个个的哈希编码,数据得到压缩。哈希函数是实现哈希表和布隆过滤器的基础。

布隆过滤器介绍

  • 巴顿.布隆于一九七零年提出

  • 一个很长的二进制向量 (位数组)

  • 一系列随机函数 (哈希)

  • 空间效率和查询效率高

  • 有一定的误判率(哈希表是精确匹配)

布隆过滤器原理

布隆过滤器(Bloom Filter)的核心实现是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k

1030776-20170106143141784-1475031003.png

以上图为例,具体的操作流程:假设集合里面有3个元素{x, y, z},哈希函数的个数为3。首先将位数组进行初始化,将里面每个位都设置位0。对于集合里面的每一个元素,将元素依次通过3个哈希函数进行映射,每次映射都会产生一个哈希值,这个值对应位数组上面的一个点,然后将位数组对应的位置标记为1。查询W元素是否存在集合中的时候,同样的方法将W通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1,则可以判断该元素一定不存在集合中。反之,如果3个点都为1,则该元素可能存在集合中。注意:此处不能判断该元素是否一定存在集合中,可能存在一定的误判率。可以从图中可以看到:假设某个元素通过映射对应下标为4,5,6这3个点。虽然这3个点都为1,但是很明显这3个点是不同元素经过哈希得到的位置,因此这种情况说明元素虽然不在集合中,也可能对应的都是1,这是误判率存在的原因。

布隆过滤器添加元素

  • 将要添加的元素给k个哈希函数

  • 得到对应于位数组上的k个位置

  • 将这k个位置设为1

布隆过滤器查询元素

  • 将要查询的元素给k个哈希函数

  • 得到对应于位数组上的k个位置

  • 如果k个位置有一个为0,则肯定不在集合中

  • 如果k个位置全部为1,则可能在集合中

布隆过滤器实现

下面给出python的实现,使用murmurhash算法

import mmh3from bitarray import bitarray# zhihu_crawler.bloom_filter# Implement a simple bloom filter with murmurhash algorithm.# Bloom filter is used to check wether an element exists in a collection, and it has a good performance in big data situation.# It may has positive rate depend on hash functions and elements count.BIT_SIZE = 5000000class BloomFilter:
    
    def __init__(self):
        # Initialize bloom filter, set size and all bits to 0
        bit_array = bitarray(BIT_SIZE)
        bit_array.setall(0)        self.bit_array = bit_array        
    def add(self, url):
        # Add a url, and set points in bitarray to 1 (Points count is equal to hash funcs count.)
        # Here use 7 hash functions.
        point_list = self.get_postions(url)        for b in point_list:            self.bit_array[b] = 1

    def contains(self, url):
        # Check if a url is in a collection
        point_list = self.get_postions(url)

        result = True
        for b in point_list:
            result = result and self.bit_array[b]    
        return result    def get_postions(self, url):
        # Get points positions in bit vector.
        point1 = mmh3.hash(url, 41) % BIT_SIZE
        point2 = mmh3.hash(url, 42) % BIT_SIZE
        point3 = mmh3.hash(url, 43) % BIT_SIZE
        point4 = mmh3.hash(url, 44) % BIT_SIZE
        point5 = mmh3.hash(url, 45) % BIT_SIZE
        point6 = mmh3.hash(url, 46) % BIT_SIZE
        point7 = mmh3.hash(url, 47) % BIT_SIZE        return [point1, point2, point3, point4, point5, point6, point7]















本文转自xsster51CTO博客,原文链接:http://blog.51cto.com/12945177/1932211 ,如需转载请自行联系原作者




版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
10088 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2962 0
StrutsPrepareAndExecuteFilter过滤器和url-pattern设置详解
1.strut 过滤器 FilterDispatcher是struts2.0.x到2.1.2版本的核心过滤器.! StrutsPrepareAndExecuteFilter是自2.1.3开始就替代了FilterDispatcher的.! 这样的改革当然是有好处的.! 为什么这么说.? 应该知道如果我们自己定义过滤器的话, 是要放在strtus2的过滤器之前的, 如果放在struts2过滤器之后
3225 0
FilenameFilter文件名过滤器——列出指定类型文件实现
  Java的IO操作中File有列出指定目录的文件的方法。如果要列出指定类型的文件,需使用FilenameFilter对象。   FilenameFilter是一个接口,所以需要写一个实现类来实现该接口。
782 0
【重新发现PostgreSQL之美】- 14 bloom 布隆过滤器索引
大家好,这里是重新发现PostgreSQL之美 - 14 bloom 布隆过滤器索引
96 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13891 0
+关注
10146
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载