极致高效的数据处理：位图、布隆过滤器与哈希切分的奇妙之旅

suye

发布于 2024-11-19 10:21:08

13000

代码可运行

文章被收录于专栏：17的博客分享17的博客分享

运行总次数：0

代码可运行

前言

本文将带领你深入探索哈希的三大高效应用——位图、布隆过滤器和哈希切分。它们如同精巧的齿轮，共同驱动着现代计算系统的高效运作。从减少存储空间到加速查找效率，从数据去重到流式处理，这些技术在幕后悄然发挥着巨大的力量。让我们一起揭开哈希算法的神秘面纱，领略数据处理的艺术之美。

📮一、位图

📧1.1 面试题

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

问题剖析：

40亿个整数代表160亿个Byte。

1G = 1024MB = 1024^2KB = 1024^3Byte

，所以

160亿Byte ≈ 16G

。显然在内存中存储16G的内容显然不合理，那我们该怎么去解决呢？这道题目本质上是让我们去判断在不在，因此我们无需将这 40亿个整数都存起来，只需要用一个标志位去判断在不在，比如 1 表示在，0 表示不在。存储标志位的最小单位是 bit。大体思路有了，下面引出位图的概念，这道题目需要使用位图去解决。

📧1.2 位图的概念

位图（bitset） 是一种使用位（bit）来表示某个元素存在与否的数据结构。每个位可以存储一个二进制值（0 或 1），这使得位图在表示大量数据时非常高效，尤其适合判断数据是否存在。

存储结构：位图使用一个比特数组（即一个由二进制位构成的数组）来存储信息。每一位（bit）对应一个可能的元素。对于给定的数据范围，每个可能的值在位图中对应一个唯一的位置。
操作方法：
- 设置位（set）：将某一位置上的位设为 1，表示该位置对应的元素存在。
- 清除位（reset）：将某一位置上的位设为 0，表示该位置对应的元素不存在。
- 检查位（test）：检查某一位置上的位是 1 还是 0，以判断该元素是否存在。
位图的存储方式：
- 先补充一个内容，小端字节序：人们习惯于将数据的高位写在左边，可在大多数PC端，字节的排序却是从右往左。
下面演示一下位图的存储方式：

📧1.3 位图的解决方案

📩1.3.1 原理

使用位图表示每个无符号整数的存在状态。由于无符号整数的范围为 0 到 2^32-1，我们可以用 2^32 个比特位（约 512 MB 内存）来表示每个数的存在状态。
位图的每一位表示一个整数是否存在。

📩1.3.2 实现步骤

初始化一个 2^32 大小的位数组，每个位表示一个可能的整数。
遍历 40 亿个数，对于每个数 x，将位图 bitset[x] 设置为 1，表示该数存在。
对于给定的查询数 num，检查 bitset[num] 是否为 1，如果是则存在，否则不存在。

📩1.3.3 实现过程

模拟实现bitset

namespace xny {
	template<size_t N>
	class bitset {
	public:
		// 构造函数，初始化位图数组，大小为 size / 32，这里 +31 的原因是为了向上取整
		bitset() : bits((N + 31) / 32, 0) {}

		// 设置整数 num 对应的位为 1
		void set(size_t num) {
			bits[num / 32] |= (1U << num % 32);
		}

		// 设置整数 num 对应的位为 0
		void reset(size_t num) {
			bits[num / 32] &= (~(1U << num % 32));
		}
		
		// 判断整数 num 是否存在
		bool test(size_t num) {
			return bits[num / 32] & (1U << num % 32);
		}

	private:
		vector<unsigned int> bits;	// 位图存储
	};
}

测试代码：

int main() {
	// 定义位图，大小为40亿
	xny::bitset<4000000000> bt;

	// 假设有40亿个不重复整数的数组 nums
	// 示例：将这些数插入位图中
	unsigned int nums[] = { 123, 456, 789, 400000000, 3999999999 };
	for (unsigned int num : nums) {
		bt.set(num);
	}

	// 查询整数是否存在
	unsigned int num = 123;
	if (bt.test(num)) {
		cout << num << " 存在于集合中" << endl;
	}
	else {
		cout << num << " 不存在于集合中" << endl;
	}

	return 0;
}

📩1.3.4 优点

