在億級數據處理場景中，「快速判重」始終是繞不開的核心痛點——傳統數據結構要麼空間開銷爆炸，要麼查詢效率低下，難以平衡性能與資源成本。而位圖（BitMap）與布隆過濾器（Bloom Filter），正是解決這一難題的高效方案：位圖以比特級存儲實現精準判重，布隆過濾器則基於位圖優化，用概率模型突破數據範圍限制。

本文將從底層原理出發，拆解二者的關聯邏輯、核心差異，結合實戰場景講清如何用這兩個工具高效搞定億級數據判重，助力開發者優化系統性能、降低資源損耗。

一.位圖原理

位圖是一種基於比特位（Bit）存儲數據的高效數據結構，核心邏輯是用「單個比特位的0/1狀態」映射「數據是否存在」——將目標數據作為比特數組（BitArray）的索引，索引對應比特位為1表示數據存在，為0則表示不存在，本質是“用空間極致壓縮實現高效判重/存在性校驗”。

看一個問題：如果此時有40億個無序的無符號整數；然後，任意給出一個無符號整數，如何快速判斷這個數在40億數據當中存不存在？

問題分析

一般判斷數據存不存在的問題，我們可以使用"set"或者"排序+二分"[O(logN)]的方式，但是對於億級數據——以40億無符號整數數據為例: 需要佔160億Byte，大約16G；也就是説單單存儲數據就要佔16G內存！這顯然不是我們想要的。

換一種方式，如果只是查找一個數據存不存在，像哈希直接定址法一樣直接標記？但我們用去bit位標記。

對於一個整型: 32個bit位，如果每個bit位都代表一個數據，一個整型能表示32個數據，那麼40億數據需要125,000,000個整數(看上去還是很多，但只需要大約0.46G)；

如何實現比特數組

比特數組：以「比特（bit，0/1）」為最小單位的數組，1位存1個二元狀態（是/否、有/無），極致省內存，也就是常説的「位圖」。

template<size_t N>//非類型模板參數 -- 一開始就確定好開多大空間
class bitset
{
public:
	bitset()//開闢_a的空間
	{			
		_a.resize(N / 32 + 1);//除會把餘數捨去，多開一個
	}

	//把x映射的那個位映射成1
	void set(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;

		//就可以用位運算操作 -- 按位與/或/異或/反
		_a[i] |= (1 << j);//從0開始的所以是左移j位
	}

	//把x映射的那個位映射成0
	void reset(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;

		//!是邏輯取反
		_a[i] &= (~(1 << j));//按位取反 在與
	}

	bool Test(size_t x)//在不在 判斷是0是1
	{
		size_t i = x / 32;
		size_t j = x % 32;

		return _a[i] & (1 << j);//在 返回真
	}
private:
	//關於對bit的操作
	//位段 -- 找到一個bit的數據
	//位運算
	vector<int> _a;//vector默認構造不開空間 -- 自己再寫個構造
	//我們需要用的是bit位，但實際操作的是整型
	//若果映射 x = 80， i = x / 32 則在vector的第i個整型上面(注意下標從0開始)
	//                  j = x % 32 得到在這個第i整型的第幾個bit位上面
};

原理：用bit位去映射(直接映射的方式)，有為1，無為0； 通過x/32 與 x%32找到映射位置；

數據測試

int main()
{
	fx::bitset<1000> bs;
	bs.set(1);
	bs.set(5);
	bs.set(10);
	bs.set(100);
	//測試某數據是否在位圖中：
	cout << bs.Test(1) << endl;
	cout << bs.Test(10) << endl;
	cout << bs.Test(100) << endl;
	cout << bs.Test(88) << endl << endl;

	bs.reset(100);
	bs.reset(99);

	cout << bs.Test(10) << endl;
	cout << bs.Test(100) << endl;
	cout << bs.Test(88) << endl;
	return 0;
}

為便於講解，只檢測了幾個數據，但億級數據的處理也是一樣；唯一要注意，在實際應用中，位圖數據源幾乎都來自文件/數據庫，需要我們掌握文件操作等內容。

