互聯網 - 大數據

 1 /*
 2  * bloom.h
 3  *
 4  *  Created on: 2012-2-22
 5  *      Author: xiaojay
 6  */
 7 
 8 #ifndef BLOOM_H_
 9 #define BLOOM_H_
10 #include <vector>
11 #include "hashFun.h"
12 
13 class Bloom
14 {
15 public :
16     Bloom(int size , std::vector<HashFun*> hashfunclist );
17     ~Bloom();
18     void add(const char * text);
19     bool check(const char * text);
20 
21 private :
22     const static int CHARBITSIZE = 8;
23     int size;
24     char * arr;
25     std::vector<HashFun*> hashfunclist;
26     inline void setbit(long pos);
27     inline bool getbit(long pos);
28 };
29 
30 #endif /* BLOOM_H_ */
31 
32 #include"bloom.h"
33 #include<assert.h>
34 
35 Bloom::Bloom(int size , std::vector<HashFun*> hashfunclist)
36 {
37     assert(hashfunclist.size()>0);
38     this->size = size;
39     this->hashfunclist = hashfunclist;
40     this->arr = new char [size];
41 }
42 
43 Bloom::~Bloom()
44 {
45     if(this->arr!=NULL)
46     {
47         delete this->arr;
48     }
49 }
50 
51 void Bloom::add(const char * text)
52 {
53     int nfunc = hashfunclist.size();
54     long code = 0;
55     for(int i=0;i<nfunc;i++)
56     {
57         code = hashfunclist.at(i)->gethashval(text);
58 
59         if(code/CHARBITSIZE>size) return;
60         else
61         {
62             setbit(code);
63         }
64     }
65 }
66 
67 bool Bloom::check(const char * text)
68 {
69     int nfunc = hashfunclist.size();
70     long code = 0;
71     for (int i=0;i<nfunc;i++)
72     {
73         code = hashfunclist.at(i)->gethashval(text);
74         if(code/CHARBITSIZE>size) return false;
75         else
76         {
77             if getbit(code) continue;
　　　　　　　　　else return false;
78         }
79     }
　　　　return true;
80 }
81 
82 inline void Bloom::setbit(long code)
83 {
84     arr[code/CHARBITSIZE] |= (1<<(code%CHARBITSIZE));
85 }
86 
87 inline bool Bloom::getbit(long code)
88 {
89     if(!(arr[code/CHARBITSIZE] & (1<<(code%CHARBITSIZE))))
90     {
91         return false;
92     }
93     return true;
94 }

#ifndef HASHFUN_H_
#define HASHFUN_H_

class HashFun
{
public :
    virtual long gethashval(const char * key) = 0;
};

#endif /* HASHFUN_H_ */

#include "hashFun.h"

class HashFunA : public HashFun
{
public:
    virtual long gethashval(const char * key)
    {
        unsigned int h=0;
        while(*key) h^=(h<<5)+(h>>2)+(unsigned char)*key++;
        return h%80000;
    }
};


#include"hashFun.h"

class HashFunB : public HashFun
{
public:
    virtual long gethashval(const char * key)
    {
        unsigned int h=0;
        while(*key) h=(unsigned char)*key++ + (h<<6) + (h<<16) - h;
        return h%80000;
    }
};

#include<iostream>
#include<stdio.h>
#include"hashFunA.h"
#include"hashFunB.h"
#include"bloom.h"
#include<vector>
using namespace std;

int main()
{
    /*
     *    Create two hash functions
     */
    HashFunA *funa = new HashFunA();
    HashFunB * funb = new HashFunB();
    vector<HashFun*> hashfunclist;
    hashfunclist.push_back(funa);
    hashfunclist.push_back(funb);

    /*
     * Create Bloom object with two parameters :
     * size of the store array and list of hash functions
     */
    Bloom bloom(10000,hashfunclist);

    ///Add some words to bloom filter
    bloom.add("hello");
    bloom.add("world");
    bloom.add("ipad");
    bloom.add("iphone4");
    bloom.add("ipod");
    bloom.add("apple");
    bloom.add("banana");
    bloom.add("hello");

    /*
     * Test
     */
    char word[20];
    while(true)
    {
        cout<<"Please input a word : "<<endl;
        cin>>word;
        if(bloom.check(word))
        {
            cout<<"Word :"<<word<<" has been set in bloom filter."<<endl;
        }
        else
        {
            cout<<"Word :"<<word<<" not exist !" <<endl;
        }
    }

    return 0;
}