查询时间复杂度为 O(1)。
内存占用合理，约 512 MB。

📧1.4 位图应用

题目1：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？

**思路一：**将其中一个文件的所有值映射到一个位图，然后去遍历另一个文件中的数据去判断在不在。这种思路存在一个缺陷，得到的交集中可能出现重复值的情况，而正常情况下交集中是不应该出现重复值，因此在前面求得交集后，还需要用 set 进行去重。这里可能会出现重复的数据过多的情况，去使用 set 可能会超过 1G 内存。
思路二：将两个文件中的整数分别映射到两个位图中，然后再将两个位图按位与一下，值为 1 的比特位对应的整数就是交集。

int main() {
	unsigned int nums1[] = { 1, 2, 3, 4, 4, 5, 3, 2, 5, 6, 7, 5, 4 };
	unsigned int nums2[] = { 2, 2, 3, 3, 4, 3, 3, 2, 4, 4};

	xny::bitset<10> bt1;
	xny::bitset<10> bt2;

	for (auto num : nums1) {
		bt1.set(num);
	}

	for (auto num : nums2) {
		bt2.set(num);
	}

	for (size_t i = 0; i < 10; i++){
		if (bt1.test(i) && bt2.test(i)) {
			cout << i << " ";
		}
	}
	cout << "是nums1和nums2的交集";

	return 0;
}

**注意：**上面用两个数组 nums1 和 nums2 来模拟两个文件。另外需要注意：位图到底需要多少个比特位不是取决于数据的个数，而是取决于这一堆数据可能的范围，数据范围有多大位图就需要开辟多少个比特位的空间。

题目2：给定100亿个整数，设计算法找到只出现一次的整数？

思路：抓住题眼“只出现一次”，最开始的那道面试题只是让我们判断一个数是否在这40亿个数中，而现在这道题的要求总共有两个：
1. 找出这些整数
2. 这些整数只出现过一次
先处理第二个条件，由之前的面试题我们可以知道要找出一个数，只需要判断它的比特位是 0 还是 1 ，而我们现在要定义一个数出现的次数，至少需要两个比特位用来表示至少三种情况：00（未曾出现），01（仅出现一次），10（出现过2次及以上），甚至 11 这种情况暂时不需要考虑。可是两个比特位才能表示一个状态，我们要如何处理呢？在一个位图中存储？那又该如何遍历？很显然我们需要两个位图来存储，只需要根据两个位图对应的比特位就能判断一个数出现的次数了，以下是一个简单的示例：

由上图可知：我们需要更新我们的bitset数据结构，使其有两个位图，然后重定义以下set函数即可。

至于第一个条件，我们只要遍历一次数组字节数组，找出状态为 01 对应的数即可。

新的数据结构：

namespace xny {
	template<size_t N>
	class bitset {
	public:
		// 构造函数，初始化位图数组，大小为 size / 32
		bitset() : bits((N + 31) / 32, 0) {}

		// 设置整数 num 对应的位为 1
		void set(size_t num) {
			bits[num / 32] |= (1U << num % 32);
		}

		// 设置整数 num 对应的位为 0
		void reset(size_t num) {
			bits[num / 32] &= (~(1U << num % 32));
		}
		
		// 判断整数 num 是否存在
		bool test(size_t num) {
			return bits[num / 32] & (1U << num % 32);
		}

	private:
		vector<unsigned int> bits;	// 位图存储
	};

	template<size_t N>
	class two_bitset {
	public:
		void set(size_t num) {
			// 00 -> 01
			if (!bits1.test(num) && !bits2.test(num)) {
				bits2.set(num);
			}
			// 01 -> 10
			else if (!bits1.test(num) && bits2.test(num)) {
				bits1.set(num);
				bits2.reset(num);
			}
			// 10代表出现两次及以上，不需要更改
		}

		// 判断只出现过一次
		bool is_once(size_t num) {
			return !bits1.test(num) && bits2.test(num);
		}

	private:
		bitset<N> bits1;	// 位图存储第一位
		bitset<N> bits2;	// 位图存储第二位
	};
}

测试代码：

