布隆过滤器

标签：函数元素布隆 filter 哈希过滤器

介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的

它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中

优点：

可以高效地进行查询，可以用来告诉你“某样东西一定不存在或者可能存在”
可以高效的进行插入
相比于传统的List、Set、Map等数据结构，它占用空间更少，因为其本身并不存储任何数据（重点）

缺点：

其返回的结果是概率性（存在误差）的
一般不提供删除操作
布隆过滤器一般使用在数据量特别大的场景下，一般不会使用

用的使用场景：

使用word文档时，判断某个单词是否拼写正确。例如我们在编写word时，某个单词错误那么就会在单词下显示红色波浪线
网络爬虫程序，不去爬相同的url页面
垃圾邮件的过滤算法
缓存崩溃后造成的缓存击穿
集合重复元素的判别
查询加速（比如基于key-value的存储系统，如redis等）

原理

布隆过滤器是一个bit向量或者说是一个bit数组（下面的数字为索引）：

在这里插入图片描述

为什么布隆过滤器要使用多个Hash函数？

Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为\(m\)个点，那么如果我们想将冲突率降低到例如 \(1%\)，这个散列表就只能容纳 \(m/100\)个元素
解决方法较简单，使用\(K>1\)的布隆过滤器，即\(K\)个函数将每个元素改为对应于\(K\)个bits，因为误判度会降低很多，并且如果参数\(K\)和\(m\)选取得好，一半的\(m\)可被置为1

假设我们的布隆过滤器有三个哈希函数，分别名为hash1、hash2、hash3，主要流程如下：

1、初始化

针对于“baidu”这个元素，我们调用三个哈希函数，将其映射到bit向量的三个位置（分别为1、4、7），并且将对应的位置置为1

2、插入

现在针对于“tencent”这个元素，我们也调用三个哈希函数，将其映射到bit向量的三个位置（分别为3、4、8），并且将对应的位置置为1

此时，整个bit向量的1、3、4、7、8这几个位置被置为1了。其中4这个索引被覆盖了，因为“baidu”和“tencent”都将其置为1，覆盖的索引与误判率有关。

3、查找

去查询一个不存在的元素，并且确定其肯定不存在：例如现在我们去查询“dongshao”这个元素，假设调用上面的三个哈希函数返回的索引是1、5、8，通过上图我们知道5这个索引处为0，因此“dongshao”这个元素一定不存在，因为如果存在的话，那么5这个位置应该被置为1才对。
去查询“baidu”这个元素，不能判断其百分百存在：我们将“baidu”传入上面的三个哈希函数中，哈希返回的对应索引值为1、4、7，发现1、4、7这几个索引处都为1，因此我们判断“baidu”这个元素可能存在。

误判率（假阳率）

布隆过滤器允许存在一定的误判断，误判率也称为“假阳”。
误判率一般是出现在查询的时候

例如上面我们去查询“baidu”的时候，由于“baidu”之前被我们插入过，为什么还不能百分百确定它一定存在呢？

因为“tencent”这个元素在插入的时候，将4这个索引置为1了。
假设我们查询“baidu”的时候实际返回的是1、7索引为1，4索引为0。而4索引又被tencent覆盖为1，所以最终“baidu”最终看到的是1、4、7索引都为1，不能百分百确定“baidu”这个元素存在。

因此，当随着增加的值越来越多时，bit向量被置为1的数量也就会越来越多，因此误判率会越来越大。例如，当查询“taobao”时，万一所有的哈希函数返回的对应bit都为1，那么布隆过滤器可能也认为“taobao”这个元素存在。

那如何控制误判率？

哈希函数越多、插入元素越少，误判率越低
满足\(m=\frac{w k}{\ln ^2 2}\)条件，则误判率最低！

\(k\)：哈希函数个数；\(w\)：带插入元素个数；\(m\)：BF数组的长度。

在线验证：https://hur.st/bloomfilter/

