BitMap
将每一个元素映射到一个Byte[]数组, 那么判断每个元素是否存在于一个数据集时, 直接用下标获取标记位进行判断即可
○○ []
●○ [1]
○● [2]
●● [1,2]
布隆过滤器
当我们允许一定的误差, 比如让 1,3 可以都映射到Byte[]数组中的同一个位置,
那么
○○ []
●○ 可能是 [1] 或者 [3] 或者 [1,3]
○● [2]
●● 可能是 [1,2] 或者 [2,3] 或者 [1,2,3]
这样的话, 在增加了存储的元素种类的清空下, 我们可以百分百确定一个元素不在一数据集里, 但是无法确定某个元素一定在此元素集里
这种不同元素可能同一个位置的映射, 其实就是一种 散列 函数(Hash Function), 映射到同一个位置的情况就叫做 碰撞
现在我们是用1个Byte来代表一个元素, 其实就是相当与在一个画板上用一个点来代表, 那么如果我们用头像, 也就是用多个点来代表一个元素, 那么画板上能代表的元素就会多很多
布隆过滤器的实现就是用多个哈希函数, 将一个元素映射到Byte[]数组中, 所以在将一个已有数据集映射成一个布隆过滤器时, 由于可能存在碰撞, 导致多个不同元素映射出来的是同一个形状, 所以给定一个元素, 只能判断出它 不属于 已有数据集, 或者是 可能 属于已有数据集
○○○○○ ○○●○○ ○○●○○ ○○●○○
○●●●○ + ○○●○○ + ○●●○○ => ○●●●○
○○○○○ ○○●○○ ○○○○○ ○○●○○
1 + 2 + 3 => [1,2,3]
所以布隆过滤器, 就是用已有数据集编织成的一个网, 可以过滤出大部分不在已知数据集里的元素, 但是剩下每个元素, 我们只能认为它是大概率属于已知元素(因为布隆过滤器其实就像是将所有已知元素的形状重叠生成一个大的形状, 只要某个元素不在该数据集里, 那么就无法与这个大形状重合, 但是就算重合, 不代表一定是属于这个数据集的)