int main() {
	// 定义位图，大小为10
	xny::two_bitset<10> bt;

	// 示例：将这些数插入位图中
	unsigned int nums[] = { 1, 2, 3, 4, 4, 5, 3, 2, 5, 6, 7, 5, 4 };
	for (unsigned int num : nums) {
		bt.set(num);
	}

	// 查询整数是否只出现一次
	for (int i = 0; i < 10; ++i) {
		if (bt.is_once(i)) {
			cout << i << "只出现过一次" << endl;
		}
	}
 
	return 0;
}

题目3：位图应用变形：1个文件有100亿个无符号整数，1G内存，设计算法找到出现次数不超过2次的所有的无符号整数。

**思路：**这个题和上一道题几乎一样，只不过要找的是出现次数不超过2次的数，我们只需要在原来数据结构的基础上，添加一个整数出现次数超过两次的函数，在遍历打印的时候对这个函数取反不就得到想要的答案了吗？

修改后的数据结构：

namespace xny {
	template<size_t N>
	class bitset {
	public:
		// 构造函数，初始化位图数组，大小为 size / 32
		bitset() : bits((N + 31) / 32, 0) {}

		// 设置整数 num 对应的位为 1
		void set(size_t num) {
			bits[num / 32] |= (1U << num % 32);
		}

		// 设置整数 num 对应的位为 0
		void reset(size_t num) {
			bits[num / 32] &= (~(1U << num % 32));
		}
		
		// 判断整数 num 是否存在
		bool contain(size_t num) {
			return bits[num / 32] & (1U << num % 32);
		}

	private:
		vector<unsigned int> bits;	// 位图存储
	};

	template<size_t N>
	class two_bitset {
	public:
		void set(size_t num) {
			// 00 -> 01
			if (!bits1.contain(num) && !bits2.contain(num)) {
				bits2.set(num);
			}
			// 01 -> 10
			else if (!bits1.contain(num) && bits2.contain(num)) {
				bits1.set(num);
				bits2.reset(num);
			}
			// 10 -> 11
			else if (bits1.contain(num) && !bits2.contain(num)) {
				bits2.set(num);
			}
			// 11代表出现两次以上，不需要更改
		}

		// 判断出现超过两次
		bool over_twice(size_t num) {
			return bits1.contain(num) && bits2.contain(num);
		}

		// 判断没有出现过
		bool empty(size_t num) {
			return !bits1.contain(num) && !bits2.contain(num);
		}

	private:
		bitset<N> bits1;	// 位图存储第一位
		bitset<N> bits2;	// 位图存储第二位
	};
}

测试代码：

int main() {
	// 定义位图，大小为10
	xny::two_bitset<10> bt;

	// 示例：将这些数插入位图中
	unsigned int nums[] = { 1, 2, 3, 4, 4, 5, 3, 2, 5, 6, 7, 5, 4 };
	for (unsigned int num : nums) {
		bt.set(num);
	}

	// 查询整数是否只出现两次
	for (size_t i = 0; i < 10; ++i) {
		if (!bt.empty(i) && !bt.over_twice(i)) {
			cout << i << "出现不超过两次" << endl;
		}
	}

	return 0;
}

**注意：**不要把没有出现过的数给打印出来了，所以应该先判断这个数是否存在即不为 00 。

📮二、布隆过滤器

📧2.1 布隆过滤器的开发历史

布隆过滤器由 布顿·布隆（Burton H. Bloom） 在 1970 年 提出。布隆在他的论文《Space/Time Trade-offs in Hash Coding with Allowable Errors》中详细描述了这种数据结构。布隆过滤器的设计初衷是为了在 空间受限 的情况下高效地进行集合成员查询操作。

📧2.2 什么是布隆过滤器

布隆过滤器（Bloom Filter） 是一种高效的 概率型数据结构，主要用于快速判断某个元素是否在一个集合中。它适合在 大规模数据 或 内存有限 的场景中使用，因为它可以用较小的空间提供快速的查询功能，但允许一定的误判。它的基本思想是使用一个位数组和多个哈希函数。元素添加到集合时，通过多个哈希函数将元素映射到位数组的多个位置，并将这些位置的位设置为 1。查询时，同样使用哈希函数计算位数组中的多个位置，如果这些位置的位都为 1，则认为该元素“可能存在”，如果有任何一位为 0，则可以确定该元素“不存在”。

📧2.3 布隆过滤器的实现原理

