【知识点随笔分析 | 第八篇】什么是布谷鸟过滤器（缓解Redis穿透）
前言在昨天我们介绍了什么是布隆过滤器，而信赖如果了解布隆过滤器的朋友应该都知道，布隆过滤器虽然可以办理Redis的穿透问题，但是由于它自身特性，布隆过滤器也是存在不少的缺点，例如随着哈希函数的增多大概哈希函数散列范围的增加，会造成一定程度的空间浪费；并且布隆过滤器是无法实现删除操作的。因此我们今天来介绍一种新的过滤器：布谷鸟过滤器
【从零开始学习Redis | 第五篇】基于布隆过滤器办理Redis的穿透问题-CSDN博客https://i-blog.csdnimg.cn/blog_migrate/003a2ce7eb50c2e24a8c624c260c5930.pnghttps://blog.csdn.net/fckbb/article/details/134226419?spm=1001.2014.3001.5501
目录
前言
引入：
布谷鸟哈希结构：
挤占循环 ：
布谷鸟过滤器：
布谷鸟过滤器的插入：
布谷鸟过滤器的删除：
布隆过滤器的查找：
基于Java实现布谷鸟过滤器：
总结：
https://i-blog.csdnimg.cn/blog_migrate/7a2b38ca83c2f5ce638c3dd4261c9940.png
引入：
在中国有一个成语，叫做鸠占鹊巢，字面意思就是说：鸠这种动物，从来不会自己搭建巢穴，在下蛋的时候就会把蛋下到鹊的巢穴里，挤占鹊的蛋的生存空间。而鸠就是布谷鸟，布谷鸟过滤器的思想就是挤占
布谷鸟过滤器的底层用的是布谷鸟哈希结构。 因此我们先来介绍一下布谷鸟哈希结构
布谷鸟哈希结构：
布谷鸟哈希结构本质上是为了办理哈希冲突，所以我们先来介绍一下什么是哈希冲突：
哈希冲突指的是在哈希函数盘算过程中，不同的输入值得到了相同的哈希值的环境。由于哈希函数将输入映射到有限的输出空间，而输入的范围通常是无限的，所以哈希冲突是不可避免的。
而最原始的布谷鸟哈希结构接纳以下步调来办理哈希冲突：
[*]对输入的Key使用两个Hash函数，得到桶中的两个位置
[*]如果两个位置都为空，就把Key随机选择一个位置放入
[*]如果两个位置只有一个为空，就把Key放入到这个空的位置
[*]如果两个位置都不为空，则随机踢出一个元素，踢出的元素再重新盘算哈希找到相应的位置
其实如许说可能照旧有点含糊，所以我们搭配图片来分析一下：
第一次插入元素：插入"张三"，经过哈希后得到两个位置：3和5，选择位置3举行插入
https://i-blog.csdnimg.cn/blog_migrate/2861bc326b7e7d6bfce297bfabddbddf.png
第二次插入元素 : 插入"赵四"，经过哈希后，得到两个位置3和4，选择位置3举行插入
https://i-blog.csdnimg.cn/blog_migrate/96444fcb373b1aba0ccfe828f8be11d5.png
而此时当“赵四”想要插入位置3的时候，就会发生挤占，将"张三"从原位置挤占出去了
https://i-blog.csdnimg.cn/blog_migrate/976a372cb27eab8882caae8e944919ca.png
此时就要重新为张三举行hash，得到位置3和5 选择位置5举行插入。
https://i-blog.csdnimg.cn/blog_migrate/70886a6688054a1926bd69c9b57f1f62.png 而在这种环境下，我们就完成了一次"挤占"的过程 。并且为被挤占的元素重新安排了位置
挤占循环 ：
如果发生挤占循环怎么办？也就是说：当重新为张三举行hash后，我们没有选择位置5，而是选择了位置3，此时就又会把“赵四”挤占出去了，而重新为“赵四”举行Hash的时候，赵四又选择了位置3，再次把“张三”挤占出去，此时“张三”又要重新举行Hash，无限循环这种环境..........
大概是不同数据之间的相互挤占，也就是A数据的插入挤占出了B数据，B数据的插入挤占出了C数据，C数据的插入挤占了D数据，如许不停的循环
而挤占循环这种问题，是没有办法真正办理的，我们能做的只有尽量克制挤占循环，有如下思路：
[*]设置最大挤占次数，如果达到最大挤占次数后，分析空间不敷用了，要举行桶的扩容操作。
[*]设置更多的哈希函数，使得一个Key有更多的位置可以选择。
而通过这两种方法，其实就可以很好的控制循环挤占的问题
而我们单独讲一下桶的扩容操作，由于桶可以使我们自己定义的数据结构，因此我们可以把让一个位置存储多个元素，类似二维数组的形式，我们来看一下代码：
type bucket byte // 一个桶，4个座位I
type cuckoo_filter struct [
buckets bucket // 一维数组
nums int // 容纳的元素的个数
kick_max // 最大挤兑次数
} 如图所示
https://i-blog.csdnimg.cn/blog_migrate/ad53cb1e472a11e548e5db66f9c2803d.png
如许我们就使得一个桶中可以存储四个数据，而此时的赵四只占用了一个位置，在同一个哈希映射坐标中，我们还可以存储三个。
注意：这里的位置是连续的。并不是有些人想的链表结构
而且根据相干文献研究，通过不停对桶举行扩容，我们可以大大进步桶的利用效率
https://i-blog.csdnimg.cn/blog_migrate/04728a512424ddd4257029803d75738b.png
文献指出，当桶的大小达到4的时候，我们整个桶数组的利用效率就达到了95%，这是我们使用布隆过滤器难以达到的
相干文献链接：
cuckoo-conext2014.pdf (cmu.edu)https://i-blog.csdnimg.cn/blog_migrate/003a2ce7eb50c2e24a8c624c260c5930.pnghttps://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
布谷鸟过滤器：
布谷鸟过滤器的基础就是布谷鸟哈希结构。
而它与布谷鸟哈希结构的区别就在于：我们在使用布谷鸟过滤器的时候，并不会像布谷鸟哈希结构一样，必要存储具体的信息。由于整个过滤器的作用只是证明当前元素是否可能存在，因此我们必要把可以证明这个元素的关键信息放进去就可以了
而我们给出的答案就是：指纹
指纹指的是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置
也就是说，我们把指纹存储到对应元素的举行哈希后所映射出来的坐标位置就好了。
但其实在这里我们就可以明确：布谷鸟过滤器的思维和布隆过滤器的底层照旧一样的，只不过是在优化布隆过滤器的数据结构。
而布隆过滤器的底层问题：可能存在误判。这个问题布谷鸟一样也避不开。
我们可以假设指纹是一个八位的二进制数字。那最多也就只有255种不同的指纹，也就是说一定会出现两个不同的元素但是指纹相同的问题，也就是误判问题。
布谷鸟过滤器的插入：
我们来看一下布谷鸟过滤器是如何插入元素的:
public void insert(int item) {
//如果包含这个数据就返回，不做重复插入
if (contains(item)) {
return;
}
//如果表总长已经达到最大程度就进行扩容
if (numItems >= table.length) {
resizeTable();
}
//进行Hash得到位置
int hash = hashItem(item);
//计算该数据的指纹
int fingerprint = getFingerprint(item);
//进入循环，MAX_KICK_ATTEMPTS是最大挤占次数
for (int i = 0; i < MAX_KICK_ATTEMPTS; i++) {
//如果当前位置为空
if (table == -1) {
//存储当前数据的指纹
table = fingerprint;
numItems++;
return;
}
//如果当前位置不为空
else {
//用temp存储原数据的指纹
int temp = table;
//存储当前数据的指纹(挤占原指纹)
table = fingerprint;
//用fingerprint来存储原数字指纹
fingerprint = temp;
//此处的hashItem是一个哈希函数，我们把fingerprint输入进去得到新的hash坐标
//也就是说，此时我们得到了一个新的坐标和原数据指纹，进行新一轮的插入
hash = hashItem(fingerprint);
}
}
//结束循环，也就是说达到了最大的挤占次数，仍然有数据被挤占
//1，进行扩容
resizeTable();
//2.重新进行一次插入
insert(item);
} 插入处的看起来复杂，其实关键点就在于：我们的第二个Hash坐标是通过指纹来盘算出来的。
而在布谷鸟哈希结构，我们是直接使用两个Hash函数对同一个数据举行两次Hash，得到两个坐标。
布谷鸟过滤器之所以不接纳两个Hash，是由于我们的布谷鸟过滤器为了节省空间，存储的并不是原数据。如果我们使用原数据得到了两个Hash坐标，选择一个存入。那么我们在发生挤占之后，得到原数据的指纹，我们又要如何得到这个数据的另一个坐标呢？
也就是说在布谷鸟过滤器得到的两个坐标中：
第一个坐标是通过某个哈希函数盘算出来，第二个坐标是使用第一个坐标和指纹的哈希做了一个异或操作，举行异或操作的好处是:由于异或操作的特性: a^b = c ,c ^ b= a,c^a=b,我们可以快速的互推数据。换句话说，在桶中挤占一个数据，我们直接用当前桶的索引i和存储在桶中的指纹盘算它的备用桶。
而布谷鸟的插入也存在一个困难的问题：我们是否答应重复？
之所以说这个问题苦难，是由于我们在布谷鸟过滤器中判断是否可以重复插入的时候，是依靠指纹举行判断的，而指纹会存在误判环境，此时就分为两种环境：
如果我们答应重复插入:插入相同的数据，那么它的两个坐标就是相同的，我们假设有两个坐标，一个坐标里面有四个位置：
https://i-blog.csdnimg.cn/blog_migrate/ad53cb1e472a11e548e5db66f9c2803d.png
那么他最多就答应八个相同的元素插入，当我们插入第九个相同的元素的时候，就会发生挤占，而且这种挤占无法通过普通的扩容来办理，必要重新设置同一个坐标的位置个数，而不是简朴的增加数组长度，也就是对这里举行操作：
https://i-blog.csdnimg.cn/blog_migrate/84157ce9c97dae62b92eede56e1937de.png
而这种级别的扩容所带来的辐射是每一个坐标的，他会使得空间复杂度飙升。
而
如果我们不答应重复插入：那么此时就存在一个BUG了，指纹是可以重复的，而我们在判断是否是重复插入元素是通过指纹举行判断的，也就是说存在误判的环境。如许会导致部分数据无法正常插入布谷鸟过滤器。
布谷鸟过滤器的删除：
这也是布隆过滤器的最大缺点：布隆过滤器不可以删除元素，想要去除元素只能重构整个布隆过滤器，在现实业务中会对服务器造成较大压力。
而我们的布谷鸟过滤器只必要根据输入数据盘算得到指纹，找到指纹举行删除就可以了。
public void delete(int item) {
//计算Hash位置
int hash = hashItem(item);
//计算指纹
int fingerprint = getFingerprint(item);
if (table == fingerprint) {
//如果桶的hash位置是对应的指纹，直接删除
table = -1;
numItems--;
return;
} else {
//如果不是，就利用指纹计算另外一个备用位置
int altHash = hashItem(fingerprint);
//如果是对应的指纹就删除
if (table == fingerprint) {
table = -1;
numItems--;
return;
}
}
} 而就像我们前面说的一样：布谷鸟过滤器为了优化存储空间，牺牲了存储的精度。所谓的指纹也只不过是一串二进制数字。也就是说：指纹可能重复。布谷鸟过滤器也会出现误删的环境。
布隆过滤器的查找：
查找很简朴，通过指纹和Hash坐标去判断就可以了。
public boolean contains(int item) {
int hash = hashItem(item);
int fingerprint = getFingerprint(item);
if (table == fingerprint) {
return true;
} else {
int altHash = hashItem(fingerprint);
if (table == fingerprint) {
return true;
}
}
return false;
} 而这个查找一样存在误判。
而这些问题从指纹的设计模式上来讲，很难办理。我们只能通过不停的扩大指纹的字节数目大概提升盘算指纹的哈希函数来缓解这个问题。
不过布谷鸟过滤器确实实现了数据的删除，办理了布隆过滤器的缺点。
https://i-blog.csdnimg.cn/blog_migrate/6aa180a16b9b3755799664cfaed70e17.png
这是文献作者提供的数据统计，其实我们看出，当桶的座位为4的时候，其实就已经可以胜任大多数的 业务了。
末了再贴一下原文献的链接，如果大家感兴趣的话可以去看一看：
cuckoo-conext2014.pdf (cmu.edu)https://i-blog.csdnimg.cn/blog_migrate/003a2ce7eb50c2e24a8c624c260c5930.pnghttps://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
基于Java实现布谷鸟过滤器：
（这并不代表真正的布谷鸟过滤器，究竟上真正的布谷鸟过滤器的哈希函数设计困难的多，我只是贴出来一个简朴模仿的）
import java.util.BitSet;
import java.util.Random;
public class CuckooFilter {
private static final int MAX_KICKS = 500;
private BitSet[] buckets;
private int numBuckets;
private int bucketSize;
private int numItems;
public CuckooFilter(int numBuckets, int bucketSize) {
this.numBuckets = numBuckets;
this.bucketSize = bucketSize;
this.buckets = new BitSet;
for (int i = 0; i < numBuckets; i++) {
buckets = new BitSet(bucketSize);
}
this.numItems = 0;
}
public boolean contains(String item) {
int fingerprint = getFingerprint(item);
int bucket1 = getBucket(item);
int bucket2 = getAltBucket(bucket1, fingerprint);
return buckets.get(fingerprint) || buckets.get(fingerprint);
}
public void insert(String item) {
if (contains(item)) {
return;
}
int fingerprint = getFingerprint(item);
int bucket1 = getBucket(item);
int bucket2 = getAltBucket(bucket1, fingerprint);
if (buckets.cardinality() < bucketSize) {
buckets.set(fingerprint);
numItems++;
} else if (buckets.cardinality() < bucketSize) {
buckets.set(fingerprint);
numItems++;
} else {
Random random = new Random();
int bucket = random.nextBoolean() ? bucket1 : bucket2;
int i = 0;
while (i < MAX_KICKS) {
int evictedFingerprint = random.nextInt(bucketSize);
if (!buckets.get(evictedFingerprint)) {
buckets.set(evictedFingerprint);
String evictedItem = getItem(bucket, evictedFingerprint);
insert(evictedItem);
return;
}
i++;
}
rehash();
insert(item);
}
}
private int getFingerprint(String item) {
// 使用合适的哈希函数生成指纹
// 这里可以使用各种哈希算法，例如MurmurHash、SHA等
// 这里简化处理，直接使用String的hashCode方法
return item.hashCode();
}
private int getBucket(String item) {
// 使用合适的哈希函数生成桶索引
// 这里可以使用各种哈希算法，例如MurmurHash、SHA等
// 这里简化处理，直接使用String的hashCode方法
return Math.abs(item.hashCode()) % numBuckets;
}
private int getAltBucket(int bucket, int fingerprint) {
// 使用异或操作产生备选桶索引
return bucket ^ (fingerprint % numBuckets);
}
private String getItem(int bucket, int fingerprint) {
// 根据桶索引和指纹反推出之前插入的元素
// 这里简化处理，直接返回桶索引和指纹的拼接字符串
return bucket + ":" + fingerprint;
}
private void rehash() {
int newNumBuckets = numBuckets * 2;
BitSet[] newBuckets = new BitSet;
for (int i = 0; i < newNumBuckets; i++) {
newBuckets = new BitSet(bucketSize);
}
for (BitSet bucket : buckets) {
for (int i = 0; i < bucketSize; i++) {
if (bucket.get(i)) {
String item = getItem(buckets, i);
int newBucket = getBucket(item);
newBuckets.set(getFingerprint(item));
}
}
}
buckets = newBuckets;
numBuckets = newNumBuckets;
}
}
总结：
布谷鸟过滤器基于布谷鸟哈希结构，它使用指纹来标志每一个元素。布谷鸟过滤器办理了布隆过滤器不可以对内部数据举行删除的痛点。但由于其基于指纹的特性，可能会存在误判环境。
如果我的内容对你有资助，请点赞，批评，收藏。创作不易，大家的支持就是我对峙下去的动力！
https://i-blog.csdnimg.cn/blog_migrate/aec39448944ff3c852020dfa630db817.png
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]