“携手创造，共同成长！这是我参与「日新计划 10 月更文应战」的第十九天，点击检查活动详情”
一、为什么要运用位图
咱们先来看一个问题，假定咱们有1千万个不同的整数需求存储，每个整数的巨细规模是1到1亿。然后，给定任意一个整数X，咱们需求判别X是否在方才的1千万个整数内。这个问题该如何处理呢？
惯例的做法必定便是先考虑如何存储这1千万个整数，在Java中，int类型是4个字节，能够表明的规模区间是-2147483648~2147483647，所以每个整数都用int来表明是可行的。那么1千万个整数需求占用多少内存空间呢？两者相乘便是了，应该是4000万字节，也便是40MB。
而且假如咱们寄存的整数是是一亿个，每个整数巨细规模是1到100亿怎么办？占用的内存空间将会是非常巨大的，是一般的计算机或许手机不能承受的。
所以咱们需求运用位图这种数据结构来大大节省内存的运用量。
二、什么是位图
咱们知道Byte表明字节，一个字节等于8bit，这里的bit就和位图有联系。在上面的比如中，咱们不是要寄存1千万个整数嘛，那就请求一个具有1千万个bit的数组，用每个bit（二进制位）来表明一个整数，当时bit为0表明不存在这个整数，为1表明该整数就存在。
尽管数量是1千万个，可是每个数的规模是1到1亿，所以咱们需求1亿个bit，换算下来，便是12.5MB，和方才的40MB比较，节省的不是一点点。
三、布隆过滤器
位图也不是万能的，假使咱们需求寄存的1千万个整数的规模是1到100亿怎么办，按道理说，咱们请求一个包含100亿个bit的数组就能够了，也是需求1.25GB，太大了，这也是许多电脑和手机承受不起的，那怎么办呢？
布隆过滤器便是让咱们有方法在原来12.5MB的内存空间下，运用1亿个bit来寄存本来需求100亿个bit才干解决的问题。咱们的中心思维便是运用hash函数，把1到100亿巨细的数值映射到1到1亿个bit内。
可是这必定会造成抵触的，鸽巢理论就告知过咱们这一点了。那咱们就运用多个不同的hash函数，来把同一个值映射到1到1亿bit中的不同位置上，如此，咱们运用多个bit的值来表明一个数值是否存在。对于两个不同的数值来说，经过同一个hash处理得到的值可能会抵触，可是经过多个hash处理得到的多个值就不太可能全部抵触的。
上图：布隆过滤器的工作原理
当咱们将某个整数放到内存中时，把它一切hash出来的bit都置为1；当咱们需求判别给定的整数X是否现已存在时，就去读取一切的hash出来的bit值，只需有一个不是1，那么就阐明这个值不存在；
可是假如一切hash出来的bit值都是1，也不能一定阐明这个值X便是现已存在的，布隆过滤器会对结果为存在的情况产生误判。
上图：布隆过滤器产生误判的场景示意
当咱们参加的数据越来越多，位图中为0的bit越来越少的时候，布隆过滤器产生误判的概率就会越来越高了。假定咱们能提早知道总共有多少数据和数据的规模，咱们能够经过调整hash函数的个数、位图的巨细来减小误判产生的概率；假定咱们并不能提早知道这些，那咱们的位图就需求支撑自动扩容，当为0的bit小于某个阈值的时候，咱们就应该触发扩容位图的操作。
布隆过滤器在对某些能够容忍小概率误判的事务场景非常有效。
四、位图的常见运用场景
4.1 生成看似无规律却呈趋势递增的号段式ID
4.2 搜索引擎爬虫网页去重
4.3 大型网站每天UV数量统计
五、结语
下一篇会实战运用位图来完成抖音号、淘淘号等需求生成看似无规律却呈趋势递增的号段式ID。