📩2.3.1 布隆过滤器的初步认识

布隆过滤器是一个 bit 数组，长这样：

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成**多个哈希值，**并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “apple” 和三个不同的哈希函数分别生成了哈希值 1、4、8，则上图转变为：

我们现在再存一个值 “banana”，如果哈希函数返回 3、4、8 的话，图继续变为：

注意，4 和 8 这两个 bit 位由于两个值的哈希函数都返回了同一个 bit 位，因此它们被覆盖了。现在我们如果想查询 purple 这个值是否存在，哈希函数返回了 1、5、8三个值，结果我们发现 5 这个 bit 位上的值为 0，说明没有任何一个值映射到这个 bit 位上，因此我们可以很确定地说 purple 这个值不存在。而当我们需要查询 “apple” 这个值是否存在的话，那么哈希函数必然会返回 1、4、8，然后我们检查发现这三个 bit 位上的值均为 1，那么我们可以说 apple 存在了么？答案是不可以，只能是 apple 这个值可能存在。

这是为什么呢？答案很简单，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值 peach 即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断 peach 这个值存在。

📩2.3.2 布隆过滤器的模拟实现

struct BKDRHash{
    size_t operator()(const string& str){
        size_t hash = 0;
        for (auto ch : str){
            hash = hash * 131 + ch;
        }

        return hash;
    }
};

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

        return hash;
    }
};

struct DJBHash{
    size_t operator()(const string& str){
        size_t hash = 5381;
        for (auto ch : str) {
            hash += (hash << 5) + ch;
        }

        return hash;
    }
};

template<size_t N, class K = string, class Hash1 = BKDRHash, class Hash2 = APHash, class Hash3 = DJBHash>
class BloomFilter {
public:
	void set(const K& key) {
        size_t hash1 = Hash1()(key) % N;
        bits.set(hash1);

        size_t hash2 = Hash2()(key) % N;
        bits.set(hash2);

        size_t hash3 = Hash3()(key) % N;
        bits.set(hash3);
	}

    bool contain(const K& key) {
        size_t hash1 = Hash1()(key) % N;
        if (bits.test(hash1) == false)
            return false;

        size_t hash2 = Hash2()(key) % N;
        if (bits.test(hash2) == false)
            return false;

        size_t hash3 = Hash3()(key) % N;
        if (bits.test(hash3) == false)
            return false;

        return true; // 存在误判
    }

private:
	bitset<N> bits;
};

测试代码：

void TestBloomFilter1(){
	BloomFilter<11> bf;
	bf.set("孙悟空");
	bf.set("猪八戒");
	bf.set("牛魔王");
	bf.set("二郎神");

	cout << bf.contain("孙悟空") << endl;
	cout << bf.contain("猪八戒") << endl;
	cout << bf.contain("沙悟净") << endl;	// 误判！
}

int main() {
	TestBloomFilter1();

	return 0;
}

由上图可知，布隆过滤器确实会误判，我们不妨把 bf.set("牛魔王"); 这行代码注释掉来试试：

可以明细看到，误判消失了，所以应该是牛魔王的出现导致猪八戒误判了。那么究竟是什么因素在影响着布隆过滤器的误判率呢？

📩2.3.3 布隆过滤器的误判率

布隆过滤器的误判率，即假阳性率，是指当一个元素实际上不在集合中时，布隆过滤器仍然判断该元素“可能存在”的概率。布隆过滤器的误判率主要受到以下几个因素的影响：

📨1. 位数组的大小（m）

位数组的大小 m 是影响误判率的一个重要因素。当位数组越大时，哈希函数产生的哈希值会更分散，每个元素占用的位也相对减少，这样可以降低误判率。相反，如果位数组太小，不同元素的哈希值更容易冲突，误判率会增高。

📨2. 哈希函数的数量（k）

布隆过滤器使用多个哈希函数，每个哈希函数可以将元素映射到位数组的一个位置。哈希函数的数量 k 直接影响布隆过滤器的误判率：

当哈希函数的数量较少时，虽然可以减少位被设置为 1 的数量，但不同元素之间的冲突会增加，从而提高误判率。
当哈希函数的数量较多时，虽然减少了冲突的可能性，但每个元素会占用更多的位，位数组中的位更容易被设置为 1，从而导致误判率增加。

