一、位图
位图就是利用好每一个比特位进行利用
适用于海量数据,数据无重复的场景,通常用来判断数据是否存在
位图的作用有
排序,去重,集合的交并集
模拟实现
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #pragma once
#include<vector>
#include<iostream>
using namespace std;
namespace 9TSe
{
class bitset
{
public:
bitset(size_t N)
{
_bits.resize(N/32+1,0);
_num = 0;
}
void set(size_t x)
{
size_t index = x / 32;
size_t pos = x % 32;
_bits[index] |= (1 << pos);
}
void reset(size_t x)
{
size_t index = x / 32;
size_t pos = x % 32;
_bits[index] &= ~(1 << pos);
}
bool test(size_t x)
{
size_t index = x / 32;
size_t pos = x % 32;
return _bits[index] & (1 << pos);
}
private:
vector<int> _bits;
size_t _num;
};
void test_bitset()
{
bitset bs(100);
bs.set(99);
bs.set(98);
bs.set(97);
bs.set(5);
for (size_t i = 0; i < 100; ++i)
{
printf("[%d]:%d\n", i, bs.test(i));
}
bitset<100> bs;
bs.set();
bs.set(3,0);
bs.set(3);
}
}
|
二、布隆过滤器
假如有100亿个ip地址在文件中，如何判断一个ip地址是否在这个文件中？
1.哈希表浪费空间
2.位图一般只能处理整形，如果内容编号是字符串，就无法处理。
3.将哈希与位图结合，即布隆过滤器
所以布隆过滤器的底层就是bitset
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
| #include"bitset.hpp"
namespace 9TSe
{
struct Hashstr1
{
size_t operator()(const std::string& s)
{
size_t theway = 0;
for (size_t i = 0; i < s.size(); ++i)
{
theway *= 131;
theway += s[i];
}
return theway;
}
};
struct Hashstr2
{
size_t operator()(const std::string& s)
{
size_t theway = 0;
size_t magic = 63689;
for (size_t i = 0; i < s.size(); ++i)
{
theway *= magic;
theway += s[i];
magic *= 378551;
}
return theway;
}
};
struct Hashstr3
{
size_t operator()(const std::string& s)
{
size_t theway = 0;
for (size_t i = 0; i < s.size(); ++i)
{
theway *= 65599;
theway += s[i];
}
return theway;
}
};
template<class K = std::string,class Hash1 = Hashstr1,class Hash2 = Hashstr2,class Hash3 = Hashstr3>
class bloomfilter
{
public:
bloomfilter(size_t num)
:_bs(5*num)
, _N(5*num)
{}
void set(const K& k)
{
size_t index1 = Hash1()(k) % _N;
size_t index2 = Hash2()(k) % _N;
size_t index3 = Hash3()(k) % _N;
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
bool test(const K& k)
{
size_t index1 = Hash1()(k) % _N;
if (_bs.test(index1) == false)
return false;
size_t index2 = Hash2()(k) % _N;
if (_bs.test(index2) == false)
return false;
size_t index3 = Hash3()(k) % _N;
if (_bs.test(index3) == false)
return false;
return true;
}
void reset(const K& k)
{
}
private:
bitset _bs;
size_t _N;
};
void test_bloomfilter()
{
bloomfilter<std::string> bf(100);
bf.set("abcd");
bf.set("aadd");
bf.set("bcad");
cout << bf.test("abcd") << endl;
cout << bf.test("aadd") << endl;
cout << bf.test("bcad") << endl;
cout << bf.test("cdbc") << endl;
}
}
|
其原理大概就是一个数据通过多个哈希函数(优质算法)映射到不同的位置
两个不同的数据映射位置完全相同的概率非常低(有可能不同数据映射相同位置)
优点
节省空间,高效,可以标记存储任何类型,
增查效率有O(K),k==哈希函数个数
缺点
有误判(可以创建白名单:将可能出现误判的数据存入)
无法获取数据本身
一般情况无法删除数据
通过计数删除可能有计数环绕问题(8->0)
计数删除:比特位扩展一个计数器(还要考虑要占几个bit位),便可以支持删除,不过哈希冲突仍然存在
