数据结构-布隆过滤器和可逆布隆过滤器

ops/2024/11/19 1:52:37/

布隆过滤器家族

  • 普通布隆过滤器
    • 基本原理
    • 代码实现
  • 计数布隆过滤器
    • 基本原理
    • 代码实现
  • 可逆布隆过滤器
    • 基本原理
    • 代码实现
  • 参考

在解决缓存穿透问题时，往往会用到一种高效的数据结构-布隆过滤器，其能够快速过滤掉不存在的非法请求，但其也存在一定的误差，即少量不存在的请求也会被放过去。本文对布隆过滤器家族进行介绍，除了常见的普通布隆过滤器（Bloom Filters），还有计数布隆过滤器（Couting Bloom Filters）和可逆布隆过滤器（Invertible Bloom Filters）。

普通布隆过滤器

基本原理

普通的布隆过滤器原理就是基于位图和哈希函数，通过多个哈希函数依次将元素哈希到位图的某个位图的某个位置，然后将该位置的值赋值为1。如果要判断一个元素是否存在，也是一个哈希函数一个哈希函数来，然后看位图中的对应位置是否为1，如果为零，则说明该元素一定不存在，如果各个哈希函数对应位图中的位置都是1，只能说明该元素可能存在。可以看到，布隆过滤器可以过滤掉一定不存在的元素，但是对于去重任务存在一定的局限性。从概率上可以缓解这种局限性，一方面是增大位图的大小，另一方面是选用好的哈希函数，能够均匀地将各个元素哈希到位图的不同位置。此外，普通的布隆过滤器不能支持删除操作，也无法还原出原来的元素。

代码实现

首先定义一个过滤器的接口1，显然，对于普通的布隆过滤器无法支持后面两种操作。

type Filter[T Hashable] interface {Add(elem T)                  // 增加一个元素Search(elem T) bool          // 查找一个元素是否存在Delete(elem T) (bool, error) // 删除一个元素，成功则返回trueList() ([]T, error)          // 列出当前所有剩余元素
}

接着来看普通布隆过滤器实现代码

type BloomFilter[T Hashable] struct {bitMap []uint8size   uint64
}func NewBloomFilter[T Hashable](size uint64) Filter[T] {count := size >> 3if (size & 7) != 0 {count++}return &BloomFilter[T]{size: count << 3}
}func (f *BloomFilter[T]) Add(elem T) {if f.bitMap == nil {f.bitMap = make([]uint8, f.size>>3)}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizef.bitMap[(pos >> 3)] |= (1 << (pos & 7))}
}func (f *BloomFilter[T]) Search(elem T) bool {if f.bitMap == nil {return false}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizeif (f.bitMap[(pos>>3)] & (1 << (pos & 7))) == 0 {return false}}return true
}func (f *BloomFilter[T]) Delete(elem T) (bool, error) {return false, ErrFunctionUnSupported
}func (f *BloomFilter[T]) List() ([]T, error) {return nil, ErrFunctionUnSupported
}

单元测试代码如下

func TestBloomFilter(t *testing.T) {filter := NewBloomFilter[String](128)filter.Add(StringPacket("Alice"))filter.Add(StringPacket("Bob"))filter.Add(StringPacket("Clone"))filter.Add(StringPacket("Dawe"))filter.Add(StringPacket("Eleps"))ret := filter.Search(StringPacket("Dawe"))Assert(t, true, ret, "BloomFilter(Dawe)")ret = filter.Search(StringPacket("Helen"))Assert(t, false, ret, "BloomFilter(Helen)")}

测试截图如下：
在这里插入图片描述

计数布隆过滤器

基本原理

为了解决普通布隆过滤器无法解决删除元素的问题，计数布隆过滤器被提出来。正如其名，这个时候每一个位置上不再是一个比特位，而是一个计数器，用一个整数来记录哈希到这个位置的次数。这样，在删除的时候，也可以用每一个哈希函数依次哈希，将对应位置减一即可，在增加一个元素的时候，则是将哈希到的位置的值加一。这样就支持了删除操作，但其实还有误删的情况，因为没有办法确定一个元素是否在布隆过滤器中。而且这种方法有点背离了布隆过滤器的初衷——以极少的内存空间判断海量数据是否存在的问题。

代码实现

首先看计数布隆过滤器的实现

type CountBloomFilter[T Hashable] struct {bitMap []uint64size   uint64
}func NewCountBloomFilter[T Hashable](size uint64) Filter[T] {return &CountBloomFilter[T]{size: size}
}func (f *CountBloomFilter[T]) Add(elem T) {if f.bitMap == nil {f.bitMap = make([]uint64, f.size)}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizef.bitMap[pos]++}
}func (f *CountBloomFilter[T]) Search(elem T) bool {if f.bitMap == nil {return false}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizeif (f.bitMap[pos]) == 0 {return false}}return true
}func (f *CountBloomFilter[T]) Delete(elem T) (bool, error) {if !f.Search(elem) {return false, nil}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizef.bitMap[pos]--}return true, nil
}func (f *CountBloomFilter[T]) List() ([]T, error) {return nil, ErrFunctionUnSupported
}

