如何在海量数据中查看是否存在某字符串

一、查询某字符串是否存在的常用数据结构

一般为红黑树、哈希表、bitmap、布隆过滤器，由于是海量数据，所以前两种数据结构不适合使用，本文着重讲bitmap与布隆过滤器。

二、Bitmap

Bitmap 是一种数据结构，用于快速存储和查询一个数在一组数中是否存在。它的实现原理是将一个数抽象为一个bit位，每个bit位只有0和1两种状态，而且可以通过位运算来实现对bit位的快速操作。使用 bitmap 可以在很短的时间内进行多个数的查询操作。

在 Golang 中，可以使用标准库中的 []byte 来实现 bitmap。[]byte 中每一个字节都可以看做一个 8 位的二进制数，因此可以表示 8 个数字。具体实现时，将需要存储的数字除以 8，得到在[]byte中的下标，然后将该数字对 8 取模，得到在对应字节中的二进制数的位置。在该位置设置 1，表示该数字存在于 bitmap 中。查询时，同样根据数字的位置，查询对应的 bit 位是否为 1，如果为 1 则表示该数字存在于 bitmap 中，否则不存在。

以下是一个使用 Golang 实现 Bitmap 的示例代码:

type BitMap struct {
    data []byte
}

func NewBitMap(max int) *BitMap {
    return &BitMap{data: make([]byte, max/8)}
}

func (b *BitMap) Set(num int) {
    index, offset := num/8, uint(num%8)
    b.data[index] |= 1 << offset
}

func (b *BitMap) Get(num int) bool {
    index, offset := num/8, uint(num%8)
    return b.data[index]&(1<<offset) != 0
}

上面的代码定义了一个 BitMap 结构体，其中data字段是存储 bit 位的[]byte。NewBitMap方法用于创建一个 BitMap 实例，其中的参数max表示该 BitMap 能够表示的最大数字。Set方法用于将指定的数字存储到 Bitmap 中，Get方法用于查询指定的数字是否存在于 Bitmap 中。

我们都知道位运算比较高效，所以上述代码中的 num/8 和 num%8 都可以优化。 在Golang，左移的运算规则是：左移 N 位，就是乘以 2 的 N 次方，例如：

a := 1 << 3 // 2的3次方*1

右移 N 位，就是除以 2 的 N 次方，例如：

a := 8 >> 3 // 8除以2的3次方

因为 2^3=8 ，所以 num/8 可以优化成 num >> 3。

%操作也有一个规则： a%2^n = a&(2^n-1)，所以 num%8可以优化成 num&7 优化后的代码如下

type BitMap struct {
    data []byte
}

func NewBitMap(max int) *BitMap {
    return &BitMap{data: make([]byte, max>>3 + 1)}
}

func (b *BitMap) Set(num int) {
    // num/8得到byte[]的index  num%8得到在byte[index]的位置 
    index, offset := num>>3, uint(num&7)
    //将1左移offset后，对应offset的位置就是1，然后和以前的数据做|，这样，那个位置就替换成1了。
    b.data[index] |= 1 << offset
}

func (b *BitMap) Get(num int) bool {
    index, offset := num>>3, uint(num&7)
    return b.data[index]&(1<<offset) != 0
}

func main() {
    // 创建一个包含 1000 个位的 Bitmap
    bm := NewBitMap(1000)

    // 设置第 100 位为 true
    bm.Set(100)

    // 获取第 100 位的值
    fmt.Println(bm.Get(100)) // true

    // 获取第 200 位的值
    fmt.Println(bm.Get(200)) // false
}

使用上述代码实现的 Bitmap 可以很方便地用于处理大规模数据的查找和去重等操作，提高代码的效率。

但是Bitmap依然存在缺陷：

1、内存消耗高：Bitmap 的内存占用随着存储数据的范围增大而增大，如果要存储的范围很大，内存占用可能会变得非常高。因此，如果需要存储的数据大小分布不均匀，Bitmap 的内存占用会变得更加明显。

2、动态增加困难：Bitmap 在存储数据时，需要预先分配足够的空间，如果数据的数量不断变化，需要不断调整分配的空间大小。

三、BloomFilter

BloomFilter是一种数据结构，用于高效地判断某个元素是否存在于一个集合中。它通过利用 Bitmap 来实现，同时使用多个哈希函数来映射元素到位图中的多个位置。因此，可以说 BloomFilter 是 Bitmap 的一种变体，通过哈希函数实现了对不同元素的分布均匀映射，进一步提高了存储效率和查询效率。

BloomFilter的核心思想是：对于一个元素， 进行 k 次哈希操作，将得到的 k 个哈希值设置到 k 个bit位上，把这 k 个位上的值都设置为 1 。当需要判断某个元素是否在集合中时，将该元素进行 k 次哈希操作，查看其对应的 k 个位上的值是否都为1，若存在某一位不为 1 ，则可以判定该元素不在集合中。如果全部为 1 ，则可能存在于集合中。

