Xor过滤器的实现是基于完美哈希函数的。所谓完美哈希函数，是指\(h(x)=y\)中，对于任意\(x\)，都不会算出来相同的两个y。比如\(h(x)=x+10\)是完美哈希函数，\(h(x)=x^{2}\)不是，因为\(h(1)=h(-1)\)。而此处使用的完美哈希函数，是使用超图分解实现的。
构建
一个xor过滤器需要确定3个位置哈希函数\(h={h0,h1,h2}\)，和1个fingerprint函数\(f(x)\)。h(x)的范围是分配的数组大小，而fingerprint是一个二进制整数，所以范围是二进制整数的长度决定的，例子假定整数长度为2。构建过程分别有插入到哈希表、超图分解、分配slot这3个步骤，它们在论文中描述的足够清楚了，所以此处只展示伪代码
所谓超图，指的是一个边可以包含多个点。
现在假定有这些键：
keyh0h1h2f\(x\)01211\(y\)12310\(z\)23401插入x,y,z到H
此时得到H为：
01234\(x\)\(x,y\)\(x,y,z\)\(y,z\)\(z\)超图分解
插入\(x,y,z\)后得到的超图是
此时黑色边包含了0,1,2三个点，红色边包含了1,2,3三个点，蓝色边包含了2,3,4三个点。
一个超边的度是由一个点所在的边的数量确定的。图中0的度是1，1的度是2，2的度是3，3的度是2，4的度是1。
超图分解，就是先将度为1的点分配给一个键，然后删除这个点和它所在的边。
比如上面的超图，0和4的度是1，删除它们和它们所在的边，并将0分配给x，4分配给z，然后在H中删除x、z的记录，并将x,z分配的点记录在栈中
01234\(y\)\(y\)\(y\)stack: {x:0}, {z:4}
此时又出现了度为1的点，随便挑一个删除就行。
\[超图已经是空图了\]
01234stack: {x:0}, {z:4}, {y:1}
分配slot
由于是按照栈的顺序分配的，所以先分配y，即B[1]=B[1] xor B[2] xor B[3] xor f(y)=10
012340010000000由于是按照栈的顺序分配的，再先分配z，即B[5]=B[2] xor B[3] xor B[4] xor f(z)=01
012340010000001由于是按照栈的顺序分配的，再先分配x，即B[0]=B[0] xor B[1] xor B[2] xor f(z)=01
012340110000001查询
查询x即检查B[0] xor B[1] xor B[2] == f(x)，得到11，查询正确。假阴性是不可能的，因为一个已经存在的键一定会映射到插入过程中选择的3个位置，这样一异或就是f(x)的值了，这得益于栈的分配顺序。假阳性可能存在，概率是fingerprint的长度决定的，长度如果为b，那么概率为\(2^{-b}\)
如果使用队列的分配顺序来构建？
由于是按照队列的顺序分配的，先分配x，即B[0]=B[0] xor B[1] xor B[2] xor f(z)=11
012341100000000由于是按照队列的顺序分配的，再分配z，即B[4]=B[2] xor B[3] xor B[4] xor f(z)=01
012341110000001由于是按照队列的顺序分配的，再分配y，即B[1]=B[1] xor B[2] xor B[3] xor f(y)=01
012341101000001此时查询x，得到的是10，出现了假阴性。回过头看原因，发现是x依赖的另外两个位置被篡改了，所以出现了这个问题。
优化
10bit数组
如果使用紧凑的10bit数组，那么它在内存中表示为：
需要几次除法运算，由于没有对齐，读写一次数据也可能需要两次总线访问，再加上它跨 cache line 的概率较高，所以其效率较低。若要考虑优化总线访问次数，那么实现断然复杂。图中 10 字节中有 8 个10bit 元素跨了字节，可以计算随机访问一个 10bit 元素导致跨 cache line 的概率是 1.25%。
有一种 10bit 数组，可以减少位运算，并且避免跨 cache line 存储，但是浪费了部分空间，即用 64bit 来表示 6 个 10bit 元素。这种做法固有的空间浪费率是 6.25%。这种浪费确实提升了查询性能，数组随机访问耗时从 9.13ns 降低到 6.47ns。- Array10Bit.Create(length)
- 说明：10bit 数组的构建函数
- 输入：length: 数组中的元素数量
- 输出：uint64 数组
- 1: n ← ⌈length / 6⌉
- 2: return 长度为 n 的数组，每个元素都是 uint64，初始化为 0
- Array10Bit.Set(array, index, value)
- 说明：设置 10bit 数组中 index 位置为 value。注意这里假定待设置处值为 0
- 输入：array: 传入传出参数，Create 创建的数组
- index: 仅传入参数，待设置的位置
- value: 仅传入参数，待设置的值
- 输出：无
- 1: shift ← 3 * (index mod 2) + (index mod 3)
- 2: array[index / 6] = array[index / 6] | (uint64)value << (10 * shift)
- Array10Bit.Get(array, index)
- 说明：返回 10bit 数组中 index 位置的值
- 输入：array: 传入传出参数，Create 创建的数组
- index: 仅传入参数，待设置的位置
- 1: shift ← 3 * (index mod 2) + (index mod 3)
- 2: return (array[index / 6] >> (10 * shift)) & 3ff
mod3=0mod3=1mod3=2mod2=0shift=0shift=1shift=2mod2=1shift=3shift=4shift=5index在0到10，shift取值分别是：
01234567891004231504231可以发现，index每6个一组，每一组都可以均匀的分配到唯一的一个10bit数字
哈希函数
我们可以用一种范围哈希函数来替代取模的哈希函数- FastRange32 (uint32 v, uint32 n)
- 说明：一种哈希函数
- 输入：v: 仅传入参数，v 待哈希的值
- n: 返回值的范围
- 输出：[0, n)范围内的一个整数
- 1: return (uint32)(((uint64)v * n) >> 32)
\[[0,2^{32})*n/2^{32}=2^{32}*[0,1)*n/2^{32}=[0,1)*n\]
至于值分布规律，举几个例子就可以说明白了。
\[v\in[0,\frac{2^{32}}{n}), fastrange(v, n) = [0,\frac{2^{32}}{n})*n/2^{32} = [0,1)=0\]
\[v\in[\frac{2^{32}}{n},\frac{2*2^{32}}{n}), fastrange(v, n) = [\frac{2^{32}}{n},\frac{2*2^{32}}{n})*n/2^{32} = [1,2)=1\]
\[v\in[\frac{2*2^{32}}{n},\frac{3*2^{32}}{n}), fastrange(v, n) = [\frac{2*2^{32}}{n},\frac{3*2^{32}}{n})*n/2^{32} = [2,3)=2\]
空间消耗
当插入键的数量为t时，很容易发现如果分配的数组大小小于t+2，那么根本就无法完成构建。
在一篇论文中，有人证明如果分配的数组是1.23t，那么构建成功率接近100%。
性能测试结果
分别使用fingerprint大小为8、10、12、16进行测试。图中横坐标的意思是:
\[查询已经插入到过滤器中的键的数量/查询次数 \]
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
千斤顶
照妖镜
