星梦启航

Appearance

维基百科版 ​

简介 ​

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

基本概念 ​

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别69b303b2c8dfb951926062e3b0a3bd39.png。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

优点 ​

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数（O(k)）。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器可以表示全集，其它任何数据结构都不能；
k和m相同，使用同一组散列函数的两个布隆过滤器的交并运算可以使用位操作进行。

缺点 ​

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面。这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
在降低误算率方面，有不少工作，使得出现了很多布隆过滤器的变种。比如：布谷鸟过滤器。

应用 ​

缓存系统：用于快速判断某个数据是否已经缓存，避免不必要的数据库查询。
垃圾邮件过滤系统：用于判断某个邮件是否在垃圾邮件列表中。
网页黑名单系统：用于判断某个链接是否在黑名单中。
爬虫的网址判重系统：用于记录已经访问过的URL，避免重复爬取。
区块链：用于快速判断某个交易是否在区块中。

参考链接 ​

维基百科：https://zh.wikipedia.org/wiki/布隆过滤器
互联网档案馆：https://web.archive.org/web/20111020130547/http://www.sigma.me/2011/09/13/hash-and-bloom-filter.html
博客园：https://www.cnblogs.com/allensun/archive/2011/02/16/1956532.html
redis与布隆过滤器：https://www.cnblogs.com/ysocean/p/12594982.html

GPT版 ​

布隆过滤器（Bloom Filter）是一种高效的空间存储结构，主要用于集合的成员判定，即判断一个元素是否在一个集合中。布隆过滤器具有以下特点：

  1. 高效的空间利用率：相比于直接存储所有元素，布隆过滤器能够在使用较少内存的情况下表示一个较大的集合。
  2. 快速查询：布隆过滤器能够以常数时间复杂度（O(1)）进行查询操作，效率极高。
  3. 有一定的误判率：布隆过滤器可能会误判一个元素在集合中（即存在“假阳性”），但绝不会误判一个元素不在集合中（即不存在“假阴性”）。

工作原理 ​

布隆过滤器使用多个哈希函数将集合中的元素映射到一个位数组（bit array）中。具体过程如下：

  1. 初始化一个位数组，长度为 (m)，所有位初始化为0。
  2. 对于每个要加入集合的元素，使用 (k) 个哈希函数对其进行哈希，得到 (k) 个哈希值，每个哈希值对应位数组中的一个位置，将这些位置的值设为1。
  3. 查询某个元素是否在集合中时，同样使用 (k) 个哈希函数对其进行哈希，得到 (k) 个哈希值，检查这些哈希值对应的位数组位置是否都为1。如果全部为1，则认为该元素在集合中；如果有任意一个位置不为1，则认为该元素不在集合中。

优点 ​

  • 空间效率高：能够用较小的空间表示较大的集合。
  • 查询速度快：查询操作非常高效，时间复杂度为O(1)。

缺点 ​

  • 存在误判率：有可能出现假阳性，即误判某个不在集合中的元素为在集合中。误判率与位数组长度 (m)、哈希函数数量 (k) 以及加入元素数量 (n) 有关。
  • 无法删除元素：一旦一个元素被加入布隆过滤器，就无法删除，因为删除操作可能会影响其他元素的判断。

应用场景 ​

  1. 缓存系统：在缓存中使用布隆过滤器可以快速判断某个数据是否已经缓存，避免不必要的数据库查询。
  2. 垃圾邮件过滤：布隆过滤器可以用于判断某个邮件是否在垃圾邮件列表中。
  3. 网络爬虫：爬虫可以使用布隆过滤器来记录已经访问过的URL，避免重复爬取。
  4. 区块链：在比特币等区块链系统中，布隆过滤器用于快速判断某个交易是否在区块中。

代码示例 ​

以下是一个简单的布隆过滤器的Python实现示例：

python
import hashlib

class BloomFilter:
    def __init__(self, size, hash_count):
        self.size = size
        self.hash_count = hash_count
        self.bit_array = [0] * size

    def _hashes(self, item):
        result = []
        for i in range(self.hash_count):
            hash_result = int(hashlib.sha256((item + str(i)).encode('utf-8')).hexdigest(), 16)
            result.append(hash_result % self.size)
        return result

    def add(self, item):
        for hash_value in self._hashes(item):
            self.bit_array[hash_value] = 1

    def check(self, item):
        for hash_value in self._hashes(item):
            if self.bit_array[hash_value] == 0:
                return False
        return True