单元测试代码实现如下：

func TestCountBloomFilter(t *testing.T) {filter := NewCountBloomFilter[String](128)filter.Add(StringPacket("Alice"))filter.Add(StringPacket("Bob"))filter.Add(StringPacket("Clone"))filter.Add(StringPacket("Dawe"))filter.Add(StringPacket("Eleps"))ret := filter.Search(StringPacket("Dawe"))Assert(t, true, ret, "BloomFilter(Search)")ret, err := filter.Delete(StringPacket("Dawe"))Assert(t, true, ret, "BloomFilter(Delete Dawe)")AssertNil(t, err, "BloomFilter(Delete Dawe)")ret = filter.Search(StringPacket("Dawe"))Assert(t, false, ret, "BloomFilter(Search)")
}

测试截图如下
在这里插入图片描述

可逆布隆过滤器

基本原理

而可逆布隆过滤器则是在计数布隆过滤器的基础上，引入更多的数据结构来实现可逆，即能够从过滤器中还原出原来的数据。具体的思路如下，定义一个数据范围0~n，一个哈希函数g用于将[0, n]的数据放缩到[0, n^2]，定义另外两个哈希函数f1和f2，用于将[0, n]的数据哈希到范围[0, m]，其中m为过滤器底层数组的大小，然后除了定义m大小的count外，还定义一个数组idSum，对应每个位置是已加入且哈希落到该点所有元素之和，以及数组hashSum,类似于idSum，只不过取得是每一个元素经过g哈希的结果之和。此外，还要维护一组这样的数据，这不过其哈希函数使用上文定义的f1和f2。具体可以参考代码实现。在列出所有原元素时，是通过不断寻找纯cell的方式，纯cell就是数组中的一个点，且只有一个元素通过哈希会落到这一点，这样，就可以删除这个元素，然后继续找纯cell。如何去找纯cell，用这样的判断条件_g(int(tab[i].idSum / tab[i].count), N) == tab[i].hashSum / tab[i].count，首先如果一个cell是纯的，一定会满足这个等式，由于哈希函数g的随机性，所以从概率上讲，不是纯cell但是满足这个等式的概率是比较小的。

代码实现

type InvertibleBloomFilter struct {tabB []filterCelltabC []filterCellsize uint64count uint64
}func NewInvertibleBloomFilter(size uint64) Filter[Integer] {return &InvertibleBloomFilter{size: size}
}func (f *InvertibleBloomFilter) Add(elem Integer) {if f.tabB == nil {f.tabB = make([]filterCell, f.size)f.tabC = make([]filterCell, f.size)}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizef.tabB[pos].count++f.tabB[pos].idSum += uint64(elem.Depacket())f.tabB[pos].hashSum += _g(elem.Depacket(), N)}poses := make([]uint, 2)poses[0] = _f1(elem.Depacket(), uint(f.size))poses[1] = _f2(elem.Depacket(), uint(f.size))for _, pos := range poses {f.tabC[pos].count++f.tabC[pos].idSum += uint64(elem.Depacket())f.tabC[pos].hashSum += _g(elem.Depacket(), N)}f.count++
}func (f *InvertibleBloomFilter) Search(elem Integer) bool {if f.tabB == nil {return false}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizeif (f.tabB[pos].count) == 0 {return false}}return true
}func (f *InvertibleBloomFilter) Delete(elem Integer) (bool, error) {if !f.Search(elem) {return false, nil}elemHash := elem.Hash()for _, hash := range hashFuncs {hashBytes := hash(elemHash)hashVal := LE2Int64(hashBytes[:8])pos := hashVal % f.sizef.tabB[pos].count--f.tabB[pos].idSum -= uint64(elem.Depacket())f.tabB[pos].hashSum -= _g(elem.Depacket(), N)}poses := make([]uint, 2)poses[0] = _f1(elem.Depacket(), uint(f.size))poses[1] = _f2(elem.Depacket(), uint(f.size))for _, pos := range poses {f.tabC[pos].count--f.tabC[pos].idSum -= uint64(elem.Depacket())f.tabC[pos].hashSum -= _g(elem.Depacket(), N)}f.count--return true, nil
}func (f *InvertibleBloomFilter) List() ([]Integer, error) {res := make([]Integer, 0)var loopAndFind func(tab []filterCell) = func(tab []filterCell) {for {flag := falsefor i := uint64(0); i < f.size; i++ {if tab[i].count != 0 && _g(int(tab[i].idSum / tab[i].count), N) == tab[i].hashSum / tab[i].count {x := IntegerPacket(int(tab[i].idSum / tab[i].count))for j := uint64(0); j < tab[i].count; i++ {f.Delete(x)}flag = trueres = append(res, x)break}}if flag {break}}}loopAndFind(f.tabB)if f.count != 0 {loopAndFind(f.tabC)}for _, item := range res {f.Add(item)}return res, nil
}

单元测试代码如下：

