布隆过滤器经常用于判断一个数据是否存在的手段。由于在查询时间和空间使用率上有着优势被广泛使用。这里记录一下布隆过滤器的原理。
布隆过滤器用一个bit的vector来存贮结果，并使用多个hash函数。在插入的时候会将相关的数据hash计算出来并将对应的位设置为1。如果需要检测某一个项是否存在，需要计算每一个hash函数，并查看对应bit的值是否已经为1。如果有一个hash函数的对应的bit不为1则相关数据一定不存在。如果每个都为1则可能存在（存在false positive 问题）
False positive 问题。
由于布隆过滤器是将相应位置为1，存在检验的值可能是由多个数据拼凑而成。举一个例子，假设现在布隆过滤器有5个bit（实际要大得多）。在插入data1的时候两个hash函数分别将1，4置为1，插入数据data2的时候两个hash函数分别将2，3置为1。现在我试图检验data3是否存在，而data3算出来的hash分别是1，3。虽然对应位已经是1了，但是实际是没有这个数据的。
布隆过滤器缺点
1. 扩容比较困难
2.删除比较困难
布隆过滤器