# 使用示例
bloom = BloomFilter(1000, 5)
bloom.add("hello")
print(bloom.check("hello"))  # True
print(bloom.check("world"))  # False

这个示例使用了Python的hashlib库来生成哈希值，并且展示了布隆过滤器的基本操作：添加元素和检查元素。实际应用中，可以根据具体需求调整位数组大小和哈希函数数量。

为什么需要多个哈希函数 ​

使用多个哈希函数可以减少误判率（假阳性）。如果只使用一个哈希函数，位数组中许多位置会被不同元素映射到同一个位置，导致冲突频繁，从而增加误判率。通过使用多个哈希函数，可以更均匀地分布哈希值，减少冲突，提高判断准确性。

选择合适的哈希函数数量 ​

哈希函数数量的选择需要在空间效率和误判率之间进行权衡。一般来说，哈希函数数量 kkk 和位数组长度 mmm 以及元素数量 nnn 的关系可以通过以下公式来确定：
k=(mn)ln⁡2k = \left( \frac{m}{n} \right) \ln 2k=(nm)ln2
这个公式确保在给定的位数组长度和元素数量下，误判率最低。

hash-count应该是多个hash函数，拼接了一个字符串，效果一样吗 ​

在一定程度上能达到效果，但严格来说，它并不是真正的多个独立的哈希函数。在实际应用中，使用多个独立的哈希函数会更加有效。

布谷鸟过滤器 ​

布谷鸟过滤器（Cuckoo Filter）是一种空间高效的概率数据结构，用于集合的成员查询。它类似于布隆过滤器，但具有一些独特的优点，包括支持删除操作。布谷鸟过滤器的设计灵感来自于布谷鸟哈希表。

基本概念 ​

布谷鸟过滤器通过使用多个哈希函数将元素插入到一个固定大小的桶数组中。每个元素可以存储在由两个哈希函数计算得到的两个位置之一。当两个位置都已被占用时，元素将尝试“踢出”已经存在的元素，这样类似于布谷鸟在其他鸟巢中下蛋。

工作原理 ​

  1. 初始化：创建一个桶数组，每个桶可以存储多个（通常是两个）元素的指纹。
  2. 插入：
    • 计算元素的两个候选位置。
    • 如果任一位置有空闲槽，则插入指纹。
    • 否则，随机选择一个位置，将现有元素“踢出”，并将其重新插入到另一个候选位置。这一过程可能会重复多次（达到预设最大次数）。
  3. 查询：
    • 计算元素的两个候选位置。
    • 检查这两个位置是否有匹配的指纹。
  4. 删除：
    • 计算元素的两个候选位置。
    • 在这两个位置中找到并删除匹配的指纹。

优点 ​

  • 支持删除操作：布谷鸟过滤器可以高效地删除元素，而布隆过滤器不支持删除操作。
  • 较低的误判率：在相同的空间复杂度下，布谷鸟过滤器通常比布隆过滤器具有更低的误判率。
  • 查询效率高：查询时间复杂度为O(1)，与布隆过滤器相似。

缺点 ​

  • 插入可能失败：当桶数组接近满时，插入可能失败，需要重新调整数组大小或增加重新插入的最大次数。

应用场景 ​

  1. 缓存系统：与布隆过滤器类似，布谷鸟过滤器可以用于快速判断某个数据是否已缓存。
  2. 网络安全：用于快速检测是否某个IP地址或URL已在黑名单中。
  3. 数据库和存储系统：用于去重和快速查找。

代码示例 ​

以下是一个简单的布谷鸟过滤器的Python实现示例：

python
import random
import hashlib