哈希函数的数量 k 的最佳值可以通过以下公式估计：

k=\frac{m}{n} \ln 2

其中：

m 是位数组的大小。
n 是添加到布隆过滤器中的元素数量。

该公式表示在一定的 m 和 n 下，最优的哈希函数数量 kkk 能够最小化误判率。

📨3. 插入的元素数量（n）

插入到布隆过滤器中的元素数量 n 越多，位数组中被设置为 1 的位置就越多，未被占用的位就越少。这会增加新元素的哈希值与已有位的重合几率，从而增大误判率。

当 n 增加到接近或超过位数组的容量时，误判率会显著上升。为此，在设计布隆过滤器时通常会根据预计的元素数量 n 来设定适当的位数组大小 m 和哈希函数数量 k。

📨4. 哈希函数的质量

哈希函数的质量也会影响布隆过滤器的误判率。理想情况下，哈希函数应当将元素均匀地映射到位数组的各个位置，避免哈希值的聚集。但如果哈希函数分布不均匀，则会导致某些位置上的碰撞频率增加，从而提高误判率。

选择高质量的哈希函数（如 MurmurHash、MD5 等）可以减少冲突，均匀地分布元素，降低误判率。

📨5. 布隆过滤器误判率的公式

布隆过滤器的误判率 P 可以通过以下公式计算：

P = \left(1 - e^{-\frac{k \cdot n}{m}}\right)^k

其中：

m 是位数组的大小。
k 是哈希函数的数量。
n 是插入的元素数量。
e 是自然对数的底，约等于 2.718。

这个公式表示，当插入的元素数量 n 较大、位数组较小 m 较小时，误判率 P 会显著增大。可以通过调整 m、k 和 n 之间的比例来控制误判率。

总结

布隆过滤器的误判率受到以下因素的共同影响：

位数组大小（m）：位数组越大，误判率越低。
哈希函数数量（k）：最优的哈希函数数量可通过公式计算。
插入的元素数量（n）：插入的元素越多，误判率越高。
哈希函数的质量：高质量的哈希函数能减少冲突，降低误判率。

设计布隆过滤器时，需要根据具体场景下的需求，合理选择位数组大小、哈希函数数量和预计的元素数量，以找到最优的误判率和内存占用平衡点。

📩2.3.4 布隆过滤器的删除

在布隆过滤器中，删除操作是非常困难的，因为它的设计不支持单独删除元素。这里的原因和解决方案如下：

📨1. 为什么布隆过滤器不能直接删除

布隆过滤器的本质是将元素通过多个哈希函数映射到一个位数组中的多个位置，并将这些位置的位设置为 1。问题在于：

布隆过滤器的每个位可能会被 多个不同的元素 设置为 1。
当试图将某个位重置为 0 时，可能会误删其他元素的映射位，这样会导致误判，即一个实际存在的元素被误判为“可能不存在”。

例如，假设有两个元素 A 和 B，它们通过不同的哈希函数映射到某个位 5。如果我们想删除 A，将位 5 重置为 0，就会导致 B 的存在性检查出错，因为它的哈希映射位也被重置了。

因此，在传统的布隆过滤器中 无法单独删除元素。

📨2. 实现布隆过滤器删除的替代方案：计数布隆过滤器（Counting Bloom Filter）

为了实现删除功能，可以使用一种变体 计数布隆过滤器（Counting Bloom Filter）。计数布隆过滤器在位数组的基础上，将每个位改为一个计数器，用于记录被哈希函数映射的次数。

计数布隆过滤器的工作原理

添加元素：当插入一个元素时，计数布隆过滤器通过多个哈希函数计算出多个位置索引，并将这些位置上的计数器 加 1。
查询元素：当查询一个元素是否存在时，计数布隆过滤器检查每个索引位置的计数器是否 大于 0。如果所有计数器都大于 0，则该元素可能存在；如果有任一计数器为 0，则元素肯定不存在。
删除元素：当删除一个元素时，计数布隆过滤器通过多个哈希函数计算出多个位置索引，并将这些位置的计数器 减 1。如果某个计数器的值变为 0，表示该位置不再被任何元素映射。

计数布隆过滤器的示例

假设位数组的大小为 m = 10，有 k = 3 个哈希函数，并且每个位存储一个计数器：

