JavaDS —— 位图（BitSet）与 布隆过滤器

位图

引入问题：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

首先要注意 40 亿个数据如果使用 整型（int) 来存放的话，就是要 40 亿个整型，一个整型有4个字节，一个字节有8个比特位，我们换算一下，40亿个字节差不多需要 15 GB 来存储，我们可以这样简便的记忆 10亿 个字节约等于 1GB

一般情况下，大家的电脑运行内存为 16GB 或者 更大的 32GB，但是我们不可能真的把这40亿 的整型数据存储进去，我们的电脑运行内存还有其他应用程序也占用着，所以我们就要想办法去缩小存储空间，这时候就可以考虑位图了

概念

位图，就是用每一位来存放某种状态，适用于海量数据，整数，数据无重复的场景。通常是用来判
断某个数据存不存在的。

位图并不是将数据存储进去，而是将这个数据的状态存储进去（即该数据存在或者不存在），位图利用比特位的 0 与 1 来表示数据的状态，通过映射关系来进行存储与读取。

举个例子：
这是位图的初始状态：

位图上面的红色 7 ~ 0 的数字大家可以自行定义顺序，可以逆序，也可以顺序，只是映射关系不同，我这里使用的是逆序

我们来插入数据，使用映射关系：使用除法式子确定下标，取模来确定具体的比特位

模拟实现

成员变量，这里我使用字节数组 byte[] 来模拟位图，源码底层是使用 long[] ，然后再加上一个统计目前元素个数的成员变量 useSize.

提供两个构造方法，注意带参数的构造方法是为了让用户自行设置大小，但是用户设计的是元素的多少，而实际我们每次开辟一个字节就可以保存 8 个元素，这里要注意换算关系。

    public MyBitSet() {this.elem = new byte[1];}public MyBitSet(int size) {if(size < 0) {throw new IndexOutOfBoundsException("设置的大小无效");}int num = size / 8 + 1;this.elem = new byte[num];}

---

在存储数据的时候，先通过映射关系来确定下标，如果下标越界，数据就要扩容，然后再存储数据，这里该如何存储数据，我们可以让 1 左移 val % 8 个位置，这样就可以对齐到这个数据的具体的比特位，然后我们再考虑使用什么位运算符来进行计算，如果比特位本身为1说明再次存储相同的数据还是为 1 ，从这里就可以看出位图无法存储相同的数据（有去重的功能），如果比特位原本为 0 那插入数据之后就要变成 1， 可以看出 这里要使用的是 或运算（|）

    public void set(int val) {int index = val / 8;if(index > elem.length) {elem = Arrays.copyOf(elem, (index + 1) * 2);}elem[index] |= 1 << (val % 8);useSize++;}

---

是否存在某个元素：
这里要注意的是要使用的是 & 运算符

    public boolean get(int val) {int index = val / 8;if(index >= elem.length) {return false;}if((elem[index] & (1 << (val % 8))) == 0) {return false;}return true;}

---

删除：
删除元素的时候，要注意是只删除对应的元素，如果该元素存在对应的比特位为 1，先按位取反 (1 << (val % 8)) 然后再与运算，这样就可以删除成功了。

    public boolean remove(int val) {int index = val / 8;if(index >= elem.length) {return false;}elem[index] &= (~(1 << (val % 8)));useSize--;return true;}

---

获取元素个数：

    public int size() {return useSize;}

最终代码

public class MyBitSet {private byte[] elem;private int useSize;public MyBitSet() {this.elem = new byte[1];}public MyBitSet(int size) {if(size < 0) {throw new IndexOutOfBoundsException("设置的大小无效");}int num = size / 8 + 1;this.elem = new byte[num];}public void set(int val) {int index = val / 8;if(index >= elem.length) {elem = Arrays.copyOf(elem, (index + 1) * 2);}elem[index] |= (1 << (val % 8));useSize++;}public boolean get(int val) {int index = val / 8;if(index >= elem.length) {return false;}if((elem[index] & (1 << (val % 8))) == 0) {return false;}return true;}public boolean remove(int val) {int index = val / 8;if(index >= elem.length) {return false;}elem[index] &= (~(1 << (val % 8)));useSize--;return true;}public int size() {return useSize;}
}

BitSet

在java.util这个包下有一个 BitSet 的类，这个就是Java提供给我们的位图的数据结构：

方法	说明
BitSet()	无参的构造方法
BitSet(int nbits)	可以设置位图的大小
void set(int bitIndex)	插入数据
boolean get(int bitIndex)	查看数据是否存在
int size()	位图存放的元素总数

位图的应用

1. 快速查找某个数据是否在一个集合中
2. 排序 + 去重
3. 求两个集合的交集、并集等
4. 操作系统中磁盘块标记

排序是因为位图存放的数据已经有序，我们只需要遍历位图依次打印出数据即为有序。

布隆过滤器

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结
构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函
数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

引用场景：
一个像 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃
圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者
不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服
务器。

如果用哈希表，每存储一亿个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个
email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有
50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此
存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

小结：

1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3. 将哈希与位图结合，即布隆过滤器

插入