\(n\)：布隆过滤器最大处理的元素的个数；\(P\)：希望的误差率；\(m\)：布隆过滤器的bit位数目；\(k\)：哈希函数的个数

代码实现

1、python简单实现

这里的哈希函数是简单定义的

import math
import random
import time

def hash_function(a, b, c, item, tablelen):
    return (a * item ** 2 + b * item + c) % tablelen  #哈希函数

def construction_of_SBF(tablelen = 1000, set = []):

    k = int(math.log(2, math.e) * (tablelen / len(set))) #哈希函数的个数
    print("k=",k)
    hash = []
    random.seed(time.time())
    for i in range(k):  #随机生成哈希函数的三个参数
        a = random.randint(1, 1000)
        b = random.randint(1, 1000)
        c = random.randint(1, 1000)
        hash.append((a, b, c))

    bitArray = [0] * tablelen   #BF数组

    for element in set:     #映射集合元素到位数组
        for i in range(k):
            hx = hash_function(hash[i][0], hash[i][1], hash[i][2], element, tablelen)
            bitArray[hx] = 1

    print("BF=",bitArray)
    filter = [bitArray, hash]
    return filter

# 测试
def test_bloom_filters(bloom_filter = None):
    if bloom_filter == None:
        return False

    testSet = [1, 3, 7, 11, 9, 5, 4, 67, 81]
    for item in testSet:
        flag = True
        for i in range(len(filter[1])):
            hx = hash_function(filter[1][i][0], filter[1][i][1], filter[1][i][2], item, len(filter[0]))
            if bloom_filter[0][hx] != 1:
                flag = False
                break

        if flag is True:
            print("%d is in filter\n" % item)
        else:
            print("%d is not in filter\n" % item)

    return True


if __name__ == "__main__":
    filter = construction_of_SBF(set = list(range(10)))
    test_bloom_filters(filter)

2、C++实现

这里哈希函数使用的是MurmurHash2算法，输出64位哈希值

#include "bloomfilter.h"
 
#define MAX_ITEMS 6000000      // 设置最大元素个数，BF容量
#define ADD_ITEMS 1000      // 添加测试元素
#define P_ERROR 0.0001// 设置误差
 
//
int main(int argc, char** argv)
{
 
    printf(" test bloomfilter\n");
 
    // 1. 定义BaseBloomFilter
    static BaseBloomFilter stBloomFilter = {0};
 
    // 2. 初始化stBloomFilter，调用时传入hash种子，存储容量，以及允许的误判率
    InitBloomFilter(&stBloomFilter, 0, MAX_ITEMS, P_ERROR);
 
    // 3. 向BloomFilter中新增数值
    char url[128] = {0};
    for(int i = 0; i < ADD_ITEMS; i++){
        sprintf(url, "https://blog.csdn.net/qq_41453285/%d.html", i);
        if(0 == BloomFilter_Add(&stBloomFilter, (const void*)url, strlen(url))){
            printf("add %s success\n", url);
        }else{
            printf("add %s failed\n", url);
        }
        memset(url, 0, sizeof(url));
    }
 
    // 4. check url exist or not
    char* str = "https://blog.csdn.net/qq_41453285/0.html";
    if (0 == BloomFilter_Check(&stBloomFilter, (const void*)str, strlen(str)) ){
        printf("https://blog.csdn.net/qq_41453285/0.html exist\n");
    }
 
    char* str2 = "https://blog.csdn.net/qq_41453285/10001.html";
    if (0 != BloomFilter_Check(&stBloomFilter, (const void*)str2, strlen(str2)) ){
          printf("https://blog.csdn.net/qq_41453285/10001.html not exist\n");
    }
 
    // 5. free bloomfilter
    FreeBloomFilter(&stBloomFilter);
    return 0;
}

参考

1、https://blog.csdn.net/qq_40989769/article/details/126781815

2、https://www.cnblogs.com/ciel717/p/16179892.html

标签：函数,元素,布隆,filter,哈希,过滤器
From： https://www.cnblogs.com/pam-sh/p/16948920.html

布隆过滤器