添加元素：添加元素 A，使用 k = 3 个哈希函数映射到三个位置，例如位置 2, 4, 7。将位置 2, 4, 7 的计数器加 1。

位数组计数器（添加 A 后）：0 0 1 0 1 0 0 1 0 0

删除元素：删除元素 A，使用相同的哈希函数映射到位置 2, 4, 7。将位置 2, 4, 7 的计数器减 1。

位数组计数器（删除 A 后）：0 0 0 0 0 0 0 0 0 0

通过计数布隆过滤器，我们可以安全地删除元素，而不会影响其他元素的存在性判断。

如果大家想更加清晰地了解布隆过滤器的删除，可以参考这篇文章 Counting Bloom Filter 的原理和实现

📧2.4 哈希表相比于布隆过滤器的缺点

📩2.4.1 内存占用较大

HashMap 为了实现快速查询，通常需要为每个元素分配一定的内存空间。在数据量巨大的情况下，这会导致 HashMap 占用大量内存。例如：

如果有 10 亿个元素，每个键值对的内存占用约为 8~16 字节，HashMap 可能会占用数 GB 的内存。
布隆过滤器则通过位数组和哈希函数组合，在保证误判率的情况下使用更少的内存，比如仅需数百 MB。

适用场景：布隆过滤器在 内存有限 的环境中更具优势，能够在低内存消耗下判断元素“可能存在”或“肯定不存在”。

📩2.4.2 无法控制内存空间和误判率之间的平衡

HashMap 使用了固定的哈希存储结构，每个元素必须占用一定的内存空间，这样的结构虽然能保证查询结果的准确性，但无法通过调节参数来降低内存消耗。

布隆过滤器可以通过调节位数组大小和哈希函数数量，灵活地在 内存消耗 和 误判率 之间找到平衡点。误判率可以被精确控制在可接受的范围内（如 0.1%、1% 等）。

适用场景：在可以接受一定误判率的场景中，布隆过滤器更节省空间。

📩2.4.3 不适合处理海量数据

HashMap 结构的空间复杂度通常为 O(n)，即数据量越大，内存占用越多。因此，在数据规模巨大的情况下，HashMap 不一定能够完全加载到内存中，从而影响性能甚至导致系统崩溃。

布隆过滤器对数据量不敏感，即使集合中的元素非常多，它的位数组也可以维持相对较小的空间，而不会显著增加内存占用。

适用场景：布隆过滤器在 数据规模较大 时表现更优越。

📩2.4.4 不支持快速去重操作

HashMap 的主要作用是键值对存储和查询，不擅长快速去重。对于海量数据去重，HashMap 需要占用大量内存来存储所有元素，从而不具备空间效率。

布隆过滤器可以高效判断元素是否已存在，并在大多数场景中将新元素的重复概率降到可接受的范围，非常适合用于去重操作（如 URL 去重、日志去重）。

适用场景：在 数据去重 场景中，布隆过滤器可以在极少内存占用的情况下完成去重。

📩2.4.5 不适合用于“可能存在”查询

HashMap 对每个查询返回准确结果，无法用于“可能存在”的场景，这可能带来额外开销。例如，当系统查询数据库或缓存时，如果查找频繁且数据规模大，直接使用 HashMap 可能增加系统负担。

布隆过滤器适合用于“存在性查询”，并且可以迅速判断元素是否 可能存在，从而避免不必要的后续查询（如数据库查询），提高系统性能。

适用场景：在需要快速判断“可能存在”与“确定不存在”的场景中，布隆过滤器更为高效。

📩2.4.6 计算复杂度和哈希冲突问题

HashMap 的插入和查询复杂度在理想情况下是

O(1)

，但在哈希冲突较多时可能退化为

O(n)

。在海量数据中，哈希冲突不可避免，尤其是当 HashMap 负载因子过高时（即存储的数据量接近 HashMap 容量），冲突会显著增加。

布隆过滤器在插入和查询时，复杂度同样为

O(k)

，其中 k 为哈希函数的个数。因为布隆过滤器仅设置和检查位数组中的位，不存储具体的键值数据，因此不受哈希冲突的影响，表现更加稳定。

适用场景：在极大规模的查询下，布隆过滤器能够保持稳定性能。

