1. Toy模板网首页
  2. > Toy博客

哈希的应用--位图和布隆过滤器

10月前 作者：爱学习的鱼佬 分类：Toy博客 阅读(52) 违法举报

这篇具有很好参考价值的文章主要介绍了哈希的应用--位图和布隆过滤器。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

位图

1. 位图概念

位图（Bitset）是一种数据结构，用于表示一组布尔值，其中每个元素通常对应于一个位或一个二进制值，可以存储0或1。位图在计算机科学和计算机工程中经常用于各种应用，特别是在位级别的标志、掩码和快速查找中。以下是位图的一些关键特点：

  1. 二进制表示：位图中的每个元素都只能存储两个值，通常是0和1。这使得位图非常高效，因为每个位只需要一个二进制位来表示。
  2. 位操作：位图支持各种位操作，包括设置位、清除位、翻转位和查询特定位的操作。
  3. 空间效率：位图在表示大量布尔值时非常节省内存，因为每个位只需要一个二进制位。这使得位图在大规模数据处理中非常有用。
  4. 快速查找：位图用于快速查找元素的存在或不存在。通过检查位的值，可以快速确定元素是否在集合中。
  5. 位运算：位图支持位级别的位运算，如与、或、异或等，这些运算可用于合并和操作多个位图。

应用领域包括：

  • 位掩码：用于将一组标志或选项组合在一起，并进行快速检查和设置。
  • 布尔向量：用于高效存储和操作布尔值集合。
  • 集合操作：用于执行集合操作，如并集、交集和差集。
  • 压缩和编码：用于压缩数据，如运行长度编码（Run-Length Encoding）等。

2. 位图在实际中的应用

某大厂给过这样一道面试题，具体如下：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中

你可能最开始想遍历？那肯定是不行的，因为40亿个无符号数占用将近15G内存。

那使用散列表呢？那这里使用的空间能在内存上吗？显然不可以，就算可以

  • 散列表需要大量内存，因为需要为40亿个整数维护哈希表。
  • 哈希冲突可能会导致性能下降，需要解决冲突。
  • 需要选择合适的哈希函数以避免碰撞。

又会遇到各种各样的问题

那么这里就可以用到我们上面提到的位图概念

位图（Bitset）方法：

  • 创建位图：首先，创建一个足够大的位图，以能够表示您的整数范围。例如，如果整数范围在0到4,000,000,000之间，可以创建一个长度为4,000,000,001的位图。
  • 插入数据：将这40亿个无符号整数中的每个整数映射到位图的相应位置，并将对应的位设置为1。
  • 查询数据：当需要判断一个数是否在这40亿个数中时，只需查看位图中相应位置的位。如果该位为1，表示该整数在集合中；如果该位为0，表示不在集合中。

优点：

  • 位图非常节省内存，因为每个整数只需要一个位。
  • 不需要哈希函数，也不需要解决哈希冲突。

这里我们只需要不到500M就很好的解决了这个问题，听起来挺理想的，那么应该如何来实现它呢？

代码如下：

template<size_t N>
class bitset
{
public:
    bitset()
    {
        _bits.resize(N/8+1, 0);
    }

    void set(size_t x)
    {
        size_t i = x / 8;
        size_t j = x % 8;

        _bits[i] |= (1 << j);
    }

    void reset(size_t x)
    {
        size_t i = x / 8;
        size_t j = x % 8;

        _bits[i] &= ~(1 << j);
    }

    bool test(size_t x)
    {
        size_t i = x / 8;
        size_t j = x % 8;


        return _bits[i] & (1 << j);
    }

private:
    vector<char> _bits;
};

模板的作用就是用来传需要查询数的范围，比如我们这里有40亿怎么传值呢？

因为是无符号数，而无符号数范围是0-42亿左右，那我们不妨传入最大值，即-1

bitset<-1> bs1;

你可能会有疑问，多了两亿不会多很多内存吗？

