如果你读过Shadowsocks或者Angular的代码,你会发现他里面都自己实现了一个布隆过滤器。
SS用他来匹配GFW名单,Angular中用来依赖注入服务名单。NodeInjector是Ivy渲染器引入的Angular注入器,它大量使用bloom过滤器来检索令牌。

Bloom过滤器的基本数据结构是位向量。

Bloom Filter原理:当一个元素被加入集合时,通过K个Hash函数将这个元素映射成一个位阵列(Bit array)中的K个点,把它们置为1。检索时,我们只要看看这些点是不是都是1就(大约)知道集合中有没有它了:如果这些点有任何一个0,则被检索元素一定不在;如果都是1,则被检索元素很可能在。

Angular中的bloom比特位为256,因此我们有一个256位的向量,它被分成8个部分。

Angular 通过递增整数值生成(如果尚未定义)令牌的唯一ID,并将其置于静态__NG_ELEMENT_ID__属性。
它通过按位AND(&)运算符获取该数字并使其适合bloom大小,以便结果始终在0-255之间。

// 用原始 bloomBit 值决定检查那个 bloom 过滤器桶
// e.g: bf0 = [0 - 31], bf1 = [32 - 63], bf2 = [64 - 95], bf3 = [96 - 127], etc
const b7 = bloomBit & 0x80;
const b6 = bloomBit & 0x40;
const b5 = bloomBit & 0x20;
const tData = tView.data as number[];

if (b7) {
  b6 ? (b5 ? (tData[injectorIndex + 7] |= mask) : (tData[injectorIndex + 6] |= mask)) :
       (b5 ? (tData[injectorIndex + 5] |= mask) : (tData[injectorIndex + 4] |= mask));
} else {
  b6 ? (b5 ? (tData[injectorIndex + 3] |= mask) : (tData[injectorIndex + 2] |= mask)) :
       (b5 ? (tData[injectorIndex + 1] |= mask) : (tData[injectorIndex] |= mask));
}

代码都是位运算,看起来挺复杂,其实就是将2^bloomBit位置为1。下面是一个简单例子:

const bloomBit = 3 % 255 // 3
const mask = 1 << bloomBit;
             1 << 3 // 8
8..toString(2) // 1000
                           
1 bucket          00000000000000000000000000001000
....
8 bucket          00000000000000000000000000000000