场景思考

我们假设一种场景，有一个集合数据（集中里的数据量可能很多），现在我们需要判断某一个元素在集合中是否存在。

低效的遍历操作

最简单直接的方式就是遍历整个集合，逐个判断我们需要的元素是否在集合里，对于小集合，遍历的方式是可行的，但是对于大集合来说，遍历的方式就显得特别低效。

使用bitmap的方式记录

什么是bitmap

Bitmap数据结构是一个非常紧凑的二进制位数组，每个位代表一个用户或对象的状态。每个位的值可以是0或1，可用于分别表示未设置和已设置的状态。

怎样使用bitmap

如果我们能够为每一个元素都分配一个唯一的整形值，那么我们就能够利用bitmap来判断元素是否存在于集合中。
例如：我们要判断某个用户当前是否正在登录，如果每个用户都有唯一一个标识的整形id，那么我们就可以在bitmap里将这个id代表的位设置为1，以标识用户已登录，后面判断用户是否已登录的话，直接查询这个位的值就行了：

位	0	1	2	3	4	5	6	7	8	9	10	......
值	0	0	0	0	0	0	1	0	0	0	0	......

 

如上图，代表id=6的用户已登录，其他id的用户都未登录。

bitmap的优点

• 节省存储空间：

       Bitmap使用位数组来表示数据，每个位只占用1比特，可以有效地节省存储空间。对于大规模的标记或计数需求，使用Bitmap可以大大减少存储需求。

• 高效的位操作：

        Bitmap提供了一系列高效的位操作命令，例如设置位、获取位、位运算等。这些操作可以在常数时间内完成，具有很高的性能。

• 简单明确的语义：

        Bitmap的操作非常直观和简单，易于理解和使用。

bitmap的缺点

• 存储需求随数据规模增加：

        虽然Bitmap可以节省存储空间，但随着数据规模的增加，所需的存储空间也会相应增加。对于非常大的数据集，Bitmap可能需要占用较多的存储空间。

• 不支持无法抽象成唯一整形的数据：

          对于某些数据，如果无法抽象成唯一的数字id，则无法使用bitmap做处理。

其中，存储需求随数据规模增加是bitmap最大的缺点。对于超大规模数据，是无法使用bitmap方式的。

布隆过滤器

接下来，我们思考另一种方法判断元素是否在集合中存在。

现在我们同样用一个数组去做状态记录，但是和bitmap不同的是，这个数组是限长的。

每次有新元素进来时，我们计算新元素的特征值，并把特征值对应的位数标记为1。

当我们需要判断某一元素是否存在时，那么只需要用相同的特征值算法计算该元素的特征值，并逐一判断特征值是否都为1即可。

例如，现在数组的长度是10，依次进来了元素a,b

1. 建立数组长度是10的元素

位	0	1	2	3	4	5	6	7	8	9	10
值	0	0	0	0	0	0	0	0	0	0	0

 

2. 新增元素a，元素a的特征值计算结果是[1,5]

位	0	1	2	3	4	5	6	7	8	9	10
值	0	1	0	0	0	1	0	0	0	0	0

 

3. 新增元素b，元素b的特征值计算结果是[5,6]

位	0	1	2	3	4	5	6	7	8	9	10
值	0	1	0	0	0	1	1	0	0	0	0

4. 判断元素c是否存在，元素c的特征值计算结果是[1,8]

位	0	1	2	3	4	5	6	7	8	9	10
值	0	1	0	0	0	1	1	0	0	0	0

如上图，数组中位8的值是0，所以可以判断元素c肯定不存在

5. 判断元素a是否存在，元素a的特征值计算结果是[1,5]

因为位1和位5的值都是1，所以我们可以认为元素a是存在的，那么，事实上，我们真的能确信元素a存在么？

布隆过滤器是准确的么？

接着上例，假如我们现在有一个新的元素d，它的特征值是[1,6]，那么会发生怎样的结果呢？

位	0	1	2	3	4	5	6	7	8	9	10
值	0	1	0	0	0	1	1	0	0	0	0

 

如上图，因为元素d的特征值的位数都是1，所以我们会判断出元素d时存在的，但是实际上元素d并不存在。

所以，在判断元素存在于集合的这点上，布隆过滤器是不准确的，和hash冲突一样，当特征值发生重叠时，布隆过滤器不能准确地判断元素是否存在于集合中，它会存在误判的可能，会将一些根本不在集合中的元素判断称存在。

从这点上来说，布隆过滤器只能准确地判断某一个元素不在集合中。

布隆过滤器的优点

• 高效的查询：

布隆过滤器通过使用多个哈希函数和位数组，可以在常数时间内进行快速的查询操作。不需要对集合进行遍历或者对比操作，因此查询效率非常高。

• 空间效率高：

布隆过滤器使用的位数组相比于其他数据结构（如哈希表）占用的空间更少。通过合理选择位数组的大小和哈希函数的数量，可以在一定的误判率下，大大减少所需的存储空间。