答案是不会，占满其实也就512M，具体我们看下面的实现

我们先看成员变量的建立，由于在编程语言中，我们没有按位存储的存储类型（至少C/C++是没有的）

所以这里我们采用最小存储类型char，char占1个字节，可是我们需要的是1bit，那么我们该如何做呢？

接下来我们看位图的构造函数，我们用模板参数/8，初始化每个字节为全0，多+1是由于数组的索引从0开始，所以需要额外的一个元素来确保能够容纳最高索引 N-1 的位，这样我们的空间开辟完毕，也初始化完毕

接下来我们看set函数（此函数用于入位图）

void set(size_t x)
{
    size_t i = x / 8;
    size_t j = x % 8;

    _bits[i] |= (1 << j);
}

用于将指定索引 x 处的位设置为1：

  • size_t i = x / 8;：这一行代码计算索引 x 对应的字节（byte）索引。因为 _bits 是一个 vector<char>，每个元素代表一个字节（8位），所以我们用索引 x 除以8来得到字节索引。
  • size_t j = x % 8;：这一行代码计算索引 x 对应的位在字节中的位置。它使用取模运算来获得余数，表示在字节中的位偏移。
  • _bits[i] |= (1 << j);：这一行代码使用位操作将位图中索引 x 处的位设置为1。具体来说：
    • (1 << j) 会创建一个只有第 j 位为1的整数。例如，如果 j 是3，那么 (1 << 3) 将得到二进制 00001000。
    • _bits[i] |= (1 << j) 利用位或运算符将 _bits[i] 中对应的位和上面的整数进行“或”操作，将指定位设置为1。

这个函数的目的是在位图中设置指定索引 x 处的位为1，从而表示该位置存在某种标记或状态。

reset函数（此函数用于出位图）

void reset(size_t x)
{
    size_t i = x / 8;
    size_t j = x % 8;

    _bits[i] &= ~(1 << j);
}

用于将指定索引 x 处的位重置为0：

  • size_t i = x / 8;：这一行代码计算索引 x 对应的字节（byte）索引，以确定所在的字节。
  • size_t j = x % 8;：这一行代码计算索引 x 对应的位在字节中的位置，以确定位的偏移。
  • _bits[i] &= ~(1 << j);：这一行代码使用位操作将位图中索引 x 处的位重置为0。具体来说：
    • (1 << j) 会创建一个只有第 j 位为1的整数。例如，如果 j 是3，那么 (1 << 3) 将得到二进制 00001000。
    • ~(1 << j) 会创建一个只有第 j 位为0、其余位为1的整数，以便将第 j 位重置为0。
    • _bits[i] &= ~(1 << j) 利用位与运算符将 _bits[i] 中对应的位和上面的整数进行“与”操作，将指定位设置为0。

这个函数的目的是在位图中重置指定索引 x 处的位为0，从而表示该位置不存在某种标记或状态。

test函数（此函数用于查询数是否在位图中）

bool test(size_t x)
{
    size_t i = x / 8;
    size_t j = x % 8;


    return _bits[i] & (1 << j);
}

用于检查指定索引 x 处的位是否为1：

  • size_t i = x / 8;：这一行代码计算索引 x 对应的字节（byte）索引，以确定所在的字节。
  • size_t j = x % 8;：这一行代码计算索引 x 对应的位在字节中的位置，以确定位的偏移。
  • _bits[i] & (1 << j)：这一行代码使用位操作检查位图中索引 x 处的位是否为1。具体来说：
    • (1 << j) 会创建一个只有第 j 位为1的整数。例如，如果 j 是3，那么 (1 << 3) 将得到二进制 00001000。
    • _bits[i] & (1 << j) 利用位与运算符将 _bits[i] 中对应的位和上面的整数进行“与”操作，以检查该位是否为1。如果结果为0，表示该位为0；如果结果为非0，表示该位为1。