布隆过滤器的思想是将一个元素用多个不同的哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1

具体使用多少个哈希函数是可以通过数学进行计算的。并且哈希函数的设置也是有规定的，作为开发人员我们就使用就可以了。

查找

分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因
为有些哈希函数存在一定的误判。

举个例子：如果一个字符串通过不同的哈希函数映射到的位置分别为 0，3，4，刚好和 上面的 world 重合，但是这个字符串却本身不存在，只是正好哈希值和另一个元素重合，所以可能会存在误判

删除

传统的布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。
缺陷：

1. 无法确认元素是否真正在布隆过滤器中【会有误判】
2. 存在计数回绕【回绕意思为：溢出】

模拟实现

class SimpleHash {public int cap;//当前容量public int seed;//随机值public SimpleHash(int cap,int seed) {this.cap = cap;this.seed = seed;}//根据seed不同 创建不能的哈希函数int hash(String key) {int h;return (key == null) ? 0 : (seed * (cap-1)) & ((h = key.hashCode()) ^ (h >>> 16));}}public class BloomFilter {//默认大小public static final int DEFAULT_SIZE = 1 << 20;//位图public BitSet bitSet;//记录存了多少个数据public int usedSize;public static final int[] seeds = {5,7,11,13,27,33};public SimpleHash[] simpleHashes;public BloomFilter() {bitSet = new BitSet(DEFAULT_SIZE);simpleHashes = new SimpleHash[seeds.length];for (int i = 0; i < simpleHashes.length; i++) {simpleHashes[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);}}public void set(String val) {for (int i = 0; i < simpleHashes.length; i++) {int hash = simpleHashes[i].hash(val);bitSet.set(hash);}usedSize++;}public boolean get(String val) {for (int i = 0; i < simpleHashes.length; i++) {int hash = simpleHashes[i].hash(val);if(!bitSet.get(hash)) {return false;}}return true;}public int size() {return usedSize;}
}

布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

布隆过滤器缺陷

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
2. 不能获取元素本身
3. 一般情况下不能从布隆过滤器中删除元素
4. 如果采用计数方式删除，可能会存在计数回绕问题

布隆过滤器使用场景

1. google的guava包中有对Bloom Filter的实现
2. 网页爬虫对URL的去重，避免爬去相同的URL地址。
3. 垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱。
4. 解决数据库缓存击穿，黑客攻击服务器时，会构建大量不存在于缓存中的key向服务器发起请求，在数
   据量足够大的时候，频繁的数据库查询会导致挂机。
5. 秒杀系统，查看用户是否重复购买。

海量数据处理

哈希切割

给一个超过 100G 大小的log file,log 存在log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？

答：使用哈希切割，将这个大文件通过哈希切割分成若干个小文件，每一个小文件只存储一个IP地址，剩下的就简单了。

位图应用

1.给定100亿个整数，设计算法找到只出现一次的整数？

答：解法一：使用哈希切割，将数字哈希到对应的小文件中
解法二：使用两个位图（bitSet1 和 bitSet2）,当插入数据的时候，先检查 bitSet1 的比特位是否为0，是则变为1，不是则在 bitSet2插入，这样的话，我们还可以进一步划分，当 bitSet1 为0 、bitSet2 也为0 时，则该数据重未出现过，
当 bitSet1 为0 、bitSet2 也为0 时，则该数据出现过一次，
当 bitSet1 为0 、bitSet2 也为0 时，则该数据出现过两次，
当 bitSet1 为0 、bitSet2 也为0 时，则该数据出现过三次及以上

解法三：使用一个位图，这时候我们可以利用解法二，将两个比特位表示一个数据的状态：

这样的话，就不能直接使用Java 提供的位图了，我们需要自己手动搓一个位图，映射关系也要修改。
举个例子：如果插入数据 4 ，4 / 4 = 1 （说明要插入到 数组的 1 下标）4 % 4 * 2= 0（说明要修改的是 0 号位置与 1 号位置）
所以这时候映射关系应该为 index = num / 4， i = num % 4 * 2

---

2.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

答：解法一：使用哈希切割
解法二：使用一个位图：遍历第一个文件将数据保存到 bitSet1 ,遍历第二个文件，在遍历第二个文件的同时，检查数据是否也出现在 bitSet1
或者使用两个位图，分别保存两个文件的数据，然后将两个位图按位与 &

拓展：
并集：两个位图按位或 |
差集：（差集 的概念是所有属于A且不属于B的元素构成的集合），这里指属于位图1但不属于位图2 和 属于位图2但不属于位图1 的元素集合，那么将位图1 按位异或 ^ 位图2

---

3.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数

答：解法一：使用哈希切割
解法二：使用两个位图
解法三：使用一个位图（两个比特位表示一个整数的状态）

布隆过滤器应用

1.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和
近似算法

精确算法：使用哈希切割或者两个位图
近似算法：使用布隆过滤器，先将第一个文件存储进布隆过滤器中，再遍历第二个文件同时查看布隆过滤器。

---

2.如何扩展BloomFilter使得它支持删除元素的操作

布隆过滤器中的每个比特位扩展成一个小的计数器，删除的时候计数器减1