位图和布隆过滤器

位图

位图的概念

• 位图（bitmap）其实就是哈希表的一种特殊情况。不同的是位图是通过二进制位来表示数据是否存在。
• 位图比哈希表更加节省空间，只需要用一个二进制位就能表示一个数字。

位图的例子

• 假设有1000万个范围在1-1亿的整数。如何快速查找某个整数是否出现在着这1000万个整数中。
• 如果用哈希表去解决。我们可以创建一个长度为1亿，存储的数据类型为bool值的数组。将这1000万个整数对应的数组下标的数组元素设置成true。我们判断某个整数K是否出现在这1000万个整数中时，我们可以直接去取array[K]是否为true，来进行判断。
• 如果用位图去解决，则更佳节省空间。表示true和false的bool值只需要用一个二进制位来表示就足够了。我们可以利用一个char类型的数组，char是一个字节，有8位，也就是说可以表示8个数组的有无。我们用取到的整数除以8，得到这个数字应该存储在哪个数组元素中后，再取这个整数与8的余数，就能得到这个数字在这个元素中的哪一位。取到对应的位上存储的bool值，即可以得出是否存在这个数字的结果。

布隆过滤器

布隆过滤器的产生

• 位图的应用场景有一定的局限性，就是数据所在的范围不能太大。因为位图是用位来表示true和false的信息的。并不能像哈希表一样，数组中的元素为链表，存储多个数据的形式。因此当数据范围很大的时候，反而会比哈希表的内存占用还要大。
• 由于上述的情况，我们就要对位图进行优化和改进。布隆过滤器就是一个很好的解决办法。

布隆过滤器的概念

• 布隆过滤器的核心思路：使用多个哈希函数，计算多个哈希值，用多个位去记录数据的存在。

• 当执行查询结果的时候，同样也是使用多个哈希函数，通过得到的多个哈希值取到多个位，如果所有的位中存储的都是true，则说明数据存在。如果有false的数据，则说明数据不存在。

• 尽管用多个哈希值去判断，但仍然是存在误判的情况。但布隆过滤器误判有一个特点：只有判断起存在的情况时，才有可能发生误判，这个数据有可能是不存在的。换句话讲，就是判断结果是其不存在时，那就是真的不存在，不存在的情况是不会存在误判的。

• 布隆过滤器的误判率和两个因素有关系。

  1.使用的哈希函数的个数。

  2.位图的大小。

• 对于动态数据，随着数据不停的增长，布隆过滤器的误判率也会越来越高，因此布隆过滤器还需要支持动态扩容。当数据个数和位图大小的比例超过某个阈值时，我们需要重新申请一个新的位图。对于后进入的数据，我们将其放置在新的位图中。同样，要判断这个数据是否存在的话，需要查看多个位图，相应的执行效率也会降低。

布隆过滤器的例子

• 利用布隆过滤器的特点，即判断数据不存在的情况是一定正确的。我们在查询某个数据时，可以先访问布隆过滤器，如果经过布隆过滤器判断数据不存在，也就不需要访问数据库去查询数据了，这样就减少了数据库的查询操作。