简介
说明
本文介绍Redis的布谷鸟过滤器的原理，优缺点，使用场景，实例。
布谷鸟过滤器起源
布谷鸟算法的启发来自于布谷鸟，因为布谷鸟这种鸟很有意思，生出来的孩子自己不养，直接把孩子扔到其他鸟的鸟巢中去了。但有时候，这些布谷鸟蛋会被被寄宿的鸟妈妈发现，然后就被抛弃；有时候，这些宿主会直接放弃整个鸟巢寻找新住处。然而道高一尺魔高一丈，有些品种的布谷鸟生下来的布谷鸟蛋的颜色和被寄宿的鸟的鸟蛋颜色很像，并且布谷鸟的破壳时间往往比宿主的鸟蛋早，小布谷鸟破壳后会将一些鸟蛋扔出鸟巢以获得更多的食物，小布谷鸟还能模拟宿主鸟孩子的叫声来骗取更多的食物！简单来说，就是如何更高效地去骗吃骗喝。
布谷鸟哈希
原理
最简单的布谷鸟哈希结构是一维数组结构，会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空，那么就可以将元素直接放进去。但是如果这两个位置都满了，它就不得不「鸠占鹊巢」，随机踢走一个，然后自己霸占了这个位置。
最原始的布谷鸟哈希采用以下步骤来解决哈希冲突：
- 对输入的Key使用两个Hash函数，得到桶中的两个位置。
- 如果两个位置都为空，就把Key随机选择一个位置放入。
- 如果两个位置只有一个为空，就把Key放入到这个空的位置。
- 如果两个位置都不为空，则随机踢出一个元素「鸠占鹊巢」，自己霸占这个位置，踢出的元素再重新计算哈希找到相应的位置。
1. 保存元素 （位置都没有被占）
新来的元素a经过hash会落在（A2，B1）的位置，由于A2还没有元素，a直接落入A2
2. 保存元素 （其中一个位置被占）
新插入元素b的hash会落在(A2,B3),由于A2已经被a占了，所以b会落在b3
3. 保存元素 （两个位置都被占）
新来元素c的hash为(A2,B3), 由于两个位置都已经被占，它会随机将一个元素挤走，这里挤走了a
4. 被挤掉的元素重新找位置
a会重新进行hash，找到还未被占的B1位置
如果这个位置也被别人占了呢？好，那么它也会再来一次「鸠占鹊巢」，把别人赶走。然后这个新的受害者还会重复这个过程直到所有的蛋都找到了自己的巢为止。
问题
如果数组太拥挤了，连续踢来踢去几百次还没有停下来，这时候会严重影响插入效率。这时候布谷鸟哈希会设置一个阈值，当连续占巢行为超出了某个阈值，就认为这个数组已经几乎满了。这时候就需要对它进行扩容，重新放置所有元素。
还会有另一个问题，那就是可能会存在挤兑循环。比如两个不同的元素，hash 之后的两个位置正好相同，这时候它们一人一个位置没有问题。但是这时候来了第三个元素，它 hash 之后的位置也和它们一样，很明显，这时候会出现挤兑的循环。不过让三个不同的元素经过两次 hash 后位置还一样，这样的概率并不是很高，除非你的 hash 算法太挫了。
出现挤兑循环时，布谷鸟过滤器认为数组太拥挤了，会进行扩容，重新计算每个指纹的位置。
布谷鸟过滤器
原理简介
布谷鸟过滤器由一个数组组成，数组中每个元素大小为4个字节，可以存储4个指纹，每个指纹占一个字节(2^8 = 256种)。这样有以下两个好处：
- 避免出现hash后的位置一致而导致的循环挤兑的情况。
- 这样即使两个元素被 hash 在了同一个位置，也不必立即「鸠占鹊巢」，因为这里有4个座位，你可以随意坐一个。除非这多个座位都被占了，才需要进行挤兑。这会显著降低挤兑次数。
- 同一个位置上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。
插入
初始化一个给定容量的过滤器Filter，这个容量数为2的n次方，如果不为2的n次方，内部会通将其转化为2的n次方。
先进行一次hash，得出应当插入位置和应当插入的值。如果这个这个位置（bucket内的4个位置均被占用）插入失败，会进行第二次hash，查看第二个位置能否插入。若第二个位置插入失败，则会随机在两个位置挑选一个将其中的一个值标记为旧值，用新值覆盖旧值，旧值会在重复上面的步骤进行插入。
会对插入的值进行校验，只有当未插入过该值时才会插入成功，若过滤器中已经存在该值，会插入失败返回false。
扩容
如果数组过小，会发生循环挤兑的情况，如果超过最大挤兑次数，进行扩容，重新计算每个指纹的位置。
查找
用两个hash函数计算，将计算结果与两个元素中的8个位置的指纹进行对比，如果对比成功则表示数据存在。先进行一次hash查询数据，若没有该值会进行第二次hash进行查询，若还是没有会返回false。
删除
通过两次hash找到索引位置，若有该数据，将该位置数据删除。因为每个对象的指纹会存储到一个位置中，所以可以通过删除这个指纹来删除数据。
删除功能无法使用的情况：如果相同对象存储超过8个，就无法使用删除功能；如果俩数据的哈希值和指纹相同时，会出现误删除情况。
删除全部
布谷鸟过滤器可以删除全部元素（重置数组为0）。
更新
删除后再添加新指纹。
原理详述
布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器），过滤器牺牲了数据的精确性换取了空间效率。
布谷鸟过滤器还是只会选用两个 hash 函数，但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊，因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后，它需要计算出另一个对偶位置，计算这个对偶位置是需要元素本身的。
哈希位置计算公式：
fp = fingerprint(x) p1 = hash1(x) % l p2 = hash2(x) % l
知道了 p1 和 x 的指纹，是没办法直接计算出 p2 的。
布谷鸟过滤器
一个独特的 hash 函数，可以根据 p1 和 元素指纹 直接计算出 p2，而不需要完整的 x 元素。
fp = fingerprint(x) p1 = hash(x) p2 = p1 ^ hash(fp) // 异或
从上面的公式中可以看出，知道 fp 和 p1，可以算出 p2。同样如果我们知道 p2 和 fp，也可以直接算出 p1 —— 对偶性。
p1 = p2 ^ hash(fp)
所以不需要知道当前的位置是 p1 还是 p2，只需要将当前的位置和 hash(fp) 进行异或计算就可以得到对偶位置。只需要确保 hash(fp) != 0 就可以确保 p1 != p2，就不会出现自己踢自己导致死循环的问题。
为什么这里的 hash 函数不需要对数组的长度取模呢？实际上是需要的，但是布谷鸟过滤器强制数组的长度必须是 2 的指数，所以对数组的长度取模等价于取 hash 值的最后 n 位。在进行异或运算时，忽略掉低 n 位 之外的其它位就行。将计算出来的位置 p 保留低 n 位就是最终的对偶位置。
优缺点
优点
- 支持新增和删除元素。
- 布隆过滤器不支持删除元素
- 更节省空间。
- 布谷鸟哈希表更加紧凑
- 布谷鸟过滤器在错误率小于3%的时候空间性能是优于布隆过滤器
- 布谷鸟过滤器比布隆过滤器空间节省40%多
- 查询效率很高
- 布谷鸟过滤器只需一次哈希
- 布隆过滤器要采用多种哈希函数进行多次哈希
缺点
- 插入性能较差
- 布谷鸟过滤器在计算哈希后可能当前位置上已经存储了指纹，这时就要将已存储的项踢到候选桶，随着桶越来越满，产生冲突的可能性越来越大，插入耗时越来越高
- 布隆过滤器插入时计算好哈希直接写入位即可
- 插入重复元素存在上限
- 布谷鸟过滤器对已存在的值会做踢出操作，因此重复元素的插入存在上限。
- 布隆过滤器在插入重复元素时并没有影响，只是对已存在的位再置一遍。
- 空间大小
- 布谷鸟过滤器必须是2的指数。
- 布隆过滤器不需要是2的指数。
- 删除问题
- 有上述重复插入的限制，删除时也会出现相关的问题：
- 删除仅在相同哈希值被插入一次时是完美的
- 如果元素没有插入便进行删除，可能会出现误删除，这和假阳性率的原因相同
- 如果元素插入了多次，那么每次删除仅会删除一个值，你需要知道元素插入了多少次才能删除干净，或者循环运行删除直到删除失败为止
- 有上述重复插入的限制，删除时也会出现相关的问题：
代码实现
Redis布谷鸟过滤器
Redis布谷鸟过滤器：https://github.com/kristoff-it/redis-cuckoofilter
Redis通过插件支持sql及布谷鸟过滤器：https://github.com/RedBeardLab/rediSQL
Java布谷鸟过滤器
import java.util.Random;
public class CuckooFilter {
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 最大的踢出次数
private final int MAX_NUM_KICKS = 500;
// 桶的个数
private int capacity;
// 存入元素个数
private int size = 0;
// 存放桶的数组
private Bucket[] buckets;
private Random random;
public CuckooFilter(int capacity) {
capacity = tableSizeFor(capacity);
this.capacity = capacity;
buckets = new Bucket[capacity];
random = new Random();
for (int i = 0; i < capacity; i++) {
buckets[i] = new Bucket();
}
}
/**
* 向布谷鸟过滤器中插入一个元素
*
* @return true：插入成功。false：过滤器已满或插入数据为空，返回false
*/
public boolean insert(Object o) {
if (o == null) {
return false;
}
byte f = fingerprint(o);
int i1 = hash(o);
int i2 = i1 ^ hash(f);
if (buckets[i1].insert(f) || buckets[i2].insert(f)) {
// 有空位置
size++;
return true;// 插入成功
}
// 没有空位置，relocate再插入
return relocateAndInsert(i1, i2, f);
}
/**
* 对插入的值进行校验，只有当未插入过该值时才会插入成功
* 若过滤器中已经存在该值，会插入失败返回false
*/
public boolean insertUnique(Object o) {
if (o == null || contains(o)) {
return false;
}
return insert(o);
}
/**
* 随机在两个位置挑选一个将其中的一个值标记为旧值，
* 用新值覆盖旧值，旧值会在重复上面的步骤进行插入
*/
private boolean relocateAndInsert(int i1, int i2, byte f) {
boolean flag = random.nextBoolean();
int itemp = flag ? i1 : i2;
for (int i = 0; i < MAX_NUM_KICKS; i++) {
// 在桶中随机找一个位置
int position = random.nextInt(Bucket.BUCKET_SIZE);
// 踢出
f = buckets[itemp].swap(position, f);
itemp = itemp ^ hash(f);
if (buckets[itemp].insert(f)) {
size++;
return true;
}
}
// 超过最大踢出次数，插入失败
return false;
}
/**
* 如果此过滤器包含对象的指纹，返回true
*/
public boolean contains(Object o) {
if (o == null) {
return false;
}
byte f = fingerprint(o);
int i1 = hash(o);
int i2 = i1 ^ hash(f);
return buckets[i1].contains(f) || buckets[i2].contains(f);
}
/**
* 从布谷鸟过滤器中删除元素
* 为了安全地删除，此元素之前必须被插入过
*/
public boolean delete(Object o) {
if (o == null) {
return false;
}
byte f = fingerprint(o);
int i1 = hash(o);
int i2 = i1 ^ hash(f);
return buckets[i1].delete(f) || buckets[i2].delete(f);
}
/**
* 过滤器中元素个数
*/
public int size() {
return size;
}
/**
* 过滤器是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 得到指纹
*/
private byte fingerprint(Object o) {
int h = o.hashCode();
h += ~(h << 15);
h ^= (h >> 10);
h += (h << 3);
h ^= (h >> 6);
h += ~(h << 11);
h ^= (h >> 16);
byte hash = (byte) h;
if (hash == Bucket.NULL_FINGERPRINT)
hash = 40;
return hash;
}
/**
* 哈希函数
*/
public int hash(Object key) {
int h = key.hashCode();
h -= (h << 6);
h ^= (h >> 17);
h -= (h << 9);
h ^= (h << 4);
h -= (h << 3);
h ^= (h << 10);
h ^= (h >> 15);
return h & (capacity - 1);
}
/**
* hashMap的源码 有一个tableSizeFor的方法，目的是将传进来的参数转变为2的n次方的数值
*/
static int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
static class Bucket {
public static final int FINGERPINT_SIZE = 1;
// 桶大小为4
public static final int BUCKET_SIZE = 4;
public static final byte NULL_FINGERPRINT = 0;
private final byte[] fps = new byte[BUCKET_SIZE];
/**
* 在桶中插入
*/
public boolean insert(byte fingerprint) {
for (int i = 0; i < fps.length; i++) {
if (fps[i] == NULL_FINGERPRINT) {
fps[i] = fingerprint;
return true;
}
}
return false;
}
/**
* 在桶中删除
*/
public boolean delete(byte fingerprint) {
for (int i = 0; i < fps.length; i++) {
if (fps[i] == fingerprint) {
fps[i] = NULL_FINGERPRINT;
return true;
}
}
return false;
}
/**
* 桶中是否含此指纹
*/
public boolean contains(byte fingerprint) {
for (byte fp : fps) {
if (fp == fingerprint) {
return true;
}
}
return false;
}
public byte swap(int position, byte fingerprint) {
byte tmpfg = fps[position];
fps[position] = fingerprint;
return tmpfg;
}
}
}
请先 ！