【数据结构与算法】【算法思想】位图

缺乏、安全感 2022-12-08 14:15 205阅读 0赞

## 位图BitMap ##

#### 算法 ####

public class BitMap {  // Java中char类型占16bit，也即是2个字节
      private char[] bytes;
      private int nbits;
      //nbits 总容量
      public BitMap(int nbits) { 
        this.nbits = nbits;
        this.bytes = new char[nbits/16+1];
      }
      //长度16 k/16 定位某一段 k%16定位段中某一位
      public void set(int k) { 
        if (k > nbits) return;
        int byteIndex = k / 16;
        int bitIndex = k % 16;
       //将数字 A 的第 k 位设置为1：A = A | (1 << (k - 1)) 
        bytes[byteIndex] |= (1 << bitIndex);
      }
    
      public boolean get(int k) { 
        if (k > nbits) return false;
        int byteIndex = k / 16;
        int bitIndex = k % 16;
        //将数字 A 的第 k 位设置为0：A = A & ~(1 << (k - 1))
    	//检测数字 A 的第 k 位：A & (1 << (k - 1)) != 0
        return (bytes[byteIndex] & (1 << bitIndex)) != 0;
      }
    }

## 布隆过滤器 ##

使用 K 个哈希函数，对同一个数字进行求哈希值，那会得到 K 个不同的哈希值，我们分别记作 X1，X2，X3，…，XK。我们把这 K 个数字作为位图中的下标，将对应的 BitMap\[X1\]，BitMap\[X2\]，BitMap\[X3\]，…，BitMap\[XK\]都设置成 true，也就是说，我们用 K 个二进制位，来表示一个数字的存在。当我们要查询某个数字是否存在的时候，我们用同样的 K 个哈希函数，对这个数字求哈希值，分别得到 Y1，Y2，Y3，…，YK。我们看这 K 个哈希值，对应位图中的数值是否都为 true，如果都是 true，则说明，这个数字存在，如果有其中任意一个不为 true，那就说明这个数字不存在。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

布隆过滤器的允许误判。如果某个数字经过布隆过滤器判断不存在，那说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，这个时候才会有可能误判，有可能并不存在。调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例，那就可以将这种误判的概率降到非常低。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

## 应用 ##

**如何实现网页爬虫中的URL去重功能？**  
我们用布隆过滤器来记录已经爬取过的网页链接，假设需要判重的网页有 10 亿，那我们可以用一个 10 倍大小的位图来存储，也就是 100 亿个二进制位，换算成字节，那就是大约 1.2GB。之前我们用散列表判重，需要至少 100GB 的空间。相比来讲，**布隆过滤器在存储空间的消耗上，降低了非常多。**  
\*\*利用布隆过滤器，在执行效率方面，比散列表更加高效。\*\*布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU 只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是 CPU 密集型的。而在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟待判重的网页链接，进行字符串匹配。这个操作涉及很多内存数据的读取，所以是内存密集型的。我们知道 CPU 计算可能是要比内存访问更快速的，所以，理论上讲，布隆过滤器的判重方式，更加快速。

[笔记整理来源： 王争 数据结构与算法之美][Link 1]  
参考资料：https://mp.weixin.qq.com/s/xxauNrJY9HlVNvLrL5j2hg

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/a62a2d920dec4d37add469941492bae0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/9482907c50434cc6a60ad28726c47062.png
[Link 1]: https://s1.ax1x.com/2020/08/03/aUh2TS.png