这个函数的目的是检查位图中指定索引 x 处的位是否为1，以判断某种标记或状态是否存在。如果该位为1，函数返回true，表示存在；如果该位为0，函数返回false，表示不存在。

实际上在C++中是加入了位图这个容器的，名称和我这一样，这里我们模拟实现是为了更好的理解这个概念

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

库中的bitset功能更多，但主要函数也是这几个

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

3. 位图相似应用

给定100亿个整数，如何找到只出现一次的整数？

其实这种问题和我们上面的示例的题目类似，解决方式只需略作改动。

我们可以使用两个位图分别标记存在次数，也就类似key value型，这里我们只需要标记3种情况

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

代码如下：

template<size_t N>
class twobitset
{
public:
    void set(size_t x)
    {
        bool inset1 = _bs1.test(x);
        bool inset2 = _bs2.test(x);

        // 00
        if (inset1 == false && inset2 == false)
        {
            // -> 01
            _bs2.set(x);
        }
        else if (inset1 == false && inset2 == true)
        {
            // ->10
            _bs1.set(x);
            _bs2.reset(x);
        }
        else if (inset1 == true && inset2 == false)
        {
            // ->11
            _bs1.set(x);
            _bs2.set(x);
        }
    }

    void print_once_num()
    {
        for (size_t i = 0; i < N; ++i)
        {
            if (_bs1.test(i) == false && _bs2.test(i) == true)
            {
                cout << i << endl;
            }
        }
    }

private:
    bitset<N> _bs1;
    bitset<N> _bs2;
};

这里我们需要实现一个双位图（Two-Bitset）数据结构。双位图是一种在每个索引上存储两个位的数据结构，通常用于表示每个索引的两种状态。代码解析如下：

  1. set(size_t x) 函数：
    • 首先，它检查 _bs1 和 _bs2 位图中索引 x 处的状态。
    • 如果 _bs1 中索引 x 处的位为0，而 _bs2 中索引 x 处的位也为0（00状态），则将 _bs2 中索引 x 处的位设置为1，将其状态变为01。
    • 如果 _bs1 中索引 x 处的位为0，而 _bs2 中索引 x 处的位为1（01状态），则将 _bs1 中索引 x 处的位设置为1，将 _bs2 中索引 x 处的位重置为0，将其状态变为10。
    • 如果 _bs1 中索引 x 处的位为1，而 _bs2 中索引 x 处的位为0（10状态），则将 _bs1 和 _bs2 中索引 x 处的位都设置为1，将其状态变为11。
  2. print_once_num() 函数：
    • 这个函数用于打印那些状态为10（01状态的相反）的索引。这表示只在 _bs2 中为1而在 _bs1 中为0的索引。这些索引被认为在双位图中只出现一次。

1个文件100亿int，1G内存，如何找到不超过2次的所有整数

两个题目其实相似，无非就是多一种状态，原理同上

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

布隆过滤器

在上面我们用位图很好的解决了多重整数高效查询的问题，那么我们在面对字符串时，该如何解决呢？

1. 布隆过滤器的提出

布隆过滤器（Bloom Filter）是由布隆在1970年提出的，它是一种空间效率高、查询速度快的数据结构，主要用于判断一个元素是否属于一个集合。布隆过滤器的提出解决了在大规模数据集中进行高效查找的问题，特别是当内存或存储有限的情况下。

以下是布隆过滤器的提出背景和主要原理：

提出背景： 在计算机科学中，一些常见的问题包括查找元素是否在某个集合中，如单词拼写检查、垃圾邮件过滤、URL检测等。传统的数据结构如散列表或树结构可以解决这些问题，但它们在存储和查询效率上存在一些限制，特别是在面对大规模数据集时。因此，布隆过滤器的提出是为了解决这些限制。

