布隆过滤器

Ame 收录于

2023-03-05 约 786 字预计阅读 2 分钟次阅读

布隆过滤器

引出
- 对于hashtable，我们存放一个数据，会先进行哈希取模，然后决定放在哪一个桶，随后就会把这个数据放进🪣中，对于哈希表来说，存放的数据是准备完整的
- 我们再来想一个场景，如果我们不需要完整的数据，我们只是想判断一个这个数据到底存不存在，这个时候哈希表其实不太适合，其实可以做到的，但是终归不是完美适合这个场景所以我们需要一个更高效的数据结构
- 布隆过滤器他lei了
什么是布隆过滤器
- 他是一个很长的 二进制向量 和一系列随机映射函数
- 布隆过滤器可以用于检索一个元素是否在一个集合中
布隆过滤器的优点
- 空间效率和时间效率是远远超过一般的数据结构
布隆过滤器的缺点
- 有一定的误别率和删除困难
布隆过滤器的图示
布隆过滤器的误别

布隆过滤器的 golang实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72


package main

import (
    "fmt"
    "github.com/bits-and-blooms/bitset"
)

//设置哈希数组默认大小为16
const DefaultSize = 16

//设置种子，保证不同哈希函数有不同的计算方式
var seeds = []uint{7, 11, 13, 31, 37, 61}

//布隆过滤器结构，包括二进制数组和多个哈希函数
type BloomFilter struct {
    // 使用第三方库
    set *bitset.BitSet
    // 指定长度为6
    hashFuncs [6]func(seed uint, value string) uint
}

//构造一个布隆过滤器，包括数组和哈希函数的初始化
func NewBloomFilter() *BloomFilter {
    bf := new(BloomFilter)
    bf.set = bitset.New(DefaultSize)

    for i := 0; i < len(bf.hashFuncs); i++ {
        bf.hashFuncs[i] = createHash()
    }
    return bf
}

//构造6个哈希函数，每个哈希函数有参数seed保证计算方式的不同
func createHash() func(seed uint, value string) uint {
    return func(seed uint, value string) uint {
        var result uint = 0
        for i := 0; i < len(value); i++ {
            result = result*seed + uint(value[i])
        }
        //length = 2^n 时，X % length = X & (length - 1)
        return result & (DefaultSize - 1)
    }
}

//添加元素
func (b *BloomFilter) add(value string) {
    for i, f := range b.hashFuncs {
        //将哈希函数计算结果对应的数组位置1
        b.set.Set(f(seeds[i], value))
    }
}

//判断元素是否存在
func (b *BloomFilter) contains(value string) bool {
    //调用每个哈希函数，并且判断数组对应位是否为1
    //如果不为1，直接返回false，表明一定不存在
    for i, f := range b.hashFuncs {
        //result = result && b.set.Test(f(seeds[i], value))
        if !b.set.Test(f(seeds[i], value)) {
            return false
        }
    }
    return true
}

func main() {
    filter := NewBloomFilter()
    filter.add("asd")
    fmt.Println(filter.contains("asd"))  // true
    fmt.Println(filter.contains("2222")) // 
    fmt.Println(filter.contains("155343"))
}

目录

布隆过滤器

布隆过滤器