写在前
bitmap和布隆过滤器主要解决大数据去重的问题。用于对大量整型数据做去重和查询。其实如果并非如此大量的数据，有很多排重方案可以使用，典型的就是哈希表。
实际上，哈希表为每一个可能出现的数字提供了一个一一映射的关系，每个元素都相当于有了自己的独享的一份空间，这个映射由散列函数来提供（这里我们先不考虑碰撞）。实际上哈希表甚至还能记录每个元素出现的次数，这样的数据结构完成这个任务有点“大材小用”了。
如果用HashSet或HashMap存储，每一个用户ID都要存成int，占4字节即32bit。而一个用户在Bitmap中只占一个bit，内存节省了32倍！所以散列表最大的问题是所占用的空间非常大！！！
Bitmap位图算法
为什么用位图？
我们先来看一个问题，假设我们有1千万个（不重复、未排序）的整数需要存储，每个整数的大小范围是1到1亿。然后，给定任意一个整数X，我们需要快速判断X是否在刚才的1千万个整数内。这个问题该如何处理呢？
常规的做法肯定就是先考虑如何存储这1千万个整数，在Java中，int类型是4个字节，可以表示的范围区间是-2147483648~2147483647，所以每个整数都用int来表示是可行的。那么1千万个整数需要占用多少内存空间呢？两者相乘就是了，应该是4000万字节，也就是40MB。
而且如果我们存放的整数是是一亿个（甚至更大），每个整数大小范围是1到100亿怎么办？占用的内存空间将会是非常巨大的，是普通的计算机或者手机不能接受的（放不下）。
ps：多台机器存储的话，资源占用量太大；另外可以不用内存，但是I/O效率低；
所以我们需要使用位图这种数据结构来大大节省内存的使用量。
什么是位图？
我们知道Byte表示字节，一个字节等于8bit，这里的bit就和位图有关系。在上面的例子中，我们不是要存放1千万个整数嘛，那就申请一个具有1千万个bit的数组，用每个bit（二进制位）来表示一个整数，当前bit为0表示不存在这个整数，为1表示该整数就存在。
虽然数量是1千万个，但是每个数的范围是1到1亿，所以我们需要1亿个bit，换算下来，就是12.5MB，和刚才的40MB相比，节省的不是一点点。
位图是指内存中连续的二进制位，用于对大量的整型数据做去重和查询。Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。
对于位图的底层存储结构实际为数组结构,目的是为了存储大量的数据,为了表示存储的数据是否存在,可以使用0/1代表true/false。
存储的数据流程为
-
根据自定义的hash计算公式得到对应的数组下标
-
并将数据进行相应的位运算得到的结果存储到数组中;
当需要查询数据时
-
将当前要查询的数据转换为对应的数组索引
-
根据索引定位数组中的数据并执行存储时位运算的相反操作判断数据是否存在
可以看出位图基于数组下标查询效率非常高效,且相对而言,位运算使用cpu计算也比较高效；由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
位图也存在一些缺点,对于随着数据量的增加,要申请数组的空间也越来越大。
bitmap应用
1）可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
2）去重数据而达到压缩数据
比如 Java 中的 BitSet 类就是一个位图，Redis 也提供了 BitMap 位图类
布隆过滤器
为什么用布隆过滤器？
位图存在两个问题
-
处理数字很方便，但是处理字符就稍微有点困难了
-
（关键）位图在数据量过大情况下导致了内存浪费
布隆过滤器为了解决内存占用的问题,由于位图实际是利用一个index来定位一个数据,如果在数据密集度相对稀疏的情况下,会导致数组空间浪费(存在大量空洞插槽); 布隆过滤器利用多个插槽位置来定义一个元素,尽最大的可能性来提高空间利用率; 对于一个数据对应多个插槽,实际就是利用多个hash函数生成多个索引位置。
什么是布隆过滤器？
布隆过滤器实际是基于位图来实现的一种数据存储结构，用来判断某个元素（key）是否在某个集合中。和一般的位图不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。
布隆过滤器最大的特点，就是对一个对象使用多个哈希函数。如果我们使用了 k 个哈希函数，就会得到 k 个哈希值，也就是 k 个下标，我们会把数组中对应下标位置的值都置为 1。布隆过滤器和位图最大的区别就在于，我们不再使用一位来表示一个对象，而是使用 k 位来表示一个对象。这样两个对象的 k 位都相同的概率就会大大降低，不仅能够解决单哈希容易造成冲突的问题，还能有效减少内存空间的使用。
但要注意的是,布隆过滤器 主要是为了解决空间浪费问题,并不能完全解决hash冲突;
由于hash冲突的存在会导致一些误判的发生（无中生有）,虽然使用多个hash函数可以降低冲突的概率,但还是会存在一些极端的情况出现hash冲突,导致不存在的数据被布隆过滤器判定为存在;但是对于布隆过滤器判定为不存在的数据,是肯定不存在的。
虽然布隆过滤器对于空间利用率较高,但随着数组剩余空间越来越小,会导致hash冲突的概率越来越大,因此需要设置一个阈值,当剩余空间达到一定阈值后,就需要执行扩容,降低hash冲突概率。
优缺点：
-
优点：不需要存储key，节省空间
-
缺点：算法判断key在集合中时，有一定的概率key其实不在集合中，已经映射的数据无法删除
应用场景
redis 缓存穿透 就可以利用 布隆过滤器来降低缓存穿透发生概率;
redis 缓存穿透的理解 , 对于 redis中和数据库中都不存在的数据,当从redis中获取不到数据时,请求就会请求到服务端执行db查询操作（绕过缓存）,当存在大量缓存穿透的情况就会导致redis和服务以及数据库的压力剧增;
当redis 使用 布隆过滤器后,
-
首先能通过布隆过滤器的判定,对于不存在的数据,redis和db中肯定都不存在;
-
但对于布隆过滤器判断为存在的数据,即使经过redis查询发生数据不存在,从而查找db也发现数据不存在 的情况, 但对于这种情况毕竟几率较低,即使出现了对整个redis以及服务的压力也不会非常大
其他：比如网络爬虫抓取时url去重，邮件提供商反垃圾黑名单Email地址去重，之所以需要k个比特位是因为我们大多数情况下处理的是字符串，那么不同的字符串就有可能映射到同一个位置，产生冲突（尽可能的降低hash冲突）。
总结
-
BitMap:把数值转化为数组的下标，下标对应的值只存放一个bit 0或1 ，0不存在 1存在。判断时 根据数值当做下标找到对应的 bit 值，1存在，0不存在
-
BloomFilter:把内容通过多个hash算法，转换成多个数组下标，下标对应的值只存放一个bit 0或1 ，0不存在 1存在。判断过滤时 多个下标对应的值都为1，则可能存在，只要有一个值为0，则一定不存在
巨人的肩膀：
网友评论