原理： 布隆过滤器的核心思想是使用一个位数组（Bit Array）和多个哈希函数。其主要工作步骤如下：

  1. 初始化：创建一个位数组，初始所有位为0，以及选择多个不同的哈希函数。
  2. 插入元素：当需要插入一个元素时，将该元素经过多个哈希函数的映射，得到多个不同的位，然后将这些位设置为1。
  3. 查询元素：当需要查询一个元素是否在集合中时，将该元素经过多个哈希函数的映射，得到多个位的位置，然后检查这些位是否都为1。如果所有位都为1，则认为元素可能存在于集合中；如果任何一个位为0，则可以确定元素不存在于集合中。

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

特点：

  • 布隆过滤器具有高效的查询速度，因为它不需要实际存储元素本身，而只需要检查位数组中的位。
  • 布隆过滤器可能会出现误判，即元素被判断为存在于集合中，但实际上并不在，但不会有漏判，即如果元素不在集合中，布隆过滤器不会将其判断为存在。
  • 布隆过滤器的空间效率很高，因为它可以存储大量元素而占用很少的内存。

2. 布隆过滤器的插入

布隆过滤器的插入过程是其核心操作之一，用于将元素添加到布隆过滤器中，以便后续查询该元素是否存在于集合中。下面是布隆过滤器的插入过程的详细解释：

  1. 初始化：首先，创建一个布隆过滤器，它包括一个位数组（Bit Array）和多个哈希函数。位数组中的每个位都初始化为0。
  2. 插入元素：要将一个元素插入布隆过滤器，执行以下步骤：
    • 哈希函数：使用预先选择的多个哈希函数，将要插入的元素映射为多个不同的位索引。每个哈希函数都会生成一个位索引，通常使用不同的种子值来确保生成不同的位索引。
    • 设置位：对于每个哈希函数生成的位索引，将相应的位数组中的位设置为1。这表示元素已经存在于布隆过滤器中。
  3. 完成插入：一旦对元素执行了上述步骤，插入过程就完成了。元素已被记录在位数组中，以后可以查询该元素是否存在于集合中。

注意事项：

  • 布隆过滤器不存储实际元素本身，只存储元素的哈希值或映射后的位索引。因此，插入操作是基于哈希值的，而不是实际元素。
  • 哈希函数的数量和质量对布隆过滤器的性能至关重要。更多的哈希函数通常意味着更低的误判率，但也需要更多的计算资源。选择哈希函数时应考虑平衡性能和内存占用。
  • 插入操作通常是快速的，因为它涉及位数组的直接设置，而不需要大量内存操作。这是布隆过滤器高效的一个原因之一。

插入过程使布隆过滤器记录了元素的存在，使后续的查询操作成为可能。查询操作会利用相同的哈希函数，检查位数组中的位来确定元素是否在集合中。这使得布隆过滤器在查找元素是否存在时非常高效，尤其适用于大规模数据集和资源有限的环境。

还需要注意的是，哈希参数当然是越多误判率越低，但是面临的问题就是内存也会越来越大，所以我们需要找到最合适的哈希函数个数，关于这一点，我们可以参考知乎大佬的一篇文章

知乎大佬文章链接

具体总结为

哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构
哈希的应用--位图和布隆过滤器,C++进阶,数据结构进阶CPP,哈希算法,算法,c++,数据结构

3. 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的，存在可能存在误判，但是不存在不会存在误判

4. 布隆过滤器的删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素
比如：删除其中一个元素，如果直接将该元素所对应的二进制比特位置0，另一元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作

5. 布隆过滤器的实现

在这里我们先实现3个哈希函数

struct HashBKDR
{
	// BKDR
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}

		return val;
	}
};

struct HashAP
{
	// BKDR
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct HashDJB
{
	// BKDR
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}

