??

目錄

一，位圖

1. 位圖概念

2.實(shí)現(xiàn)

3. 測(cè)試題

位圖的優(yōu)缺點(diǎn)

二，布隆過(guò)濾器

1). 布隆過(guò)濾器提出

2). 概念

3). 布隆過(guò)濾器的查找

4). 布隆過(guò)濾器刪除(了解)

5). 布隆過(guò)濾器優(yōu)點(diǎn)

6).?布隆過(guò)濾器缺陷

三，海量數(shù)據(jù)面試題

1）哈希切割

一，位圖

我們首先由一道面試題來(lái)理解位圖

給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在

這40億個(gè)數(shù)中?！掘v訊】

40億無(wú)符號(hào)整形，我們知道1G大概是10億個(gè)字節(jié)，也就是說(shuō)起碼 16G數(shù)據(jù)，排序，二分查找都需要在內(nèi)存下進(jìn)行，16G的內(nèi)存性價(jià)比著實(shí)有些低。而我們使用位圖的方法，用40億個(gè)比特位來(lái)表示這40億個(gè)數(shù)是否存在，大概就是要消耗 512MB(40億bit? ==? 5億字節(jié) == 512MB)的內(nèi)存。

注意：

1. 位圖概念

2.實(shí)現(xiàn)

#include <iostream>
#include <vector>
using namespace std;

template < size_t N>
class bitset
{
public:
	bitset()
	{
		_bit.resize(N / 8 + 1, 0); // + 1防止有越界
	}

	// 映射的比特位設(shè)置為1
	void set(size_t x)
	{
		size_t spa_bit = x / 8;
		size_t in_bit = x % 8;

		_bit[spa_bit] &= (1 << in_bit);
	}

    // 映射的比特位設(shè)置為0
	void reset(size_t x)
	{
		size_t spa_bit = x / 8;
		size_t in_bit = x % 8;
	}

    // 測(cè)試x,是否存在
	bool test(size_t x)
	{
		size_t spa_bit = x / 8;
		size_t in_bit = x % 8;
		return _bit[spa_bit] & (1 << in_bit);
		// 返回0: 則不存在
		// 返回一個(gè)很大的數(shù)：存在
	}

private:
	vector<char> _bit;
};

測(cè)試案例：

?再回到題目，我們知道有40億個(gè)數(shù)，我們知道這只是數(shù)量，不是范圍，所以，我們盡量開(kāi)到無(wú)符號(hào)的最大值，在開(kāi)大小的時(shí)候我們可以這么來(lái)設(shè)置：

bitset<-1>? st? 或者? bitset<0xffffffff> st;

3. 測(cè)試題

template <size_t N>
class two_set
{
public:
	void set(size_t x)
	{
		if (st1.test(x) == false
			&& st2.test(x) == false)
		{// 00 -> 01 情況
			st2.set(x);
		}
		else if (st1.test(x) == false
			&& st2.test(x) == true)
		{// 01 -> 10 情況
			st1.set(x);
			st2.reset(x);
		}
	}
private:
	// 我們用 01，00，10 表示三種情況
	bitset<N> st1; // 記錄第一位 
	bitset<N> st2; // 記錄第二位
};

template <size_t N>
class cross_set
{
public:
	void set1(size_t x)
	{
		st1.set(x);
	}

	void set2(size_t x)
	{
		st2.set(x);
	}

	void test()
	{
		for (size_t i = 0; i < N; i++)
		{
			if (st1.test(i) && st2.test(i))
				cout << i << " ";
		}
	}

private:
	bitset<N> st1;
	bitset<N> st2;
};

class cross_set2
{
public:
	void set(size_t x )
	{
		st.set(x);
	}

	void test(size_t x)
	{
		if (st.test(x))
		{
			cout << x << " ";
			st.reset(x); //第一次檢測(cè)完后設(shè)置為0
		}
	}
private:
	bitset<N> st;
};

思想：還是用2個(gè)位圖，用 00 , 01, 10, 11 表示這四種狀態(tài)，跟第1題類(lèi)似。

