经常听到的位图、布隆过滤器到底是什么？本文带你来拆解一下~

Q：给定一组学生数据，数据格式为学号-学生姓名；现在要求：输入学生的学号，能够快速查询出学生的姓名。

A：如何解决上面的问题？思路有如下：

遍历，直接暴力遍历，直到找到学生姓名

使用哈希表，通过哈希表的key-value映射来查找

使用数组下标映射的关系，通过将id作为学生下标来存储学生姓名。

图片

通过上面的问题，我们知道可以通过一一映射的关系来进行数据快速存储查询。

位图：位图位图，就是只存储一位（0/1），通过0/1来判断true/false

Q：现在又有一个问题，假设有万个整数，整数范围为0~3千万。问：如何快速确定某个数据是否在这万个数据中？

A：来思考下如何解决，常见方案如下：

①基于数组：这种方式的话就要直接暴力遍历，伪代码如下：

for(inti=0;inums.length;i++){if(nums[i]==target)returni;}

②基于排序数组：这种方式是对上面方法的改进，通过排序后可以进行二分查找，提高查找效率。

Arrays.sort(nums);//进行排序//二分查找伪代码booleanbinarySearch_r(int[]nums,intleft,intright,target){while(left=right){intmid=left+(right-left)/2;if(nums[mid]==target)returntrue;if(nums[mid]target){binarySearch_r(nums,mid+1,right);}else{binarySearch_R(nums,left,mid-1);}}returnfalse;}

③基于哈希表：基于哈希表实现的话，维护对应的数值关系即可。

④基于一一映射的数组：就是使用数组，将有值的下标标记为true，否则标记为false。

图片

⑤基于位图：基于上面方式的话，可以，但是true/false还是很占空间啊

我的需求只是要知道是不是有没有存在这个数而已

只有想不到没有做不到，我们思考一下能不能直接用0/1来存储每一位上的值。

实际上是可以的，通过使用char类型的数组，char是16个字节，64位，每位来保存对应的数据。

赋值：a[charIdx]

=(1bitIdx)

取值：a[charIdx](1bitIdx)

让每位的0/1表示有没有这个值

图片

接着上面题目进行延伸，假设有0万个整数，整数范围为0~1亿。问：如何快速确定某个数据是否在这0万个数据中？

如果要接着使用位图的话，就要存储相当大的存储空间了。

但是我们转念一想，如果使用位图，并且对应的下标为哈希计算之后的值，这样可以减少存储空间。

只是，这样的话就很容易导致哈希冲突，也就是两次计算之后的值是一样的。

图片

所谓的布隆过滤器，其实就是位图+容忍存在hash冲突的误判

我们假设使用上面图中的布隆过滤器判断某个值是否存在，如果存在的话例如:hash()==1，hash()==1,而hash()肯定是0

这样的话，就算存在哈希冲突，也造不成多大的关系。

通过使用布隆过滤器，我们可以快速地知道某个值是否存在数据中，大大提高查询速度。

比如，在判断某个数据是否存mysql中时，先访问缓存中的位图判断是否存在，如果数据压根不存在mysql中的话，就不用走库区查询了，减少数据库的操作。

图片

1、通过对数组的了解，我们知道数组的下标可以得到更好的利用

2、位图采用更少的空间消耗来存储数据，实现数据和一些业务目的一一映射

3、布隆过滤器是“粗糙版”的位图，通过布隆过滤器可以实现海量数据下的数据是否存在判断

如果你有任何想法，欢迎和我留言，也欢迎

转载请注明:http://www.aideyishus.com/lktp/475.html