		return hash;
	}
};
  1. BKDR哈希函数 (Bentley and Sedgewick, 1997)：
    • BKDR哈希函数使用一个常数因子131，以及遍历字符串中的字符。
    • 对于每个字符，它将当前哈希值乘以131，然后加上字符的ASCII码值。
    • 最终，它返回计算得到的哈希值。
  2. AP哈希函数 (Arjen Lenstra and Endre Szemerédi’s hash function)：
    • AP哈希函数使用一系列位运算和异或操作来处理字符串中的字符。
    • 对于每个字符，它会根据字符的位置（奇数或偶数）应用不同的位运算操作。
    • 最终，它返回计算得到的哈希值。
  3. DJB哈希函数 (Daniel J. Bernstein, 1991)：
    • DJB哈希函数使用一个初始哈希值5381，以及遍历字符串中的字符。
    • 对于每个字符，它将当前哈希值左移5位，然后加上字符的ASCII码值。
    • 最终，它返回计算得到的哈希值。

布隆过滤器代码

// N表示准备要映射N个值
template<size_t N, 
class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio*N);
		//cout << hash1 << endl;

		_bits->set(hash1);

		size_t hash2 = Hash2()(key) % (_ratio*N);
		//cout << hash2 << endl;

		_bits->set(hash2);

		size_t hash3 = Hash3()(key) % (_ratio*N);
		//cout << hash3 << endl;

		_bits->set(hash3);
	}

	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio*N);
		//cout << hash1 << endl;
		if (!_bits->test(hash1))
			return false; // 准确的

		size_t hash2 = Hash2()(key) % (_ratio*N);
		//cout << hash2 << endl;

		if (!_bits->test(hash2))
			return false; // 准确的

		size_t hash3 = Hash3()(key) % (_ratio*N);
		//cout << hash3 << endl;

		if (!_bits->test(hash3))
			return false;  // 准确的

		return true; // 可能存在误判
	}


private:
	const static size_t _ratio = 5;
	std::bitset<_ratio*N>* _bits = new std::bitset<_ratio*N>;
};
  • Set(const K& key)：
    • Set 方法用于将元素插入布隆过滤器中。
    • 它分别使用三个哈希函数将元素映射到位数组中的三个位置，然后将这三个位置的位设置为1。
    • 这样，插入操作将三次设置位操作，将元素标记为存在于布隆过滤器中。
  • Test(const K& key)：
    • Test 方法用于测试元素是否存在于布隆过滤器中。
    • 与插入相似，它使用三个哈希函数将元素映射到三个位数组位置，并检查这三个位置的位是否都为1。
    • 如果有一个位置的位为0，说明元素不在布隆过滤器中，返回 false。
    • 如果三个位置的位都为1，可能存在误判，返回 true。

这个布隆过滤器可以用于在快速查找集合中的元素是否存在，但需要注意，它存在误判的可能性，即可能会将不在集合中的元素判断为存在。_ratio 在这个布隆过滤器实现中是一个倍数，它决定了位数组的大小。位数组的大小是 _ratio * N，其中 N 表示准备要映射的值的数量。具体来说，这个倍数 _ratio 用于控制位数组的大小以平衡误判率和内存使用。增加 _ratio 会增加位数组的大小，从而减小误判率，但也会增加内存占用。减小 _ratio 会减小位数组的大小，降低内存占用，但也会增加误判率。

6. 布隆过滤器优点

  1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
  2. 哈希函数相互之间没有关系，方便硬件并行运算
  3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
  4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
  5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
  6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

7. 布隆过滤器缺陷

  1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
  2. 不能获取元素本身
  3. 一般情况下不能从布隆过滤器中删除元素
  4. 如果采用计数方式删除，可能会存在计数回绕问题

8. 布隆过滤器的应用

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？

