位图

1、简介

位图（BitMap），基本思想就是用一个bit来标记元素，bit是计算机中最小的单位，也就是我们常说的计算机中的0和1，这种就是用一个位来表示的。 所谓位图，其实就是一个bit数组，即每一个位置都是一个bit，其中的取值可以是0或者1。

位图最大的好处就是节省空间。 位图有很多种用途，特别适合用在去重、排序等场景中，著名的布隆过滤器就是基于位图实现的。

但是位图也有着一定的限制，那就是他只能表示0和1，无法存储其他的数字。所以他只适合这种能表示ture or false的场景。

"Bitmap"算法通常指的是位图索引算法，它是一种常用的数据结构和算法，用于高效地存储和查询大量的布尔值或整数值。它的基本思想是将每个值映射到一个位图中的一个位上，从而将大量的值压缩到一个位图中，从而节省存储空间和提高查询效率。

常见的位图算法包括布隆过滤器和Roaring Bitmaps。布隆过滤器是一种基于哈希函数的数据结构，用于判断一个元素是否存在于一个集合中，它可以高效地处理大量的查询请求，但可能会出现误判。Roaring Bitmaps是一种基于位图的数据结构，它可以高效地存储和查询大量的整数值，同时具有压缩和快速合并等优点。

除了位图索引算法，"Bitmap"算法还可以指其他与位图相关的算法，例如位图图像处理算法、位图压缩算法等。

2、布隆过滤器

布隆过滤器是一种数据结构，用于快速检索一个元素是否可能存在于一个集合(bit 数组)中。

它的基本原理是利用多个哈希函数，将一个元素映射成多个位，然后将这些位设置为 1。当查询一个元素时，如果这些位都被设置为 1，则认为元素可能存在于集合中，否则肯定不存在。

所以，布隆过滤器可以准确的判断一个元素是否一定不存在，但是因为哈希冲突的存在，所以他没办法判断一个元素一定存在。只能判断可能存在。

所以，布隆过滤器是存在误判的可能的，也就是当一个不存在的Hero元素，经过hash1、hash2和hash3之后，刚好和其他的值的哈希结果冲突了。那么就会被误判为存在，但是其实他并不存在。

想要降低这种误判的概率，主要的办法就是降低哈希冲突的概率及引入更多的哈希算法。

代码见：D:\Github\Storage\c++\bitmap\BloomFilter.cpp

2-1、应用场景

1、网页爬虫： 爬虫程序可以使用布隆过滤器来过滤掉已经爬取过的网页，避免重复爬取和浪费资源。

2、缓存系统： 缓存系统可以使用布隆过滤器来判断一个查询是否可能存在于缓存中，从而减少查询缓存的次数，提高查询效率。布隆过滤器也经常用来解决缓存穿透的问题。

3、分布式系统： 在分布式系统中，可以使用布隆过滤器来判断一个元素是否存在于分布式缓存中，避免在所有节点上进行查询，减少网络负载。

4、垃圾邮件过滤： 布隆过滤器可以用于判断一个邮件地址是否在垃圾邮件列表中，从而过滤掉垃圾邮件。

5、黑名单过滤： 布隆过滤器可以用于判断一个IP地址或手机号码是否在黑名单中，从而阻止恶意请求。