class CuckooFilter:
    def __init__(self, size, bucket_size, max_kicks):
        self.size = size
        self.bucket_size = bucket_size
        self.max_kicks = max_kicks
        self.buckets = [[] for _ in range(size)]

    def _hashes(self, item):
        hash1 = int(hashlib.sha256(item.encode('utf-8')).hexdigest(), 16) % self.size
        hash2 = (hash1 ^ int(hashlib.md5(item.encode('utf-8')).hexdigest(), 16)) % self.size
        return hash1, hash2

    def insert(self, item):
        i1, i2 = self._hashes(item)
        if len(self.buckets[i1]) < self.bucket_size:
            self.buckets[i1].append(item)
            return True
        if len(self.buckets[i2]) < self.bucket_size:
            self.buckets[i2].append(item)
            return True
        for _ in range(self.max_kicks):
            i = random.choice([i1, i2])
            item, self.buckets[i][0] = self.buckets[i][0], item
            i1, i2 = self._hashes(item)
            if len(self.buckets[i1]) < self.bucket_size:
                self.buckets[i1].append(item)
                return True
            if len(self.buckets[i2]) < self.bucket_size:
                self.buckets[i2].append(item)
                return True
        return False

    def contains(self, item):
        i1, i2 = self._hashes(item)
        return item in self.buckets[i1] or item in self.buckets[i2]

    def delete(self, item):
        i1, i2 = self._hashes(item)
        if item in self.buckets[i1]:
            self.buckets[i1].remove(item)
            return True
        if item in self.buckets[i2]:
            self.buckets[i2].remove(item)
            return True
        return False

# 使用示例
filter = CuckooFilter(100, 2, 500)
filter.insert("hello")
print(filter.contains("hello"))  # True
print(filter.contains("world"))  # False
filter.delete("hello")
print(filter.contains("hello"))  # False

在这个示例中，布谷鸟过滤器使用两个哈希函数 _hashes 来计算元素的位置，并通过插入、查询和删除操作实现基本功能。桶大小和最大重新插入次数可以根据具体应用需求进行调整。

使用多个哈希函数实现而不是拼接字符串 ​

确实，我在前面的代码示例中使用了拼接字符串的方法来模拟多个哈希函数。虽然这种方法在一定程度上能达到效果，但严格来说，它并不是真正的多个独立的哈希函数。在实际应用中，使用多个独立的哈希函数会更加有效。我们可以使用哈希函数的变体来生成多个不同的哈希值。
下面是一个更为合适的实现，使用了 Python 的 mmh3 库（MurmurHash3）来生成多个哈希值。这样可以确保每个哈希函数是独立的：

安装 mmh3 库 ​

首先需要安装 mmh3 库：

bash
pip install mmh3

代码示例 ​

python
import mmh3
import random

class CuckooFilter:
    def __init__(self, size, bucket_size, max_kicks):
        self.size = size
        self.bucket_size = bucket_size
        self.max_kicks = max_kicks
        self.buckets = [[] for _ in range(size)]

    def _hashes(self, item):
        hash1 = mmh3.hash(item, 0) % self.size
        hash2 = mmh3.hash(item, hash1) % self.size
        return hash1, hash2

    def insert(self, item):
        i1, i2 = self._hashes(item)
        if len(self.buckets[i1]) < self.bucket_size:
            self.buckets[i1].append(item)
            return True
        if len(self.buckets[i2]) < self.bucket_size:
            self.buckets[i2].append(item)
            return True
        for _ in range(self.max_kicks):
            i = random.choice([i1, i2])
            item, self.buckets[i][0] = self.buckets[i][0], item
            i1, i2 = self._hashes(item)
            if len(self.buckets[i1]) < self.bucket_size:
                self.buckets[i1].append(item)
                return True
            if len(self.buckets[i2]) < self.bucket_size:
                self.buckets[i2].append(item)
                return True
        return False

    def contains(self, item):
        i1, i2 = self._hashes(item)
        return item in self.buckets[i1] or item in self.buckets[i2]

    def delete(self, item):
        i1, i2 = self._hashes(item)
        if item in self.buckets[i1]:
            self.buckets[i1].remove(item)
            return True
        if item in self.buckets[i2]:
            self.buckets[i2].remove(item)
            return True
        return False

# 使用示例
filter = CuckooFilter(100, 2, 500)
filter.insert("hello")
print(filter.contains("hello"))  # True
print(filter.contains("world"))  # False
filter.delete("hello")
print(filter.contains("hello"))  # False

在这个代码中，使用 mmh3.hash 方法生成两个独立的哈希值，确保哈希函数是独立的，减少冲突，增强了布谷鸟过滤器的性能。这样可以更准确地模拟多个哈希函数的效果。

本站收录内容源自互联网，不对其网站内容或交易负责。 | 如有内容侵犯权益，请联系站长删除相关内容！

Copyright © 2024 IT.Python斗罗 |