使用布隆过滤器和哈希切割

  1. 建立布隆过滤器：首先，创建一个合适大小的布隆过滤器。布隆过滤器的位数组大小需要足够大，以容纳所有可能的IP地址。
  2. 遍历日志文件：逐行遍历日志文件，提取每行中的IP地址。
  3. 哈希切割：对每个提取的IP地址应用一种哈希函数来将其映射到布隆过滤器的位数组上。这可以使用布隆过滤器的 Set 方法来实现。
  4. 统计次数：同时，维护一个哈希表，其中键是IP地址，值是出现的次数。在哈希切割过程中，检查IP是否已存在于表中，如果存在，则增加其出现次数。
  5. 查询次数最多的IP：在遍历完整个日志文件后，您可以遍历字典，找到出现次数最多的IP地址。
  6. 查询top K的IP：要找到top K的IP地址，可以对字典按照出现次数进行排序，然后选择前K个IP地址。

使用Linux系统命令

Linux系统提供了一些强大的命令行工具来处理文本文件，可以使用这些工具来解决问题：

  1. 使用awk命令或grep命令提取日志文件中的IP地址。
  2. 使用sort命令对提取的IP地址进行排序。
  3. 使用uniq -c命令统计IP地址的出现次数。
  4. 使用sort -nr命令按出现次数对IP地址进行逆序排序。
  5. 使用head命令来获取top K的IP地址。

示例命令行操作：

cat log_file.log | grep -oE "\b([0-9]{1,3}\.){3}[0-9]{1,3}\b" | sort | uniq -c | sort -nr | head -n K

这将列出出现次数最多的top K个IP地址。

无论使用哪种方法，都需要根据实际需求和性能要求来选择。使用布隆过滤器和哈希切割的方法可能需要编写自定义代码，但可以处理非常大的数据集。使用Linux系统命令则更加简单，但可能受限于系统资源和性能。

给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法

在这种情况下，由于内存有限，需要使用外部排序（external sorting）技术来处理这两个大型文件并找到它们的交集。外部排序是一种适用于大规模数据集的算法，其中数据无法完全加载到内存中。

精确算法：

  1. 分别对两个文件进行外部排序：首先，将两个文件分别划分为多个小文件块，每个小文件块可以适应内存的大小。然后，对每个小文件块进行内部排序，以确保每个块内的数据是有序的。
  2. 合并排序的块：对于每个文件，使用归并排序等合并算法，逐个合并排序后的小块，以创建一个完全有序的大文件。
  3. 查找交集：一旦两个文件都有序，可以使用合并算法来查找它们的交集。比较两个文件中的元素，将相同的元素输出到结果文件中。

这是一个精确的算法，它可以找到确切的交集，但需要大量的磁盘I/O和计算时间，因为数据需要多次读取和写入磁盘。

近似算法： 在内存有限的情况下，使用布隆过滤器可以实现近似的交集查找。以下是近似算法的步骤：

  1. 构建两个布隆过滤器：对于每个文件，构建一个布隆过滤器。这需要一小部分内存。在构建布隆过滤器时，需要选择合适的哈希函数和位数组大小，以平衡内存使用和误判率。
  2. 查询交集：对于第一个文件的每个查询，检查是否在第二个布隆过滤器中。如果布隆过滤器中存在该查询，将其添加到结果集中。
  3. 结果集：结果集中包含两个文件的近似交集。

近似算法的主要优点是节省了内存，但它会引入误判。如果某个查询在第一个布隆过滤器中存在，但实际上不存在于第二个文件中，它仍然会出现在结果集中。误判率取决于布隆过滤器的参数选择。

无论使用哪种算法，都需要在性能和准确性之间做权衡。精确算法提供准确的结果，但需要更多的时间和资源。近似算法可以在有限内存下快速处理，但可能会引入一定程度的误判。

如何扩展BloomFilter使得它支持删除元素的操作

Bloom过滤器是一种概率数据结构，通常不支持元素的删除操作。要扩展Bloom过滤器以支持元素的删除，可以考虑使用一些额外的技巧。以下是一种可能的方法：

使用计数型Bloom过滤器

一种支持删除操作的变体是计数型Bloom过滤器（Counting Bloom Filter）。与标准Bloom过滤器不同，计数型Bloom过滤器中的每个位不是简单的0或1，而是一个计数器。计数器可以表示一个元素被插入的次数。

