作者主页：进击的1++ 朗 专栏链接：【1++的数据结构】
文章目录
一，前言二，位图1. 位图2. 位图的应用
三，布隆过滤器
一，前言
上一节我们讲解了哈希表，简单的了解了哈希思想，这一节我们对哈希思想进行更深入的了解，对其应用进行学习。大家坐稳了，学习的快车又要发动了！！！
二，位图
1. 位图
什么叫位图呢？ 位图就是用每一位来存储一种状态。位是表示信息的最小单位，每一位存储一种状态，那么我们可以将每一位的状态与数据映射。那么便可以用较少的内存去处理海量的数据。通常用其判断某个数据存不存在。 接下来我们进行位图的实现: 来看代码：
template
class Bit_set
{
public:
Bit_set()
{
_bit_table.resize(N / 8 + 1, 0);
}
void set(const size_t& key)
{
//锁定位置
size_t i = key / 8;
size_t j = key % 8;
//将那一位置为1
_bit_table[i] |= (1 << j);
}
void reset(const size_t& key)
{
//锁定位置
size_t i = key / 8;
size_t j = key % 8;
//将那一位置为0
_bit_table[i] &= ~(1 << j);
}
bool test(const size_t& key)
{
//锁定位置
size_t i = key / 8;
size_t j = key % 8;
//检查那一位是否为1
return _bit_table[i] & (1 << j);
}
private:
vector
};
总的思路就是开一个有N个位大小的空间（N应该比元素集合中的最大值还要大），然后将数据（整型）映射到位图中的位置：即第几个char中的第几位,然后将其进行置1，置0,或是检查那位是否为1。
2. 位图的应用
快速查找某个数据是否在一个集合中 此题可直接使用位图，进行查找。排序 + 去重 由于位图只可以表示其状态（在或不在）因此其天生就有去重的特性，其排序，只需将我位图遍历一遍，便可以得到升序的元素集合。
void test2()
{
size_t N = 100;
Bit_set<100> s1;
int arr[] = { 1,5,3,7,0,10,9,8,3 };
for (auto& e : arr)
{
s1.set(e);
}
for (size_t i = 0; i < N; i++)
{
if (s1.test(i))
{
cout << i << endl;
}
}
}
求两个集合的交集、并集等 我们只需要创建两个相同大小的对象，然后各自进行set，最后一起遍历。。。。。
void test3()
{
size_t N = 100;
Bit_set<100> s1;
Bit_set<100> s2;
int arr1[] = { 1,5,3,7,0,10,9,8,3 };
int arr2[] = { 1,10,3,7,11,10,2,8,4 };
for (auto& e : arr1)
{
s1.set(e);
}
for (auto& e : arr2)
{
s2.set(e);
}
for (size_t i = 0; i < N; i++)
{
if (s1.test(i) && s2.test(i))
{
cout << i << endl;
}
}
}
找出现两次的元素 既然一个位只能表示一种状态，那么两个位是不是就能表示四种状态（一次没出现，出现一次，出现两次，出现两次以上）
template
class two_bit
{
public:
void set(const size_t& key)
{
if (_bits1.test(key) == false && _bits2.test(key) == false)
{
_bits2.set(key);
_bits1.reset(key);
}
else if (_bits1.test(key) == false && _bits2.test(key) == true)
{
_bits1.set(key);
_bits2.reset(key);
}
else
{
_bits1.set(key);
_bits2.set(key);
}
}
bool test(const size_t& key)
{
return (_bits1.test(key) == true && _bits2.test(key) == false);
}
private:
Bit_set
Bit_set
};
void test3()
{
two_bit<100> t1;
int arr[] = { 1,4,6,2,3,7,9,10,2,6,2 };
for (auto& e : arr)
{
t1.set(e);
}
cout< cout << t1.test(6) << endl; cout << t1.test(1) << endl; } 三，布隆过滤器 什么是布隆过滤器？ 布隆过滤器是用多个哈希函数，将一个数据元素映射到位图结构中。此方式不仅可以提升效率，也可以节省空间。 以下是布隆过滤器的实现： template class BloomFilter { public: void set(const K& key) { size_t len = N * 5; size_t hash1 = DJBHash()(key) % len; size_t hash2 = BKDRHash()(key) % len; size_t hash3 = APHash()(key) % len; _bitset.set(hash1); _bitset.set(hash2); _bitset.set(hash3); } void reset(const K& key)//普通的删除可能会影响其他值 bool test(const K& key) { size_t len = N * 5; size_t hash1 = DJBHash()(key) % len; size_t hash2 = BKDRHash()(key) % len; size_t hash3 = APHash()(key) % len; if (!_bitset.test(hash1)) return false; if (!_bitset.test(hash2)) return false; if (!_bitset.test(hash3)) return false; return true; } private: Bit_set }; 布隆过滤器的优点及其缺陷： 增加和查询元素的时间复杂度位O(K) K为哈希函数的个数。布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势数据量很大时，布隆过滤器可以表示全集，其他数据结构不能 缺点： 有误判，能够判定某一元素一定不在，但不能够判定该元素一定在。一般情况下不能够进行删除不能够获取元素本身 好文链接
发表评论