func TestInvertibleBloomFilter(t *testing.T) {filter := NewInvertibleBloomFilter(128)filter.Add(IntegerPacket(123))filter.Add(IntegerPacket(89))filter.Add(IntegerPacket(34))filter.Add(IntegerPacket(123))ret := filter.Search(IntegerPacket(123))Assert(t, true, ret, "TestInvertibleBloomFilter(search 123)")ret, err := filter.Delete(IntegerPacket(89))Assert(t, true, ret, "TestInvertibleBloomFilter(delete 89)")AssertNil(t, err, "TestInvertibleBloomFilter(delete 89)")ret = filter.Search(IntegerPacket(89))Assert(t, false, ret, "TestInvertibleBloomFilter(search 89)")rets, err := filter.List()Assert(t, 3, len(rets), "TestInvertibleBloomFilter(List)")AssertNil(t, err, "TestInvertibleBloomFilter(List)")t.Logf("filter.List()=%+v", rets)
}

测试截图如下：
在这里插入图片描述

参考

  • Straggler Identification in Round-Trip Data Streams via Newton’s Identities and Invertible Bloom Filters

  1. 完整代码可以参考：gulc: golang语言实用工具库 ↩︎


http://www.ppmy.cn/ops/134831.html

相关文章

【网络】HTTP 协议

【网络】HTTP 协议

目录 基本概念基于 HTTP 的系统组成HTTP 的基本性质 HTTP 请求头 & 响应头HTTP 的请求方法HTTP 的返回码HTTP 的 CookieHTTP 缓存 Cache-Control会话HTTP/1.x 的连接管理 基本概念 HTTP&#xff08;Hypertext Transfer Protocol&#xff0c;超文本传输协议&#xff09;是一…
阅读更多...
ctfshow DSBCTF web部分wp

ctfshow DSBCTF web部分wp

ctfshow 单身杯 web部分wp web 签到好玩的PHP 源码&#xff1a; <?php error_reporting(0); highlight_file(__FILE__);class ctfshow {private $d ;private $s ;private $b ;private $ctf ;public function __destruct() {$this->d (string)$this->d;$this…
阅读更多...
【Golang】——Gin 框架中的模板渲染详解

【Golang】——Gin 框架中的模板渲染详解

Gin 框架支持动态网页开发&#xff0c;能够通过模板渲染结合数据生成动态页面。在这篇文章中&#xff0c;我们将一步步学习如何在 Gin 框架中配置模板、渲染动态数据&#xff0c;并结合静态资源文件创建一个功能完整的动态网站。 文章目录 1. 什么是模板渲染&#xff1f;1.1 概…
阅读更多...
Mac 使用mac 原生工具将mp4视频文件提取其中的 mp3 音频文件

Mac 使用mac 原生工具将mp4视频文件提取其中的 mp3 音频文件

简介 Hello！ 非常感谢您阅读海轰的文章，倘若文中有错误的地方，欢迎您指出～ ଘ(੭ˊᵕˋ)੭ 昵称：海轰 标签：程序猿｜C++选手｜学生 简介：因C语言结识编程，随后转入计算机专业，获得过国家奖学金，有幸在竞赛中拿过一些国奖、省奖…已保研 学习经验：扎实基础 + 多做笔…
阅读更多...
ChatDev本地部署教程

ChatDev本地部署教程

ChatDev本地部署教程 &#x1f4d6; 概述 ChatDev 是一家虚拟软件公司&#xff0c;通过各种不同角色的智能体 运营&#xff0c;包括执行官&#xff0c;产品官&#xff0c;技术官&#xff0c;程序员 &#xff0c;审查员&#xff0c;测试员&#xff0c;设计师 等。这些智能体形…
阅读更多...
「Mac玩转仓颉内测版14」PTA刷题篇5 - L1-005 考试座位号

「Mac玩转仓颉内测版14」PTA刷题篇5 - L1-005 考试座位号

本篇将继续讲解PTA平台上的题目 L1-005 考试座位号&#xff0c;通过考生准考证号与座位号的对应关系&#xff0c;掌握简单的数据查询与映射操作&#xff0c;进一步提升Cangjie编程语言的实际应用能力。 关键词 PTA刷题数据查询映射操作输入输出Cangjie语言 一、L1-005 考试座位…
阅读更多...
DAY27|贪心算法Part01|LeetCode:455.分发饼干、376. 摆动序列、53. 最大子序和

DAY27|贪心算法Part01|LeetCode:455.分发饼干、376. 摆动序列、53. 最大子序和

贪心算法 贪心的本质是选择每一阶段的局部最优&#xff0c;从而达到全局最优。 贪心算法并没有固定的套路&#xff0c;最难想的就在于如何通过局部最优去推出全局最优。在做一个题目的时候&#xff0c;靠自己手动模拟&#xff0c;如果模拟可行&#xff0c;就可以试一试贪心策略…
阅读更多...
源码解析-Spring Eureka（更新ing）

源码解析-Spring Eureka（更新ing）

源码解析-Spring Eureka 文章目录 源码解析-Spring Eureka前言一、从Spring.factory和注解开始二、重要的一步EurekaServerInitializerConfiguration三、初始化了什么&#xff1f;自动保护 四, 重新回到EurekaServerAutoConfiguration关于unavailable-replicas 前言 无 一、从…
阅读更多...
最新文章

Copyright @ 2022~2023