以下是如何扩展Bloom过滤器以支持删除元素的步骤：

  1. 初始化计数型Bloom过滤器：创建一个计数型Bloom过滤器，其中每个位都初始化为0。计数型Bloom过滤器的大小通常与标准Bloom过滤器相同。
  2. 插入元素：当要插入元素时，不再将相应的位设置为1，而是增加相应的计数器。每次插入操作会增加计数器的值。
  3. 查询元素：在查询操作中，检查计数器是否大于零。如果计数器大于零，则表示元素存在。这是因为每次插入操作都会增加计数器的值。
  4. 删除元素：要删除元素，可以递减相应的计数器。如果计数器变为零，元素就被标记为不存在。

注意：在计数型Bloom过滤器中，可能存在溢出问题。因此，在删除元素时，需要小心确保计数器不会变为负数。

这种方法允许支持删除操作，但会占用更多的内存。计数型Bloom过滤器在需要跟踪元素出现次数的应用中非常有用，但仍然需要注意误判和溢出问题

另请注意，标准Bloom过滤器无法实现可靠的删除操作，因为删除一个元素可能会影响其他元素的位状态，从而导致不可预测的行为。计数型Bloom过滤器是一种可以处理删除操作的变体，但它需要更多的内存和计算资源。
示一个元素被插入的次数。

以下是如何扩展Bloom过滤器以支持删除元素的步骤：

  1. 初始化计数型Bloom过滤器：创建一个计数型Bloom过滤器，其中每个位都初始化为0。计数型Bloom过滤器的大小通常与标准Bloom过滤器相同。
  2. 插入元素：当要插入元素时，不再将相应的位设置为1，而是增加相应的计数器。每次插入操作会增加计数器的值。
  3. 查询元素：在查询操作中，检查计数器是否大于零。如果计数器大于零，则表示元素存在。这是因为每次插入操作都会增加计数器的值。
  4. 删除元素：要删除元素，可以递减相应的计数器。如果计数器变为零，元素就被标记为不存在。

注意：在计数型Bloom过滤器中，可能存在溢出问题。因此，在删除元素时，需要小心确保计数器不会变为负数。

这种方法允许支持删除操作，但会占用更多的内存。计数型Bloom过滤器在需要跟踪元素出现次数的应用中非常有用，但仍然需要注意误判和溢出问题

另请注意，标准Bloom过滤器无法实现可靠的删除操作，因为删除一个元素可能会影响其他元素的位状态，从而导致不可预测的行为。计数型Bloom过滤器是一种可以处理删除操作的变体，但它需要更多的内存和计算资源。文章来源地址https://www.toymoban.com/news/detail-713252.html