📩2.4.7 总结对比

特性	布隆过滤器	HashMap
空间占用	较小，可调节	较大，随数据量增长
误判率	允许控制的假阳性	无误判（精确判断）
支持的数据量	极大，适合海量数据	较大，但容易耗尽内存
应用场景	快速去重、存在性判断	精确查找、键值对存储
删除操作	不支持	支持
查询性能	稳定，不受哈希冲突影响	冲突较多时性能可能降低

总结

布隆过滤器和 HashMap 各有优缺点，适用场景不同：

布隆过滤器 适合需要 快速存在性查询 和 低内存消耗 的场景，如缓存层查询、URL 去重等，但不适合需要精确判断和删除元素的情况。
HashMap 适合需要 精确查找 的场景，如数据存储、键值对映射等，但在海量数据和内存有限的环境下，布隆过滤器更具优势。

如果你的场景可以接受一定的误判且不需要删除操作，并且内存资源有限，布隆过滤器会是一个更高效的选择。

📮三、哈希切分

哈希切分（Hash Partitioning）是一种分治策略，用于将一个大数据集划分为若干较小的子集，以便在有限的内存或处理能力下逐步处理大数据。这种思想广泛应用于大数据处理、数据库查询优化、分布式计算等场景。

📧3.1 哈希切分的基本思想

哈希切分的核心思想是：将数据通过哈希函数映射到不同的分区中。具体而言，对数据中的每个元素使用哈希函数计算一个值，然后根据哈希值将元素分配到不同的子集合或桶（分区）中。

📧3.2 哈希切分的步骤

假设有一个数据集 A，我们希望将它分为 N 个子集或分区 A_0, A_1, ..., A_{N-1}，步骤如下：

选择哈希函数：选择一个合适的哈希函数 hash(x)，可以是一个简单的哈希函数（如取模运算）或其他复杂的哈希算法。
计算分区索引：对于数据集中的每个元素 x，使用哈希函数 hash(x) 计算出一个哈希值，将其映射到分区 A_i。具体做法是对 hash(x) 的结果取模 N：

i=hash(x)

%N 其中 i 是分区编号，范围为 0 到 N-1。

分配数据：根据计算出的分区编号 i，将元素 x 存入对应的子集 A_i。

通过这种方式，数据集 A 被划分成了 N 个较小的子集，每个子集可以单独处理。

📧3.3 哈希切分的应用场景

大数据集的交集、并集、差集计算：在计算两个大数据集 A 和 B 的交集时，可以分别将 A 和 B 进行哈希切分，使得每个分区的数据量显著减少。然后在对应分区内计算交集，最后合并各个分区的交集即可得到最终结果。
数据去重：在大规模数据去重问题中，哈希切分可以将数据分布到不同的分区，每个分区内独立进行去重，最后合并去重后的结果。
分布式计算：在分布式系统中，哈希切分可以用于将任务划分到不同的节点上，实现负载均衡。各节点分别处理自己分区内的数据，最后将结果汇总。
数据库分区：数据库中常用哈希切分将数据分布到不同的物理存储上，提升查询效率，同时实现负载均衡。

📧3.4 哈希切分的优缺点

优点：

降低内存和处理压力：通过分区使得每次处理的数据量减少，能够在内存有限的情况下处理更大的数据集。
分布式处理：可以将不同的分区分配给多个节点或线程并行处理，提高计算速度。
简单高效：哈希函数计算简单，能够高效地将数据分布到不同分区中。

缺点：

不适合更新频繁的场景：如果数据频繁更新，分区会导致数据重新分布，增加维护开销。
分区不均匀问题：如果哈希函数设计不当，可能会导致数据分布不均匀，影响并行效率。
丢失顺序信息：哈希切分会打乱数据的顺序，对于需要顺序访问的数据处理场景并不适用。

📧3.5 哈希切分的应用

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