位圖的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：速度快，節(jié)省空間。

缺點(diǎn)：只映射整型，像浮點(diǎn)數(shù)，string等類(lèi)不能作為存儲(chǔ)，進(jìn)行映射。

二，布隆過(guò)濾器

1). 布隆過(guò)濾器提出

2). 概念

哈希的詳細(xì)知識(shí)點(diǎn)，請(qǐng)查看本篇文章：?詳解布隆過(guò)濾器的原理，使用場(chǎng)景和注意事項(xiàng) - 知乎 (zhihu.com)

使用布隆過(guò)濾器，優(yōu)點(diǎn)之一是節(jié)省空間。雖然哈希函數(shù)個(gè)數(shù)越多，沖突的概率越低；但占用的平均內(nèi)存也會(huì)提高

然后就是當(dāng)我們的哈希函數(shù)為3時(shí)，過(guò)濾器的長(zhǎng)度與插入個(gè)數(shù)的關(guān)系。（K是哈希函數(shù)個(gè)數(shù)，m是長(zhǎng)度，n是插入個(gè)數(shù)）

?

根據(jù)里面提供的關(guān)系可以得出， 布隆過(guò)濾器長(zhǎng)度應(yīng)是插入個(gè)數(shù)的 5 倍

3). 布隆過(guò)濾器的查找

4). 布隆過(guò)濾器刪除(了解)

關(guān)于哈希函數(shù)的選擇，我們參考這篇大佬hash函數(shù)算法博客的推薦：各種字符串Hash函數(shù) - clq - 博客園 (cnblogs.com)

// 三個(gè)哈希函數(shù)

struct APHash
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (long 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 BKDRHash
{
	size_t operator()(const string& str)
	{
		size_t hash = 0;
		for (auto e : str)
		{
			hash += (size_t)e;
			hash *= 31;
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& str)
	{
		if (!str[0])   // 這是由本人添加，以保證空字符串返回哈希值0  
			return 0;
		size_t hash = 5381;
		for (auto e : str)
		{
			size_t ch = size_t(e);
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

template <size_t N, class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class bloom_set
{
public:
	// 插入
	void set(const string&  str)
	{
		Hash1 hash1;
		size_t len = N * time;
		st.set(hash1(str) % len);

		Hash2 hash2;
		st.set(hash2(str) % len);

		Hash3 hash3;
		st.set(hash3(str) % len);
	}

	// 判斷是否存在
	// 1. 如果其中一個(gè)不存在，那么一定不存在
	// 2. 如果三位置都存在，那么可能存在，需要確認(rèn)
	bool test(const string& str)
	{
		Hash1 hash1;
		Hash2 hash2;
		Hash3 hash3;
		size_t len = N * time;
		if (!st.test(hash1(str) % len))
			return false;

		if (!st.test(hash2(str) % len))
			return false;

		if (!st.test(hash3(str) % len))
			return false;

		return true; // 都存在，那可能存在
	}
private:

	static const size_t time = 5;  // 過(guò)濾器長(zhǎng)度與插入個(gè)數(shù)關(guān)系
	bitset < N * time > st;
};

5). 布隆過(guò)濾器優(yōu)點(diǎn)

6).?布隆過(guò)濾器缺陷

三，海量數(shù)據(jù)面試題

1）哈希切割

1. B3有一種query大量重復(fù)，無(wú)法進(jìn)行切割。

2. B3中有大量不同，可以切割。

如果插入2.5G的內(nèi)存，一定會(huì)報(bào)內(nèi)存不足的問(wèn)題，而這個(gè)就是 情況2，出現(xiàn)這個(gè)我們可以更換哈希函數(shù)，對(duì)小文件進(jìn)行再次進(jìn)行切割。

如果插入2.5G的內(nèi)存，沒(méi)有內(nèi)容不足的問(wèn)題，那么就是情況1。

下期預(yù)告： C++11 ！?。?/h3>

到了這里，關(guān)于哈希思想應(yīng)用【C++】(位圖，布隆過(guò)濾器，海量數(shù)據(jù)處理面試題)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！