• 可扩展性

布隆过滤器可以根据需要进行扩展，可以动态地添加或删除元素。通过调整位数组的大小和重新计算哈希函数，可以适应不同规模的数据集。

• 无需存储实际数据

布隆过滤器只需要存储元素的哈希值，而不需要实际存储元素本身。这样可以节省存储空间，尤其适用于大规模数据集。

• 易于实现和使用

布隆过滤器的实现相对简单，只需设计合适的哈希函数和位数组即可。使用时，只需将元素通过哈希函数映射到位数组中，并进行查询即可。

布隆过滤器的缺点

• 存在一定的误判率：

由于布隆过滤器使用多个哈希函数来映射元素到位数组中的不同位置，可能会发生哈希冲突，导致不同元素被映射到相同的位上，从而导致误判。

• 无法删除元素：

布隆过滤器是一种基于位数组的数据结构，无法直接删除已经插入的元素。删除操作会影响到其他元素的判断结果。

• 需要占用较多的内存空间：

为了降低误判率，布隆过滤器需要使用较大的位数组和多个哈希函数，从而占用较多的内存空间。

• 无法存储额外的数据信息：

布隆过滤器只能判断元素是否存在，无法存储额外的数据信息，如元素的具体数值或其他属性。

• 哈希函数的选择和设计比较困难：

选择和设计适合的哈希函数对于布隆过滤器的性能和误判率有很大影响，但是并没有一种通用的方法来选择和设计哈希函数。不同的数据集和应用场景可能需要不同的哈希函数。

给布隆过滤器增加计数器

上例的布隆过滤器只是记录某个特征位的是否存在（即只有0和1两种状态），因此我们是无法删除元素的，例如元素a被移除了，因为我们不清楚其它元素有没有使用到位1和5，所以我们是无法把数组里的位1和5改成0的。

因此，如果需要支持元素删除功能的话，我们可以考虑给布隆过滤器增加计数器，亦即，位记录里不再是简单的0和1，而是具体的命中的次数，即上述的a，b元素进来后，数组里的记录是：

位	0	1	2	3	4	5	6	7	8	9	10
值	0	1	0	0	0	2	1	0	0	0	0

要删除的话，只需要做对应的特征位-1即可。

这样，我们就可以实现元素的删除了。

布谷鸟过滤器

布谷鸟过滤器是一种基于哈希的数据结构，类似于布隆过滤器，但具有更高的查找效率和更低的空间占用。

布谷鸟过滤器的工作原理可以理解为“鹊巢鸠占”。

布谷鸟过滤器是一种基于hash的数据结构，它的工作原理是：

• 布谷鸟过滤器是基于hash的数据结构
• 布谷鸟过滤器通过元素的特征指纹，位元素查找n个对应的位点，并随机将元素的特征值安放到其中一个空位点里。
• 如果没有空的位点，布谷鸟过滤器会随机踢掉其中一个位里的元素，并将自己的数据放置到该位点里
• 被踢出的元素重复上述流程，为自己重新查找位点
• 如果发生循环挤占，则进行扩容。
• 查找元素时，只需要计算元素的特征值，并根据特征值重新计算可能的位点，逐个位点判断元素是否存在即可。

布谷鸟过滤器的优点

布谷鸟过滤器的优点有：

• 低错误率：

布谷鸟过滤器具有较低的错误率，即误判率较低。这是因为布谷鸟过滤器使用了多个哈希函数和解决哈希冲突的机制，可以有效减少误判的概率。

• 动态性：

布谷鸟过滤器可以进行动态操作，如插入和删除元素。布谷鸟过滤器可以在插入或删除元素时进行重建，而不需要重新构建整个过滤器。这使得布谷鸟过滤器适用于动态数据集的场景。

• 较好的查询性能：

布谷鸟过滤器具有较好的查询性能。布谷鸟过滤器使用了多个哈希函数，可以减少哈希冲突的概率，从而提高查询的准确性和速度。

• 更优的空间效率：

布谷鸟过滤器在一些情况下可以比布隆过滤器占用更少的空间。这是因为布谷鸟过滤器可以解决哈希冲突，减少了额外的空间消耗。

布谷鸟过滤器的缺点

以下是布谷鸟过滤器的缺点：

• 内存占用较多：

相比于布隆过滤器，布谷鸟过滤器通常需要更多的内存空间。这是因为布谷鸟过滤器需要存储额外的指针来解决哈希冲突，从而增加了内存占用。

• 构建时间较长：

布谷鸟过滤器的构建时间相对较长。这是因为布谷鸟过滤器需要进行多次哈希计算和解决哈希冲突的操作，从而增加了构建的时间复杂度。

• 插入和删除的开销：

虽然布谷鸟过滤器支持动态操作，但插入和删除元素的开销相对较高。这是因为插入和删除元素时需要进行重建操作，可能涉及到多次哈希计算和指针的移动。