快速定位元素在哪个集合中：Bloom Filter

平时会接触到数据库的拆分，文件的拆分等等
拆分后，如何快速定位信息，找到包含某信息的分段

比如要查找 id=xxx 的记录，怎么知道它在哪个表里
1. 最简单的方法是在每一个表中找一遍
2. 最有效的方法是，按 id 特征分配到特定表里。比如分10个表，其中table[i]中存的都是 id % 10 == i 的元素，这时当一个 id 到来时，只要到 table[id % 10] 中找即可。
以上两种方法都能解决一开始提出的需求。但是，方法一显然效率低下；方法二灵活性差，如果查找 name=xxx 的记录，又不知道在哪个表里了。

Bloom Filter 建立的索引，消耗极少的存储空间，花费O(1)的时间复杂，就能判断某个元素是否在集合中。
“我们总能找到一个时间换空间或空间换时间的方法解决问题”
Bloom Filter 能把时间空间都缩小?
它牺牲的是“判断的准确率”

Bloom Filter 可能把不包含的元素误判为包含，但不会把包含的元素误判为不包含。
因此它非常适合做分库、分文件后的路由查找。当出现误判时，就是进入集合中执行一番无效的查找

记元素总量是 n 个，Bloom Filter 占用空间 m bit
错误率是 (xxx)^(n/m) 具体忘了，反正 m = 10n 时，只有0.8xx%

Bloom Filter 资料也挺多的，原理不难，实现也容易