哈希扩展:位图与布隆过滤器

发布时间:2023年12月18日

1. 位图

1.1 位图引入

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

很经典的判断在不在的模型,那么可以使用set吗?答案是不可以的,40亿个整数大概需要16G的内存空间来进行存储,一般而言操作系统是不能也无法开辟这么大的空间,因此这种数据量大且仅需判断在不在的场景可以使用位图来解决。

数据是否在给定的整形数据中,结果是在或者不在,刚好是两种状态,那么可以使用一个二进制比特位来代表数据是否存在的信息,如果二进制比特位为1,代表存在,为0代表不存在。比如:
在这里插入图片描述
一个整形能表示数的个数为2的32次方,因此就需要这么多个比特位来表示,换算成字节为2的29次方也就是500MB左右,500MB系统是可以开出来的。

若有负数的情况,需要做一次相对映射,让其加上一个数变成正数,其余所有数字都需要加上这个数,然后判断某个值是否存在则需要再减去这个数得到它的真实值即可

1.2 位图概念

所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。

1.3 位图的模拟实现

//位图的模板参数为非类型模板参数
//用来表示数的总范围
template<size_t N>
class bitset
{
public:
	bitset()
	{
		// 先开辟空间
		_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);
	}

	// 第x个比特位个标记成0
	void reset(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		_a[i] &= (~(1 << j));
	}
	// 检测第x个比特位是0还是1
	bool test(size_t x)
	{
		size_t i = x / 32;
		size_t j = x % 32;
		return _a[i] & (1 << j);
	}
private:
	// 由于要用到移位运算符,因此参数类型必须是整形家族的
	//若使用char则上面所有/或%32的位置都要改成8
	//因为char占8个比特位
	vector<int> _a;
};

1.4 位图相关问题

  1. 给定100亿个整数,设计算法找到只出现一次的整数?

一个比特位只能表示两种状态,即在不在,无法统计对应数字的出现次数,而两个比特位则可以表示出四种状态,00 01 10和11,因此可以使用两个比特位即两个位图来统计次数,规定00代表没有出现,01代表出现一次,10代表两次及以上。

代码实现:

template<size_t N>
class twoBt {
public:
	void set(size_t x) {
		//如果是00则置为01,表示出现一次
		if (!b1.test(x) && !b2.test(x)) {
			b2.set(x);
		}
		//如果是01则置为10,表示出现次数≥2次
		else if (!b1.test(x) && b2.test(x)) {
			b1.set(x);
			b2.reset(x);
		}
		//其它情况均表示大于2次无需出口i
	}

	//判断是否出现一次,即为01
	bool isOnce(size_t x) {
		return !b1.test(x) && b2.test();
	}

private:
	//使用两个位图
	bitset<N> b1;
	bitset<N> b2;
};
  1. 给两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件交集?

一种方法是建立一个位图,然后将一个文件中的数据依次set到对应的位置,然后再依次检测另一个文件中的数据,看该数据对应要set的位置是否为1,若为1说明前面一个文件中出现了和当前相同的元素,就是交集,此时需要把该位置的值reset一下即置成0,因为可能会出现重复的值,但是交集没有重复,相当于去重。
另一种方法是建立两个位图,把两个文件中的数据依次set到对应位图中,然后遍历两个位图,若两个位图中的同一个位置都为1说明是交集,使用两个位图天然就完成了去重操作。

代码实现:

//使用第二种方法:
int main() {
	int a1[] = { 1,1,2,2,3,4,5,5,6 };
	int a2[] = { 3,5,7,9 };

	bit::bitset<10> b1;
	bit::bitset<10> b2;

	for (int x : a1) {
		b1.set(x);
	}
	for (int x : a2) {
		b2.set(x);
	}

	for (int i = 0; i < 10; ++i) {
		if (b1.test(i) && b2.test(i)) {
			cout << i << ' ';
		}
	}
	cout << endl;
	return 0;
}
  1. 位图应用变形:1个文件有100亿个int,1G内存,设计算法找到出现次数不超过2次的所有整数。

和第一问非常类似,直接上代码:

template<size_t N>
class twoBt {
public:
	void set(size_t x) {
		//如果是00则置为01,表示出现一次
		if (!b1.test(x) && !b2.test(x)) {
			b2.set(x);
		}
		//如果是01则置为10,表示出现两次
		else if (!b1.test(x) && b2.test(x)) {
			b1.set(x);
			b2.reset(x);
		}
		//如果是10则置成11,表示出现三次及以上
		else {
			b1.set(x);
			b2.set(x);
		}
	}
	
	//判断出现0、1和2次
	//00、01和10
	bool isValid(size_t x) {
		return (!b1.test(x) && !b2.test(x)) || (!b1.test(x) && b2.test(x)) || (b1.test(x) && !b2.test(x));
	}
private:
	bitset<N> b1;
	bitset<N> b2;
};