到了这里，关于哈希的应用--位图和布隆过滤器的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C++】哈希应用：位图 哈希切分 布隆过滤器

    【C++】哈希应用：位图 哈希切分 布隆过滤器

    我走后，他们会给你们加班费，会给你们调休，这并不是他们变好了，而是因为我来过。------龙哥 1. 大厂经典的面试题，给你40亿个不重复的无符号整数，让你快速判断一个数是否在这40亿个数中，最直接的思路就是遍历这40亿个整数，逐一进行比对，当然这种方式可以倒是可

    2023年04月09日
    浏览(41)
  • C++ 哈希思想应用:位图,布隆过滤器,哈希切分

    C++ 哈希思想应用:位图,布隆过滤器,哈希切分

    1.问题 给你40亿个不重复的无符号整数,没排过序.给一个无符号整数,如何快速判断一个数是否在这40亿个数中? 2.分析 1 Byte = 8 bit 1KB = 1024 Byte 1MB = 1024KB = 1024 1024 大约= 10的6次方Byte 1GB = 1024MB = 1024 10的6次方 大约= 10的9次方Byte = 10亿字节 因此4GB 约等于40亿字节 其实最快的方式就是

    2024年04月17日
    浏览(49)
  • [C++]哈希应用之位图&布隆过滤器

    [C++]哈希应用之位图&布隆过滤器

               主厨：邪王真眼 主厨的主页：Chef‘s blog   所属专栏：c++大冒险        我们之前学习了哈希表，哈希表通过映射关系，实现了O(1)的复杂度来查找数据，哈希在实践中是一个非常重要的思想，今天要学习的就是哈希思想的两大应用：位图与布隆过滤器 给 40 亿个

    2024年04月15日
    浏览(40)
  • 【C++】哈希的应用:位图、哈希切分与布隆过滤器

    【C++】哈希的应用:位图、哈希切分与布隆过滤器

    需要云服务器等云产品来学习Linux的同学可以移步/--腾讯云--/--阿里云--/--华为云--/官网，轻量型云服务器低至112元/年，新用户首次下单享超低折扣。   目录 一、位图 1、位图的概念 2、大厂面试题 2.1位图应用（腾讯） 2.2位图应用 3、位图的优缺点 二、哈希切分 三、布隆过滤

    2023年04月09日
    浏览(49)
  • 【C++学习】哈希的应用—位图与布隆过滤器

    【C++学习】哈希的应用—位图与布隆过滤器

    文章简介 ： 在这篇文章中，你会学习到关于哈希思想的最常见的两个应用，也就是 位图 与 布隆过滤器 ， 文章会讲解位图和布隆过滤器的概念，底层实现，对应的适应的场景，以及相关经典 海量数据面试题 及解析。 所谓位图，就是用每一位来存放某种状态，适用于 海量

    2024年04月14日
    浏览(60)
  • 【C++高阶(六)】哈希的应用--位图&布隆过滤器

    【C++高阶(六)】哈希的应用--位图&布隆过滤器

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 哈希最常用的应用是unordered 系列的容器,但是当面对海量数据 如100亿个数据中找有没有100这 个数时,使用无序容器的话内存放不下 所以哈希

    2024年02月05日
    浏览(46)
  • C++哈希hash：位图、布隆过滤器的实现及应用

    C++哈希hash：位图、布隆过滤器的实现及应用

    所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用 来判断某个数据存不存在的。 当我们想查找某一个数据是否存在或者是否处于某种状态时，相比于直接对存放数据的容器进行遍历查找，与原存放数据的容器所建立映射关系的位图来

    2024年04月11日
    浏览(49)
  • 哈希思想应用【C++】(位图，布隆过滤器，海量数据处理面试题)

    哈希思想应用【C++】(位图，布隆过滤器，海量数据处理面试题)

       目录 一，位图 1. 位图概念 2.实现 3. 测试题 位图的优缺点 二，布隆过滤器 1). 布隆过滤器提出 2). 概念 3). 布隆过滤器的查找 4). 布隆过滤器删除(了解) 5). 布隆过滤器优点 6). 布隆过滤器缺陷 三，海量数据面试题 1）哈希切割 我们首先由一道面试题来理解位图 给40亿个不

    2024年02月04日
    浏览(45)
  • 【C++】哈希（位图，布隆过滤器）

    【C++】哈希（位图，布隆过滤器）

    今天的内容是哈希的应用：位图和布隆过滤器 目录 一、位图 1.位图概念 2.位图的应用 二、哈希切分 三、布隆过滤器 1.布隆过滤器的概念 2.布隆过滤器的应用 四、总结   今天的内容从一道面试题开始引入： 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何

    2024年02月01日
    浏览(37)
  • 【C++】哈希位图和布隆过滤器

    【C++】哈希位图和布隆过滤器

    哈希位图和布隆过滤器都是常用的概率数据结构，用于高效地判断一个元素是否存在于一个集合当中，但它们在实现方法和各自的优缺点上有所区别。 哈希位图 哈希位图（Hash Bitmap）是由一个位数组构成，每个元素（通常是一个整数）被映射到位数组中的某个位置。对于集合

    2024年02月08日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包