bitmap算法的介绍

尽管用某种列表的下表来作为某个元素的值这种想法很多人都有（大学的时候做算法题经常会有这种想法，有时也会付诸实践），但是相信刚从大学出来，很少有人会知道这种思想已经被提炼成一种算法了。

bitmap算法的意思就像他的名字，它是由一堆bit组成的map，它先初始化一大堆bit，就假设n个bit吧。然后，这些bit的下标作为某种哈希算法的值，bit本身表示该值是否存在。如果不告诉你他的应用场景，你可能会觉得这是一个怪异的数据结构。

下面看这样一个问题，你是一个淘宝比价网的程序员，你要实现一个爬虫，爬取淘宝很多很多的url。我们可以想到，淘宝有成亿上兆的商品，这意味着你爬取得数据量可以说是海量。我们也可以想像得到，这些url肯定会有重复，因为很多页面下的链接指向的是同一个商品。那么问题来了

我如何对这些海量的url进行去重？

那么我们来分析，去重，最耿直的想法是，一个一个看，每一个新爬取的url需要与前面的爬取的url进行比较，这个是属于没有计算机素养，小孩子也可以想到的办法。
那么有些学过编程的同学，会说我使用Set这种数据结构，这种数据结构本身已经实现了去重，我好方便的，直接往里面丢就行了。

其实这些想法都忽略了这是一个海量数据处理问题：我算有一亿的商品，一个url我算0.05kb，那么整个Set占用4882.8125Mb，就是4个G的内存，工业上是不允许的。

那么现在我们来看看bitmap

我有一亿商品的url，我直接分配一亿个bit，bit的下表表示这些url的hash值，至于数据的内容嘛我就丢数据库好了，反正我去重也只需要比较hash值。
现在我将这些url全部都hash，并将下表为这些hash值的bit位全部置为1，如果接下来的一个url，下标为他的hash值的bit位已经是1，那么表示这个url已经存在了（灰色表示该bit为1，下图表示hash值为3的url已经存在了）

那么像这样子，我们就可以用一亿个bit来代表这一亿个url来参与解决去重问题，总共需要多少空间呢？
100000000Bit = 12500000Byte = 12207Kb = 12Mb 这个空间效率的提升是核爆式的。

一个问题
这种bitmap算法需要使用到hash来处理元素的值，既然是hash，那么就会存在冲突，在冲突的情况下，可能会有另一个不一样的url，他的hash值也是3，这个时候我们看到下标为3的bit位被置为1，就会认为这是个已经存在的，出现这个错误的概率是n/(m*p)，n为被置为1的bit数，m为总的bit数，p为hash冲突的概率，如何降低这个概率？下面就会说到这个算法的升级版：布隆过滤器。