应用介绍

此项目是Java笔试和面试及知识整理资料。

 Bloom filter

### 适用范围

实现数据字典，进行数据的判重，或者集合求交集

### 基本原理

　　对于原理来说很简单，**Bit-Map + K个独立 Hash 函数**。将 Hash 函数对应的值的位数组置`1`，**查找时如果发现所有 Hash 函数对应位都是`1`说明存在**。很明显这个过程并不保证查找的结果是 100% 正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 **Counting Bloom filter**，用一个 Counter 数组代替位数组，就可以支持删除了。


对于元素个数：{{<katex>}}n{{</katex>}}，错误率（假阳率）：{{<katex>}}P{{</katex>}}。我们可以计算：

  - Bit-Map 大小：{{<katex>}}m\ge -\frac{n\times ln^P}{(ln^2)^2}{{</katex>}}

  - Hash 函数个数：{{<katex>}}k=log_2^\frac{1}{P}{{</katex>}}

> 参数在线计算工具：[Bloom Filter Calculator](https://hur.st/bloomfilter)

举个例子我们假设 {{<katex>}}P=0.01{{</katex>}}，{{<katex>}}n=4000{{</katex>}}，则此时 m 应大概是 {{<katex>}}9.5\times n=38000{{</katex>}} bit，{{<katex>}}k=7{{</katex>}}

注意这里 m 与 n 的单位不同，m是 `bit` 为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多 `bit` 的。所以使用bloom filter内存上通常都是节省的。

### 扩展

　　Bloom filter 将集合中的元素映射到位数组中，用 k 个映射位是否全1表示元素在不在这个集合中。`Counting bloom filter（CBF）`将 **位数组中的每一位扩展为一个 Counter**，从而支持了元素的删除操作。`Spectral Bloom Filter（SBF）`将其与集合元素的出现次数关联。**`SBF`采用 Counter 中的最小值来近似表示元素的出现频率**。

### 问题实例

给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。如果是三个乃至n个文件呢？

答：根据这个问题我们来计算下内存的占用，`4G=2^32`大概是40亿*8大概是 340亿，n=50亿，如果按出错率 0.01 算需要的大概是 475 亿个bit。现在可用的是 340 亿，相差并不多，这样可能会使出错率上升些。另外如果这些url ip是一一对应的，就可以转换成ip，则大大简单了。

---

## Hashing

### 适用范围

快速查找，删除的基本数据结构，通常需要总数据量可以放入内存

。。。。。 想了解更多请下载附件。