下面的是网络上找到的python的布隆过滤器的实现.

#coding=gbk

'''

Created on 2012-11-7

@author: palydawn

'''

import cmath

from BitVector import BitVector

class BloomFilter(object):

    def __init__(self, error_rate, elementNum):

        #计算所需要的bit数

        self.bit_num = -1 * elementNum * cmath.log(error_rate) / (cmath.log(2.0) * cmath.log(2.0))

        #四字节对齐

        self.bit_num = self.align_4byte(self.bit_num.real)

        #分配内存

        self.bit_array = BitVector(size=self.bit_num)

        #计算hash函数个数

        self.hash_num = cmath.log(2) * self.bit_num / elementNum

        self.hash_num = self.hash_num.real

        #向上取整

        self.hash_num = int(self.hash_num) + 1

        #产生hash函数种子

        self.hash_seeds = self.generate_hashseeds(self.hash_num)

    def insert_element(self, element):

        for seed in self.hash_seeds:

            hash_val = self.hash_element(element, seed)

            #取绝对值

            hash_val = abs(hash_val)

            #取模，防越界

            hash_val = hash_val % self.bit_num

            #设置相应的比特位

            self.bit_array[hash_val] = 1

    #检查元素是否存在，存在返回true，否则返回false 

    def is_element_exist(self, element):

        for seed in self.hash_seeds:

            hash_val = self.hash_element(element, seed)

            #取绝对值

            hash_val = abs(hash_val)

            #取模，防越界

            hash_val = hash_val % self.bit_num

            #查看值

            if self.bit_array[hash_val] == 0:

                return False

        return True

    #内存对齐    

    def align_4byte(self, bit_num):

        num = int(bit_num / 32)

        num = 32 * (num + 1)

        return num

    #产生hash函数种子,hash_num个素数

    def generate_hashseeds(self, hash_num):

        count = 0

        #连续两个种子的最小差值

        gap = 50

        #初始化hash种子为0

        hash_seeds = []

        for index in xrange(hash_num):

            hash_seeds.append(0)

        for index in xrange(10, 10000):

            max_num = int(cmath.sqrt(1.0 * index).real)

            flag = 1

            for num in xrange(2, max_num):

                if index % num == 0:

                    flag = 0

                    break

            if flag == 1:

                #连续两个hash种子的差值要大才行

                if count > 0 and (index - hash_seeds[count - 1]) < gap:

                    continue

                hash_seeds[count] = index

                count = count + 1

            if count == hash_num:

                break

        return hash_seeds

    def hash_element(self, element, seed):

        hash_val = 1

        for ch in str(element):

            chval = ord(ch)

            hash_val = hash_val * seed + chval

        return hash_val

'''

#测试代码

bf = BloomFilter(0.001, 1000000)

element = 'palydawn'

bf.insert_element(element)

print bf.is_element_exist('palydawn')'''

#其中使用了BitVector库，python本身的二进制操作看起来很麻烦，这个就简单多了

如果解决了您的问题请采纳！

如果未解决请继续追问

如果使用哈希表，内存空间需要100亿*64字节=640G(10亿字节（byte）是1G)，空间就爆掉了。此时就轮到布隆过滤器登场了。

布隆过滤器应用场景：黑名单 爬虫去重

布隆过滤器优势：节省内存(30G以内)，查询速度快

布隆过滤器劣势：存在一定失误率

但布隆过滤器的失误率是可以容忍的，一是可以通过设计人为的把失误率控制的很低；二是就算失误了不会误报已经在黑名单里的URL。布隆过滤器只会把正常的URL当成黑名单系统里的，但不会误报已经在黑名单里的URL。形象点说就是“宁可错杀三千不会放过一个”

在讲解布隆过滤器原理之前先讲位图。

位图是bit类型的数组。 int类型4字节即32bit，所以长度100的int类型数组可以看出长度3200的bit数组。假如要找1782位比特，那么在int数组里下标是1782/32，在下标里存的int数字里第几个比特位？即1782%32的计算结果，从而把整型数组操作转换成比特类型数组操作。

布隆过滤器即大位图，假设是长度为m的bit数组，那么占用m/8位字节（Byte）,

URL加黑名单过程：开始时m位比特都是0（白）的状态，该URL通过哈希函数f1得到一个哈希值，然后%m,得到0~m-1上某个位置，将该位置描黑（变成1），再用哈希函数f2得到一个哈希值，再描黑，再用哈希函数f3同样处理（f1、f2、f3是独立的哈希函数），假设一共用了k个哈希函数，那么描黑了k个位置（某个位置重复了就重复了，但一旦描黑就没有描白的时候）完成后可以说该URL加入了位图里。对下一个URL同样处理，用k个哈希函数描黑k个位置……一直做100亿个，位图中有相当多位置被描黑了。

如何查某个URL在不在黑名单里？把待查的URL用K个哈希函数算出对应的哈希值，再把该哈希值%m，把K个位置的状态都拿出来，如果全黑，就说这个URL属于黑名单系统，如果有一个是白，就不属于黑名单系统。如果m很小，100亿个URL之后所有位图都是黑的，那么不论查谁都在黑名单里；如果m取的大一些，失误率就会降低。

但布隆过滤器需要准备多少个bit位和单样本的大小无关。一个URL经过K个哈希函数得到K个哈希值，对m取模后去相应的大比特map中描黑，只要保证哈希函数能接收单样本这种类型的参数就可以了，与样本是64字节还是128字节无关。所以影响失误率的重要参数就是样本量N和位图比特数组长度m。

布隆过滤器三公式： 出处

1.确定m:对于输入的数据量n（这里是100亿）和失误率p（这里是万分之一），布隆过滤器的大小m：m = - (n lnp) / (ln2 ln2)

2.确定K：K假如很少，例如只有一个哈希函数，相当于每个数据只采集了一个特征点，只把一个位置描黑，查的时候也只用一个哈希函数，特征点不够，失误率虽然不至于很高但有一定的量，如果K很大，例如用10万个哈希函数去把10万个位置描黑，m的空间会接近耗尽，查什么URL都是黑的，失误率非常高。需要的哈希函数的个数k：k = ln2 * m/n = 0.7 * m/n

3.因为前两步中公式1公式2都会进行向上取整，所以公式3算出的实际的失误率与比预期失误率要低

布隆过滤器在Hadoop中的应用：Hadoop中的分布式文件系统，是由许多小文件组成的，如何查询一个数据在哪个文件里？首先不可能记录每个小文件的索引，这样做占用空间太大了。所以每个小文件里都搞一个布隆过滤器，当Hadoop想知道某个key在哪个文件里，就查每一个布隆过滤器，文件a的布隆过滤器会说明你这个key在我这个文件里，但可能会有误报；文件c的布隆过滤器会说明你这个key在我这个文件里，但可能会有误报……如果失误率很低，哪怕有几万个分布式文件，最终可能算出来只有3个文件里可能含有这个key。那么就只用把这3个小文件遍历一遍，就知道key在哪个小文件里了。通俗点讲，如果一个文件真的含有key，那么它的布隆过滤器会说这个key属于我；但因为有失误率，可能会发生一个文件不含有这个key，它还是会说这个key属于我；可是这也没关系，多查一遍就可以，反正失误率很低，需要遍历的文件很少。