# python布隆过滤器

BloomFilter的应用

> * 黑名单
>
>   > 比如邮件黑名单过滤器，判断邮件地址是否在黑名单中
> * 排序(仅限于BitSet)
>
>   > 仔细想想，其实BitSet在set(int value)的时候，“顺便”把value也给排序了。
> * 网络爬虫
>
>   > 判断某个URL是否已经被爬取过
> * K-V系统快速判断某个key是否存在
>
>   > 典型的例子有Hbase，Hbase的每个Region中都包含一个BloomFilter，用于在查询时快速判断某个key在该region中是否存在，如果不存在，直接返回，节省掉后续的查询。

实习经历过的例子：如何判断右边👉1000万条数据id中，有多少条在左边👈50万条数据中。当然，反过来也一样

显然可能会想到用set数据结构，或者bitset

参考了：<https://blog.csdn.net/xinzhongtianxia/article/details/81294922>

总之之前的想法都躺枪试过，不尽完美。

BloomFiler又叫布隆过滤器，下面举例说明BlooFilter的实现原理：

> 比如你有10个Url，你完全可以创建一长度是100bit的数组，然后对url分别用5个不同的hash函数进行hash，得到5个hash后的值，这5个值尽可能的保证均匀分布在100个bit的范围内。然后把5个hash值对应的bit位都置为1，判断一个url是否已经存在时，一次看5个bit位是否为1就可以了，如果有任何一个不为1，那么说明这个url不存在。这里需要注意的是，如果对应的bit位值都为1，那么也不能肯定这个url一定存在，这个是BloomFilter的特点之一

![](/files/-LqkEsFk1KaWEeWOVAPg)

BloomFilter的核心思想有两点：

1. 多个hash，增大随机性，减少hash碰撞的概率
2. 扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率。

## 安装使用

`pip install pybloom`

### BloomFilter:定容

```python
from pybloom import BloomFilter

# capacity是容量, error_rate 是能容忍的误报率
f = BloomFilter(capacity=1000, error_rate=0.001)

# 返回False，一定不存在/返回True，则有可能存在
state=f.add('你好')
```

### ScalableBloomFilter:自动扩容

```python
from pybloom import ScalableBloomFilter

#SMALL_SET_GROWTH，扩容规则
sbf = ScalableBloomFilter(mode=ScalableBloomFilter.SMALL_SET_GROWTH)
sbf.add() #与BloomFilter 同
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://im-qianuxn.gitbook.io/pytorch/ji-suan-ji/python/bloomfilter.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.