BloomFilter的优点是占用空间非常小，且判断速度非常快。由于使用了哈希函数，所以缺点是存在误判率，即某些元素会被误判为在集合中。误判率取决于哈希函数的数量和位图大小等因素。

在实现BloomFilter时，需要确定 Bitmap 大小和哈希函数数量，以及哈希函数的选择。Bitmap 大小取决于要存储的元素数量和期望的误判率。哈希函数数量一般是根据 Bitmap 大小和要存储的元素数量计算得出的。哈希函数的选择要保证哈希函数值的分布尽可能均匀。

通常可以使用下面的公式来确定 Bloom Filter 的位图大小和哈希函数数量：

• 位图大小 = -(n * log(p)) / (log(2)^2) ，其中 n 表示需要处理的数据量，p 表示期望的误判率。
• 哈希函数数量 = (位图大小 * log(2)) / n

在Go中，可以使用以下公式计算位图大小和哈希函数数量：

位图大小 = ceil(n * log(p) / log(1/(2^8))) 其中，n是要存储的元素数量，p是误判率，2^8表示每个byte有8位。

哈希函数数量 = ceil(m / n * log(2)) 其中，m是位图大小，n是要存储的元素数量，log(2)表示以2为底的对数，ceil()函数表示向上取整。

下面是使用Go实现上述公式的示例代码：

package main

import (
    "fmt"
    "math"
)

func main() {
    // 输入参数
    n := 1000000 // 需要处理的数据量
    p := 0.01    // 期望的误判率

    // 计算位图大小
    bitmapSize := int(-(float64(n) * math.Log(p)) / math.Pow(math.Log(2), 2))

    // 计算哈希函数数量
    hashNum := int((float64(bitmapSize) * math.Log(2)) / float64(n))

    fmt.Printf("位图大小：%d\n", bitmapSize)
    fmt.Printf("哈希函数数量：%d\n", hashNum)
}

在确定位图大小和哈希函数数量时，需要注意以下几点：

位图大小和哈希函数数量需要根据实际的数据量和误判率进行调整，以达到最佳的效果。

• 通常情况下，位图大小会比数据量大，以确保误判率的准确性。
• 哈希函数数量越多，误判率越小，但是计算哈希函数也需要时间和资源，因此需要权衡使用。
• 选择合适的哈希函数对 BloomFilter 的性能和误判率都有很大的影响，因此需要根据实际应用场景进行选择和优化。

以下是BloomFilter代码实现：

package main

import (
    "github.com/spaolacci/murmur3"
)

type BloomFilter struct {
    bitmap []byte
    k      uint
    count  uint64
}

func NewBloomFilter(m uint, k uint) *BloomFilter {
    return &BloomFilter{
        bitmap: make([]byte, m),
        k:      k,
    }
}

func (b *BloomFilter) Add(data []byte) {
    hashers := b.hashers(data)
    for _, h := range hashers {
        b.bitmap[h>>3] |= 1 << (h & 7)
    }
    b.count++
}

func (b *BloomFilter) Contains(data []byte) bool {
    hashers := b.hashers(data)
    for _, h := range hashers {
        if b.bitmap[h>>3]&(1<<(h&7)) == 0 {
            return false
        }
    }
    return true
}

func (b *BloomFilter) Remove(data []byte) {
    hashers := b.hashers(data)
    for _, h := range hashers {
        b.bitmap[h>>3] &^= 1 << (h & 7)
    }
    b.count--
}

func (b *BloomFilter) hashers(data []byte) []uint64 {
    h1, h2 := murmur3.New128(), murmur3.New128()

    hashers := make([]uint64, b.k)
    for i := uint(0); i < b.k; i++ {
        h1.Reset()
        h2.Reset()
        h1.Write(data)
        h2.Write(data)
        v1, v2 := h1.Sum128()
        v3, v4 := h2.Sum128()
        hashers[i] = (v1 + uint64(i)*v2 + uint64(i*i)*v3 + uint64(i*i*i)*v4) % uint64(len(b.bitmap)*8)
    }
    return hashers
}

func main() {
    n := 1000000
    p := 0.01

    // 计算位图大小
    m := -(float64(n) * math.Log(p)) / math.Pow(math.Log(2), 2)
    // 计算哈希函数数量
    k := (m * math.Log(2)) / float64(n)

    bf := NewBloomFilter(uint(m), uint(k))

    bf.Add([]byte("apple"))
    bf.Add([]byte("banana"))
    bf.Add([]byte("orange"))

    fmt.Println(bf.Contains([]byte("apple")))
    fmt.Println(bf.Contains([]byte("pear")))

    bf.Remove([]byte("apple"))

    fmt.Println(bf.Contains([]byte("apple")))
    fmt.Println(bf.Contains([]byte("banana")))

    fmt.Println(bf.count)
}