CodingExperiment1-2_BloomFilter/BloomFilter.cpp at master · AnimationFan/CodingExperiment1-2_BloomFilter · GitHub

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
#include"MurmurHash2.h"
#include"BloomFilter.h"
#include<math.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
//计算

unsignedintBloomFilter::getMemSize(unsignedint sourceNum, float errorRate) {
int temp = ceil((double)sourceNum * 1.44 * log(1 / errorRate) / (log(2.0))) + 1;
return (temp >> 3) + 1;
};

unsignedintBloomFilter::getHashNum(unsignedint sourceNum, unsignedint memSize) {
returnceil(0.693 * (double)(memSize << 3) / (double)sourceNum);
}

BloomFilter::BloomFilter(float errorRate, unsignedint sourceNum) {
//memSize以字节为单位
this->memSize = this->getMemSize(sourceNum, errorRate);
this->hashNum = this->getHashNum(sourceNum, this->memSize);
this->mem = newchar[this->memSize];
this->hashBuffer = newunsignedint[this->hashNum];
this->seed = newunsignedint[this->hashNum];
memset(this->mem, 0x00, this->memSize);
time_t t;
srand((unsignedint)time(&t));
for (int i = 0; i < this->hashNum; i++) {
this->seed[i] = rand();
	}

}

boolBloomFilter::setOne(unsignedint loc){
unsignedint locInt, locMant;
	locInt = loc >> 3;
	locMant = loc & 0x07;

if (locInt >= this->memSize)
returnfalse;

char m = 0x01;
	m << locMant;
this->mem[locInt] = this->mem[locInt] | m;
returntrue;
}

intBloomFilter::checkOne(unsignedint loc) {
unsignedint locInt, locMant;
	locInt = loc >> 3;
	locMant = loc & 0x07;

if (locInt >= this->memSize)
return -1;

int m = 0x01;
	m << locMant;
	m = m & this->mem[locInt];

if (m == 0)
return0;
else
return1;
}


voidBloomFilter::getHash(unsignedint* m,char* str,int len) {
if (m == NULL) return;
memset(m, 0x00, this->hashNum * sizeof(unsignedint));
for (int i = 0; i < this->hashNum; i++) {
 m[i] = MurmurHash2(str, len , this->seed[i])%(this->memSize<<3);
	}
}

boolBloomFilter::put(char* str) {
if (str == NULL)
returnfalse;
int len = strlen(str);
memset(this->hashBuffer,0x00,this->hashNum*sizeof(unsignedint));
this->getHash(this->hashBuffer, str, len);
for (int i = 0; i < this->hashNum; i++) {
this->setOne(this->hashBuffer[i]);
	}
returntrue;
}

//返回-1则说明出现异常问题
//返回0则说明目标不存在
//返回1则说明目标存在
intBloomFilter::get(char* str) {
if (str == NULL)
return -1;
memset(this->hashBuffer, 0x00, this->hashNum * sizeof(unsignedint));
int len = strlen(str);
this->getHash(this->hashBuffer, str, len);
for (int i = 0; i < this->hashNum; i++) {
int result = this->checkOne(this->hashBuffer[i]);
if (result == -1)
return -1;
if (result == 0)
return0;
	}
return1;
}

BloomFilter::~BloomFilter() {
delete[]this->hashBuffer;
delete[]this->seed;
delete[]this->mem;
}