有100亿个url被加入了黑名单，现在提供一个url要去判断是否属于黑名单。也就是一个很简单的一个东西是否属于一个集合的问题。
一般来说用set就能解决这种问题，但是由于url数目太多，内存中无法开辟一个这么大的空间去存放所有url，这个时候就需要我们去使用一种结构，去减少状态信息存储所需要的内存，而布隆过滤器就可以很好地实现这个功能。
2.基本知识
在了解布隆过滤器算法前，需要先了解一些前置知识，例如哈希函数和位图
哈希函数
哈希函数就是一个映射函数，可以把任意长的输入位（或字节）变化成固定长的输出字符串的一种函数。理想的哈希函数是从所有可能的输入值得到所可能的有限输出值的一个随机映射。
性质
哈希函数保证有离散性，即当m1和m2 这两个输入有一点差别的时候，最终经过哈希函数计算的输出结果可能完全不同，离散开来。
对于相同的输入，哈希函数计算的输出一定会相同，反过来只要输出不相同，那么输入一定就不会相同。对于不同的输入，极小概率下，哈希函数的计算输出会相同（即哈希碰撞），一般都不同。
同时哈希函数也保证有均匀性，即在输出的大范围里，每一小片区域中存在的值的个数是相近的（举例：一共有1000个值被输出，在整个输出范围里，每一小片区域里包含的值的个数基本相同）。
hash函数为单向函数，给定消息m可以很容易计算h(m)，但对于给定的x，不能求出满足x=h(m)的m
总而言之，哈希函数就是一个映射函数，计算的结果H（m）会在值域上离散均匀分布
位图
位图，bitmap或者bitarray，就是用bit位去存储信息的一种结构。正常的数组要么是int数组或者是long数组，每个元素是4字节或者8字节，也就是32bit或者64bit的信息表示一个元素或者一种状态。而bitarray就是1个bit表示数组里的一个元素或者一种状态，这样的优点就是非常省空间，本来用几十个bit表达的信息被它用1个bit就表达了（前提是信息能用位图表达的情况下）。
下面一串数字0和1即是位图的表示，一共有32个数字，分别表示数组里的32个元素，这些元素的值要么是0要么是1。
因为位图的每一个元素只有2个值，一般可以用来判断一个数是否出现过这种简单的布尔值是或否的问题。
如何实现一个位图？因为我们的数字都是32或64bit的，所以需要借助真实的数字来实现bitmap。现在设一个数字是32个bit，现在有一个长度位10的数组，这个数组可以用来表示长度为320的bit类型的数组，然后通过位运算去实现从bit数组里面取值
复制代码
const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
let i = 199 //想要获取bit数组里第199个元素的值
let numIndex = Math.floor(i / 32) //找到arr里的对应的元素
let bitIndex = i % 32 //找到对应元素里的位数
let value = (arr[numIndex] >> bitIndex) & 1 //获取第199位的值
复制代码
对bitarray进行赋值操作
arr[numIndex] = arr[numIndex] | (1 << bitIndex) //将第199位变成1
arr[numIndex] = arr[numIndex] & (~(1 << bitIndex)) //将199位变成0
实现BitMap类
代码、案例如下
复制代码
class BitMap {
constructor(size) {
this.size = Math.ceil(size / 32)
this.bitArray = new Array(this.size).fill(0)
}
getNumber(num) {
//获取位数
let numIndex = Math.floor(num / 32)
let bitIndex = num % 32
return (this.bitArray[numIndex] >> bitIndex) & 1
}
isExist(num) {
//判断一个数是否存在
let value = this.getNumber(num)
return value == 1
}
addNumber(num) {
//添加一个数
let numIndex = Math.floor(num / 32)
let bitIndex = num % 32
this.bitArray[numIndex] = this.bitArray[numIndex] | (1 << bitIndex)
}