我们知道数据的最小存储位是比特(bite),每个比特位只能是0或1,我们用1和0来表示在或不在,或是其它类型的状态信息,这种结构称作位图。
当我们面对海量数据时,使用 int 类型来存储数据,会需要巨大的空间,这样成本就太高了,这种时候可以用位图来解决,它可以大幅降低所需空间。
库里面是有位图这个结构的,可以看到,有一个非类型模板参数,它决定位图的大小。
接下来让我们来模拟实现简易的位图,同样采用非类型模板参数的形式 。
位图是需要访问比特位的,但是我们没有任何一个类型的大小是一个比特位,所以我们可以开一个整型数组(当然char也行),一个整型就表示32个比特位,这样我们数组的大小只需要开 N/32+1 就行了。
set 的作用是把该比特位设置成1。
给我们一个数 x ,我们该如何把 x 映射到位图中呢,并把映射到的这个位置改成1(并且不改变其它位置)呢?
接下来使用位运算的知识将这个位置设置成1,并不影响其他位置。
我们知道按位或运算是只要有1就是1,所以按位或上一个0,并不影响原来的值,按位或上一个1结果为1。
void set(size_t x)
{
size_t i = x / 32; //求出在哪个字节
size_t j = x % 32; //求出在哪个比特位
bs[i] |= (1 << j);
}
reset 是把该位置的比特位设置成 0 。
这就要用到按位与了。
对于按位与运算,只要有0就是0,按位与上一个1并不影响原来的值。
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
bs[i] &= (~(1 << j));
}
判断一个位置的比特位是 0 还是 1
这里同样还是用按位与,但要注意是对某一个位置按位与上一个1,不用像 reset 一样取个反。
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return bc[i] &(1 << j); //注意不能写成 &=
}
template<size_t N>
class Bitset
{
public:
Bitset()
{
bs.resize(N / 32 + 1);
}
void set(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
bs[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
bs[i] &= (~(1 << j));
}
bool test(size_t x)
{
size_t i = x / 32;
size_t j = x % 32;
return bs[i] &(1 << j);
}
private:
vector<int> bs;
};
布隆过滤器的插入是利用多个哈希函数,将一个数据映射到一个位图的多个位置上,生活中,要插入的数据类型大多是字符串型,所以本篇文章将以插入字符串为例模拟实现布隆过滤器。
void set(const K& key)
{
size_t hash1 = Hash1(key) % N;
bs.set(hash1);
size_t hash2 = Hash2(key) % N;
bs.set(hash2);
size_t hash3 = Hash3(key) % N;
bs.set(hash3);
}
分别计算每个哈希值对应的比特位置存储的是否为零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。
注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可 能存在,因为有些哈希函数存在一定的误判。
所以布隆过滤器在实际应用中起到一个过滤器的作用,如果在的话还要到数据库里继续查找,防止误判,提高了效率;如果不在,就一定不存在,就不需要到数据库里取寻找。
一般情况下布隆过滤器是不支持删除的,因为布隆过滤器存储的时候是一对多,如果删除一个位置,那么很可能会影响其它的数据。
如果非要删除的话,只能再加一个位图来表示每个比特位为1的个数。
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;
size_t ch;
for (long i = 0; i < str.size(); i++)
{
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)
{
if (str.size() == 0)
return 0;
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;
bs.set(hash1);
size_t hash2 = Hash2(key) % N;
bs.set(hash2);
size_t hash3 = Hash3(key) % N;
bs.set(hash3);
}
bool test(const K& key)
{
size_t hash1 = Hash1(key) % N;
size_t hash2 = Hash2(key) % N;
size_t hash3 = Hash3(key) % N;
return bs.test(hash1)&& bs.test(hash2)&& bs.test(hash2)
}
private:
Bitset<N> bs;
};
给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出 精确算法和近似算法。
对于大文件,我们可以分成多个小文件,那该怎那么分呢?
首先一定不能均分,均分的效率极低,我们可以利用哈希表的原理来分。
如何找交集?
如果哈希冲突太多,会导致一个小文件的大小超过1个G,这该如何解决?
此时分两种情况:
解决方案:
这里有100亿个整数,如果用set,红黑树这一类的结构,空间必定不够。
所以就需要用位图解决。
但是一个比特位只能表示两种状态,怎么找到只出现一次的整数呢?
可以用两个链表,这样0和1两两组合就有四种状态:00 01 11 10
我们可以用:
可以复用 Bitset 来创建一个有两个位图的双位图结构。
template<size_t N>
class TwoBitset
{
public:
void set(size_t x)
{
if (bs1.test(x) == 0 && bs2.test(x) == 0) //00
bs2.set(x); //01
else if (bs1.test(x) == 0 && bs2.test(x) == 1) //01
bs1.set(x); //11
else
;
}
bool test(size_t x)
{
if (bs1.test(x) == 0 && bs2.test(x) == 1)
return true;
else
return false;
}
private:
Bitset<N> bs1;
Bitset<N> bs2;
};
还是和前面一样使用双位图,如果只把一个文件的数据映射到一个位图,另一个文件的数据用来遍历找交集的话,就会出现重复项。
把两个文件的数据分别映射到两个位图中,由于整形数据是有范围的,实际上在100亿个整数中,有非常多重复的,当两个文件的数据映射完成后,遍历所有整数,如果在两个位图中都在,那么这个数就是一个交集。这要做的好处是不会找到重复的数。
这题还是和第一题是一样的,只不过是找不超过2次的整数,可以: