【C++ 哈希应用】

位图

概念

一个值在给定的集合中有两种状态，在或不在，要表示这种状态，最少可以用一个比特位，比特位为1表示在，比特位为0表示不在。
位图中的比特位的位置表示编号，比特位的内容表示是否存在。

代码实现

	template<size_t N>
	class bitset
	{
	public:
		bitset()
			:_bits(N / 32 + 1)
		{}
		//设置某一位为1
		void set(size_t pos)
		{
			size_t x = pos / 32;
			size_t y = pos % 32;

			_bits[x] |= (1 << y);
		}
		//设置某一位为0
		void reset(size_t pos)
		{
			size_t x = pos / 32;
			size_t y = pos % 32;
			_bits[x] &= ~(1 << y);
		}
		//检测某一位的值
		bool test(size_t pos)
		{
			size_t x = pos / 32;
			size_t y = pos % 32;
			return _bits[x] & (1 << pos);
		}
	private:
		vector<int> _bits;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

海量数据处理

1. 给定100亿个整数，设计算法找到只出现一次的整数？
   使用两个位图标记出现的次数，(0, 0)表示出现0次，(0, 1)表示出现1次，(1,0)表示出现了两次及以上。
2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
   整形最多有UINT_MAX个数，按照一个数一个比特位来算，差不多需要512MB,所以只需要使用两个位图标记出现的次数，最后依次遍历每一位，如果都为1，就是交集
3. 1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数？
   结合题1和题2的思路，用1G内存创建两个位图，(0, 0)表示出现0次，(0, 1)表示出现1次，(1,0)表示出现了两次及以上。

布隆过滤器

概念

位图的位置表示编号，内容表示是否存在这个值。那如果我们想用位图来标示某一个字符串的存在呢，我们可以用字符串hash函数将字符串转换为对应的整型值，但是这个hash值可能会产生冲突。这时，有人提出一种思路，既然一个hash函数不能标定一个字符串是否存在，那么如果字符串用多个字符串hash函数映射在位图中，如果一个字符串的所有hash值在位图中都存在(对应值为1)，也不能肯定这个字符串真的存在，但如果有一个hash值在位图中不存在(对应值为0)，那么可以肯定这个字符串一定不存在。
通过加入更多的字符串hash函数，可以使得每个字符串即使冲突，也可以通过找不在位图中的hash值来快速判断一个字符串一定不存在。
注意：布隆过滤器一般不提供删除接口，因为删除之后可能存在冲突。

代码实现

template<size_t N, class HashFun1 = BKDRHash, class HashFun2 = APHash, class HashFun3 = DJBHash>
class BloomFilter
{
public:
    BloomFilter()
        :_bs(new bitset<N>)
    {}
    void set(const string& s)
    {
        size_t hash1 = HashFun1()(s) % N;
        _bs->set(hash1);

        size_t hash2 = HashFun2()(s) % N;
        _bs->set(hash2);

        size_t hash3 = HashFun3()(s) % N;
        _bs->set(hash3);
    }

    bool test(const string& s)
    {
        size_t hash1 = HashFun1()(s) % N;
        if (!_bs->test(hash1))
            return false;

        size_t hash2 = HashFun2()(s) % N;
        if (!_bs->test(hash2))
            return false;

        size_t hash3 = HashFun3()(s) % N;
        if (!_bs->test(hash3))
            return false;

        return true;
    }

private:
    bitset<N>* _bs;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

海量数据处理

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
   近似算法：使用布隆过滤器，将一个文件映射到布隆过滤器中，再遍历另一个文件，查找是否存在布隆过滤器中。这种方法存在误判。
   精确算法：哈希切分使用统一的字符串hash函数，分别将两个文件的所有字符串转换为对应的hash值，对于其中一个文件，创建N 个小文件，假设N = 10000，用字符串hash值 % N，最终将字符串写入对应的文件中，另一个文件也是同样的操作，这样相同的query一定会进入到相同编号的文件中，最后将相同编号的文件读入内存中，用set进行求交集。
   如果文件太大，有两种可能：a.文件中重复query太多，此时不需要处理，set自动去重 b.文件中不同的query太多，这是可以换一个字符串hash函数，再创建文件，将字符串映射到不同的文件中，进行操作。
2. 如何扩展BloomFilter使得它支持删除元素的操作？
   每个位位置上不再存储比特位，而是存储一个整形，当插入一个元素时，将其映射到的位的位置上的计数器加一；当删除一个元素时，将其映射到的位的位置上的计数器减一。

哈希切割海量数据处理

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？
哈希切分使用统一的字符串hash函数，分别将两个文件的所有字符串转换为对应的hash值，对于其中一个文件，创建N 个小文件，假设N = 1000，用字符串hash值 % N，最终将字符串写入对应的文件中，另一个文件也是同样的操作，这样相同的IP一定会进入到相同编号的文件中，最后将相同编号的文件读入内存中，用map进行记数求出出现次数最多的IP地址
如果文件太大，有两种可能：a.文件中重复IP太多，此时不需要处理，map自形解决即可 b.文件中不同的IP太多，这是可以换一个字符串hash函数，再创建文件，将字符串映射到不同的文件中，进行操作。
与上题条件相同，如何找到top K的IP？
维护一个小根堆即可