**思路一：**首先假设一个 query 占用 30Byte，那么100亿个 query 就会占用3000亿Byte，1G近似10亿Byte，所以3000亿Byte差不多就是300G。这里直接去遍历 A 中的元素再到 B 中去查找是不现实的，我们可以将这两个大文件分成若干份小文件，这里就将每个文件按照大小平均分成1000个小文件（A0-A999、B0-B999），这样以来每个小文件的大小就是300MB，然后我们可以依次拿着A0-A999这1000个小文件，去和B0-B999这1000个小文件进行对比，有相同的就放进交集。但是这样做的问题在于，A0~A999的每一个小文件都要和B的所有小文件对比一遍，这样效率也十分的低。所以下面我们引出哈希切分的方法。

**思路二（哈希切分）：**大思路上还是将 A 和 B 这两个大文件进行切分。但是并不再按照上面的内存大小进行平均切分，而是采用哈希切分。所谓哈希切分就是：根据一个哈希函数去计算确定将该元素划分到哪一个小文件里，可以采取下面这个公式进行计算：

hashi=HashFunc(query) % 1000

。最终每个文件中存放的都是 hashi 相同的元素，这里的一个小文件就类似于一个哈希桶，里面的这些元素只有两种可能：重复、冲突。将 A 和 B 文件都采取相同的方式进行划分，最终 A 和 B 中相同的 query 一定会分别进入 Ai 和 Bi 编号相同的小文件。接下来我们只需要去对比 Ai 和 Bi 即可，这样效率会大大提高。这种做法还是存在一些小问题，有可能出现一个小文件中数据过多的情况，这样就不满足题目中的内存要求了。一个小文件中数据过多有以下两种情形：

比如 Ai 有 5G 数据，其中有 4G 都是相同的 query（即重复数据），还有 1G 是不同的 query（即冲突数据）。
基本上都是不同的数据（即冲突数据）。

针对这两种情形提出以下解决方案：

先把 Ai 的 query 读到一个 set 里面，如果 set 的 insert 报错抛异常（bad_alloc，内存错误），那么就说明该小文件中大多数 query 都是不相同的（即冲突）。如果能够全部读出来，insert 到 set 里面，那么说明 Ai 里面大部分都是相同的 query（这里利用了 set 可以去重的机制）
如果抛异常，说明有大量冲突，就再换一个哈希函数，进行二次切分。

**注意：**这道题中的 query 不是整数，不适合使用位图来解决。使用哈希切分的目的就是为了满足内存限制，切分后再使用 set，对小文件的数据做进一步处理，如果小文件中都是重复的数据，set 会起到去重的作用，如果小文件中都是不相同的冲突数据，set 会抛异常，那么我们就再找一个哈希函数对该小文件继续切分。最终再用 set 去查找在不在，这样还可以做到精确查找。要做近似查找，直接使用布隆过滤器即可。

题目2：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

**思路：**这道题还是采取哈希切分的方法去完成。用一个哈希函数将 100G 大小的文件分成若干份小文件，相同的 IP 一定会被划分到同一个小文件中，然后再用一个 map 去统计出每一个小文件中 IP 出现的次数。记录下出现次数最多的即可。 解决方案：

1. 哈希切分：

使用哈希函数 hash(IP) % N 将日志文件中的 IP 地址分成多个小文件 part_0, part_1, ..., part_{N-1}，其中 N 是一个合适的分区数量，使得每个分区的文件大小可以被内存容纳（例如几百 MB 或 1GB）。
对于每个 IP 地址，根据哈希值将其写入对应的分区文件中。这样可以确保相同的 IP 地址都在同一个分区文件中。

2. 统计每个分区的 IP 频次：

依次将每个分区文件 part_i 加载到内存中，使用哈希表（例如 std::unordered_map 或 Python 的 dict）统计该分区文件中每个 IP 的出现次数。
对于分区 part_i，找到出现次数最多的 IP 地址，并记录该 IP 地址及其出现次数。
记录每个分区的最多出现次数的 IP。

3. 合并结果：

经过步骤 2 后，每个分区都有一个“出现次数最多的 IP 地址”和对应的出现次数。
比较所有分区结果中出现次数最多的 IP，即为全局出现次数最多的 IP。

结语

希望通过这篇文章，你能体会到哈希技术的精妙之处，也能将这些知识应用到实际场景中，为项目注入新的活力。在大数据的世界里，每一个小小的优化，都可能成就巨大的提升。让我们继续探索数据的奥秘，在哈希的世界中，书写更高效的未来。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-18，如有侵权请联系 cloudcommunity@tencent.com 删除

数据

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！