这是之前面试的时候面试官问到过的一个问题，今天正好看到 布隆过滤器，写篇文章总结一下
我们先看一下流程，流程懂了，问题就解决 90%了
我们都知道一个 int 占 4字节，一个字节又有 8个bit位，所以一个 int有 32位，没毛病吧？
位图就是：我们用一个 int 类型二进制位来表示 0~31的数是否存在。
稍微解释一下：
总体流程就是这样，那么该怎么实现一个位图呢，直接撸code（保姆级注释）。
public class BitMap {
private int[] bits;
/**
* @param max 数字的最大范围
*/
public BitMap(int max) {
// (max+1) >> 5 -> (max+1) / 32
// 这一步的意义就在于，如果数字最大范围 max 等于 10，直接除 32 的话，size 就等于 0 了，相当于做一下边界处理
int size = (max + 1) >> 5;
bits = new int[size];
}
public void add(int num) {
// 假如 num == 3
// num >> 5 -> num / 32，目的在于找到 num 在数组中哪一个位置，比如 35 / 32 = 1，说明 35 在数组下标为 1 的坑里
int idx = num >> 5;
// num & 31 >> num % 32 ，35 % 32 = 3，说明 35 在数组下标为 1 的坑里的第 3 位
int bit = num & 31;
// 现在我们知道 35 在第一个坑里的第三位，我们现在要把这个第三位设置为 1，先让 1 左移三位，然后或运算到原来的数上
// 或运算就是 有1为1
bits[idx] = (1 << bit) | bits[idx];
}
public void delete(int num){
int idx = num >> 5;
int bit = num & 31;
// 假如 bits[idx] 的二进制为：1011 1101 0110，假如 num 还是 35，那么 bit == 3
// 把 1 左移 3 位：0000 0000 1000
// 取反：1111 1111 0111
// 再与 bits[idx] 做与运算： 1011 1101 0110 ，就相当于把第 bit 位置为 0 了
bits[idx] = (~(1 << bit)) & bits[idx];
}
public boolean contains(int num) {
int idx = num >> 5;
int bit = num & 31;
// 假如 bits[idx] 的二进制为：1011 1101 0110，假如 num 还是 35，那么 bit == 3
// 把 1 左移 3 位：0000 0000 1000
// 做与运算，如果 bits[idx] 第 3 位为 1，那么和 1 左移 3 位后的结果 作 与运算 肯定就不会为 0 。
return (bits[idx] & (1 << bit)) != 0;
}
}
弄清楚位图后我们来看一下位图的场景。
假如我们有 10亿 个数字，假设数字的范围在 0~10 亿，我们现在需要对这些数字进行去重操作。
谈到去重，你一定会想到使用 HashSet的方式，我们都知道一个 int 类型的数字占用 4字节，如果 10亿数字中，有 5亿的重复数据，那就需要 5*4 = 20亿字节≈ 2G的内存空间。
如果使用位图的方式，我们只需要申请长度为 10亿/32 ≈ 3千万 的数组，这时候内存占用为 3千万*4≈1.2亿字节可以看到使用 位图比 HashSet内存占用少了大约 20倍。
稍微增加一下难度，我们都知道 int 类型 -> 4字节 -> 32位，范围也就在 21亿的样子
一个手机号 11位，范围是 [100亿，1000亿)，如果我们使用之前的存储方式，发现根本没有数据类型能够存储这么大的数据。
这时候就要用到 HashMap分桶的概念了，我们都知道手机的号码段都是前三个都是固定的： 135, 136, 159… 我们可以分为不同的 bit桶，比如 bits135, bits136, bits159…
这时候剩下的手机号还有 8 位，也就是 [100万，1000万]的范围，这时候就可以用 int 进行存储。
看到这里我相信你已经发现了 位图的特点：
通过二进制位来压缩数据量，同时也存在一个很大的局限性，只能存储数字，且对数字大小还有要求
如果对 10 亿的 IP 进行去重，或者对10亿的 UUID 进行去重，那又该如何设计呢？
这就要引出 位图的 pro 版本： bloom filter（布隆过滤器）
Original: https://www.cnblogs.com/Fzeng/p/16101122.html
Author: 小冯同学c
Title: 拜托，面试官别问我「位图」了
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/592983/
转载文章受原作者版权保护。转载请注明原作者出处！