二.位圖的應用

問題一

給定100億整型數據，設計算法找到只出現一次的整數。

在面對大量數據時(查找/去重/計數)，首先考慮位圖的方法；但是上文只介紹了面對數據"存不存在"，也就是説只能判斷一個數據出現了，並不能體現出現幾次，面對“計數”情況，應該如何改進?

思路

• 用兩個bit位表示一個數據
• 用兩個bitset處理

以法②為例：

	template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			//00 -> 01
			if (!_bs1.Test(x) && !_bs2.Test(x))
			{
				_bs2.set(x);
			}//01->10
			else if (!_bs1.Test(x) && _bs2.Test(x))
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
			//如果要統計出現3次的數據
			/*else
			{
				_bs2.set(x);
			}*/
		}
		bool is_once(size_t x)
		{
			return !_bs1.Test(x) && _bs2.Test(x);//找01
		}
	private:
		bitset<N> _bs1;//會調用bitset的構造初始化
		bitset<N> _bs2;
	};

如此，我們需要統計出現"3次"、"4次"的數據，我們都可藉助位圖統計。

問題二-練習

給兩個文件各有100億數據，找交集。

思路提示

• 位圖標記一個文件內數據
• 遍歷第二個文件，尋找交集。
• (如果要解決重複數據而導致多次輸出的問題，可以增加第二個位圖，記錄已輸出的交集元素)

總結

位圖適用場景

•  海量整數存在性判斷

• 1bit標記存在狀態，極致省內存，查詢O(1)。

•  兩/多集合高效運算（交、並、差集）

• 位圖標記集合元素，通過位運算（&交集、|並集、^差集）快速計算，效率遠超哈希/排序。

•  整數排序（海量無重複整數）

• 位圖標記元素，按bit位順序遍歷輸出，時間O(n)，內存佔用極低。

• 統計元素次數

• 多個位圖/多個bit位協作計數

• 操作系統磁盤塊標記(標記空閒/佔用狀態)

 對於非整數且難唯一映射的數據(如複雜對象)或是數據範圍極大且不規則（如10¹⁸級整數，內存無法承載）,不適合使用位圖。

三.布隆過濾器

布隆過濾器: 是一種基於位圖與多哈希函數的概率型數據結構，用於高效判斷元素是否存在於集合中，以極小誤判率換取極致內存佔用與查詢效率，無漏判、不支持刪除。

誤判

誤判的唯一來源的是：「不同元素經哈希函數計算後，映射到了同一個存儲位置，導致系統無法區分這兩個元素，進而把“不存在的元素”誤判為“存在”」，本質是「哈希碰撞」引發的“位置佔用衝突”。

舉個例子：當多個字符串映射到某個位置時，不同字符映射可能用了相同的“數字”( 比如"abc"和"abd"映射方式是用首字母映射，這兩個字符串一定會映射到相同bit位上 )，本來不存在數數據被標記成了存在，出現誤判。

解決

在1970年：美國科學家伯頓·霍華德·布隆（Burton Howard Bloom）發表論文，首次提出布隆過濾器概念，核心是用位圖+多哈希實現高效存在性判斷—— 一個數據用多種方式映射到多個位置，這樣只有當多個位置都被標記時，才能證明該數據存在。

布隆過濾器應用

對於用位圖判斷字符串等數據存在性而言，它判斷不存在一定是準確的(為0肯定不存在)，而存在卻可能受到已有數據干擾，即使用布隆過濾器也無法完全保證不會出現誤判。所以布隆過濾器僅僅適用於"精確要求不高"的場景：

• 不需要精確的場景：如快速判斷暱稱是否註冊過（如果要精確：位圖也可作為第一層判斷，不在時直接返回(不存在判斷一定準確)，存在則去數據庫查找準確結果）。
• 過濾效果：和第一點"需精確"情況一樣，布隆過濾器用於快速將“不存在”情況過濾出去，提高效率。