这是之前面试的时候面试官问到过的一个问题,今天正好看到 布隆过滤器,写篇文章总结一下
我们先看一下流程,流程懂了,问题就解决 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/
转载文章受原作者版权保护。转载请注明原作者出处!