1.5 位图的应用

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记

2. 布隆过滤器

位图一般应用在判断整形数据是否存在的场景,得到的结果一定准确,若为字符串(或其它自定义)类型则得到的结果就不一定准确了,会存在误判的可能性,因为不同的字符串通过哈希函数得到的映射位置可能是一样的,这样便导致了冲突造成误判,如何有效缓解误判问题呢?

2.1 布隆过滤器概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

将哈希与位图结合,即布隆过滤器

需要注意的是,即使是布隆过滤器也无法完全杜绝误判的存在,只能降低误判率

2.2 模拟实现

#include <iostream>
#include <bitset>
using namespace std;
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;
    }
};

namespace bit {
	template<size_t N,
			 class K = string,
			 class hashFunc1 = BKDRHash,
			 class hashFunc2 = APHash,
		     class hashFunc3 = DJBHash>
        class BloomFilter {
        public:
            void set(const K& key) {
                size_t hashi1 = hashFunc1()(key) % N;
                _bs.set(hashi1);

                size_t hashi2 = hashFunc2()(key) % N;
                _bs.set(hashi2);

                size_t hashi3 = hashFunc3()(key) % N;
                _bs.set(hashi3);
            }

            bool test(const K& key) {
                //计算出对应存储位置
                //只要有一个位置是0就是不存在
                size_t hashi1 = hashFunc1()(key) % N;
                if (!_bs.test(hashi1))
                    return false;

                size_t hashi2 = hashFunc2()(key) % N;
                if (!_bs.test(hashi2))
                    return false;

                size_t hashi3 = hashFunc3()(key) % N;
                if (!_bs.test(hashi3))
                    return false;

                //依旧是存在误判
                //不存在的值可能会返回true
                return true;           
            }

        private:
            bitset<N> _bs;
    };
}

一般而言,布隆过滤器是不支持删除的,因为简单的把某个位置置成0有可能会影响其它值的判定,比如x和y都映射到了1位置,若删除x,把1位置置成0则会影响到y的判定,y存在但是查找y会得到不存在的结果。

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

布隆过滤器的优势之一就是空间损耗小,若像上述支持删除功能的话就相当于把这个优势给抹掉了,需要酌情考虑

2.3 布隆过滤器相关问题

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

设两个大文件的名称分别为A文件和B文件。

近似算法:把A文件中的数据全部放进布隆过滤器,然后逐个检测B文件中的数据是否在过滤器中,如果不在那一定不是交集,如果在,很有可能就是交集,因为还存在小概率误判。

精确算法:可以将其分别平均分割成N份小文件(每个文件大小为几百兆即可),然后把A文件中数据依次放入每个小文件中,然后依次拿A的每个小文件中的数据与B的每个小文件中的数据依次比对,相同就是交集,但是这种比对的效率很低,如果要提高效率则需要用到哈希切分

2.3.1 哈希切分

同样是将其分割成N份小文件(无需平均分割),编号为0~N,把A和B文件中的query依次通过哈希函数计算出一个位置i,然后将该query数据放入编号为Ai(或者Bi)的小文件中,由于使用的是相同的哈希函数,因此A和B文件中相同的query数据必然分别会存放到对应相同编号的小文件中(但也可能包含冲突的query)。

这里与哈希桶非常相似,每个相同的数据必然进入同一个桶,但是桶中不一定都是相同的数据,还可能包含不同但冲突的数据

切分完毕后,找交集,只需要把Ai文件中的数据依次放入哈希表中,然后再用Bi中的数据依次检测是否存在,在就是交集再把其从表中删除(防止重复),这种做法极大的提高了比对效率,那还有什么问题没?

问题是每个小文件并不是平均切分的,因此可能某个小文件相同的或者冲突的query过多导致文件过大,该怎么办?

解决方案如下:先把该文件中的数据读出来放入一个set中,若set报错抛异常(bad_alloc),那么说明该文件数据的冲突太多,set放不下了,这种情况则需要换个哈希函数继续对其进行切分,重新对数据进行映射。
若能够全部放进set中,则说明该文件中有大量相同的数据,这种情况直接进行比对即可。

还有一个与其类似的问题:
给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?与上题条件相同,如何找到top K的IP?

同样使用哈希切分,切分成若干份小文件,把每个IP地址数据通过哈希函数计算出一个编号i,将其存进对应编号的小文件中,然后使用哈希表依次统计每个小文件中每个数据的出现次数,并且每统计一个文件都要更新出现次数最多的那个IP地址数据,全部文件统计完成后即可找到出现次数最多的那个IP地址。

而统计topK则需要再加个小堆结构来处理。

同样会出现某个小文件过大的问题,但是解决方法是一样的

文章来源:https://blog.csdn.net/weixin_66672501/article/details/135023983
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。