赞
踩
非常感谢评论里指出了我代码里的小问题。以下代码修改了一下,主要是在第二次 HasH 的时候有小问题。
Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构,它具有很好的空间和时间效率,被用来检测一个元素是不是集合中的一个成员。如果检测结果为是,该元素不一定在集合中;但如果检测结果为否,该元素一定不在集合中。因此Bloom filter具有100%的召回率。这样每个检测请求返回有“在集合内(可能错误)”和“不在集合内(绝对不在集合内)”两种情况,可见 Bloom filter 是牺牲了正确率和时间以节省空间。
以上文字来源百度百科
如需要判断一个元素是不是在一个集合中,我们通常做法是把所有元素保存下来,然后通过比较知道它是不是在集合内,链表、树都是基于这种思路,当集合内元素个数的变大,我们需要的空间和时间都线性变大,检索速度也越来越慢。 Bloom filter 采用的是哈希函数的方法,将一个元素映射到一个 m 长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,反之则不在集合内。这个方法的缺点就是当检测的元素很多的时候可能有冲突,解决方法就是使用 k 个哈希 函数对应 k 个点,如果所有点都是 1 的话,那么元素在集合内,如果有 0 的话,元素则不在集合内。
例如我们有一个简单的Bloom Filter结构如下:(所有位都是0)
[ 0 0 0 0 0 0 0 0 0 0 ]
第一次插入a
用两个哈希函数,映射到1 4
位置上,变为1.
[ 1 0 0 1 0 0 0 0 0 0 ]
第二次插入b
同样的hash函数,映射到1 8
位置上, 变为1.
[ 1 0 0 1 0 0 0 1 0 0 ]
这样就存放了a b
两个元素,当我们查找a
是否在的时候,两次hash找到1 4
位置,发现同时为 1。则表明a
存在。
但是假如我们查找的d
哈希后映射到4 8
位置,发现也同时为 1. 认为存在,这就出错了,因为现在里面只存放了a b
没有d
。
下面写下我用C++写的代码实现,比较简单的实现了下,具体的Hash算法我都简略的写了。
首先是头文件Header.h
//
// Header.h
// BloomFilter
//
// Created by Alps on 15/3/19.
// Copyright (c) 2015年 chen. All rights reserved.
//
#ifndef BloomFilter_Header_h
#define BloomFilter_Header_h
class BitMap{
public:
BitMap(){
bitmap = NULL;
size = 0;
}
BitMap(int size){
bitmap = NULL;
bitmap = new char[size];
if (bitmap == NULL) {
printf("ErroR In BitMap Constractor!\n");
}else{
memset(bitmap, 0x0, size * sizeof(char));
this->size = size;
}
}
int initBitMap(int size){
bitmap = NULL;
bitmap = new char[size];
if (bitmap == NULL) {
printf("ErroR In BitMap Constractor!\n");
return 0;
}else{
memset(bitmap, 0x0, size * sizeof(char));
this->size = size;
return this->size;
}
}
/*
* set the index bit to 1;
*/
int bitmapSet(int index){
int addr = index/8;
int addroffset = index%8;
unsigned char temp = 0x1 << addroffset;
if (addr > (size+1)) {
return 0;
}else{
bitmap[addr] |= temp;
return 1;
}
}
/*
* return if the index in bitmap is 1;
*/
int bitmapGet(int index){
int addr = index/8;
int addroffset = index%8;
unsigned char temp = 0x1 << addroffset;
if (addr > (size + 1)) {
return 0;
}else{
return (bitmap[addr] & temp) > 0 ? 1 : 0;
}
}
/*
* del the index from 1 to 0
*/
int bitmapDel(int index){
if (bitmapGet(index) == 0) {
return 0;
}
int addr = index/8;
int addroffset = index%8;
unsigned char temp = 0x1 << addroffset;
if (addr > (size + 1)) {
return 0;
}else{
bitmap[addr] ^= temp;
return 1;
}
}
private:
char *bitmap;
int size;
};
#endif
头文件保存好,放到工程路径下。
下面是BloomFilter.cpp
文件了。
//
// main.cpp
// BloomFilter
//
// Created by Alps on 15/3/18.
// Copyright (c) 2015年 chen. All rights reserved.
//
#include <iostream>
#include "Header.h"
using namespace std;
template <class Type> class BloomFilter{
public:
BloomFilter();
BloomFilter(int length){
bitmap.initBitMap(length);
this->length = length;
}
bool Add(const Type &T);
bool Contains(const Type &T);
int HasH(const Type &T);
int SecondHasH(const Type &T);
private:
BitMap bitmap;
int length;
};
template <class Type> int BloomFilter<Type>::HasH(const Type &T){
int temp = (int) T;
return temp%length;
}
template <class Type> int BloomFilter<Type>::SecondHasH(const Type &T){
int temp = (int) T;
return temp%9973;
//这里直接选了一个大素数 请各位自己优化自己的 HasH函数
//不然会出现频繁的哈希冲突,并且把布隆过滤器的大小尽量放大一点几百万都可以
}
template <class Type> bool BloomFilter<Type>::Add(const Type &T){
int first = HasH(T);
int second = SecondHasH(first);
if (bitmap.bitmapSet(first) && bitmap.bitmapSet(second)) {
return true;
}else{
return false;
}
}
template <class Type> bool BloomFilter<Type>::Contains(const Type &T){
int first = HasH(T);
int second = SecondHasH(T);
if (bitmap.bitmapGet(first) && bitmap.bitmapGet(second)) {
return true;
}else{
return false;
}
}
int main(int argc, const char * argv[]) {
BloomFilter<int> bloom(10);
bloom.Add(3);
if (bloom.Contains(3)) {
printf("true\n");
}else{
printf("false\n");
}
if (bloom.Contains(2)) {
printf("true\n");
}else{
printf("false\n");
}
return 0;
}
这就是我的代码了。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。