- #pragma once
- #include "BitMap.h"
- typedef const char* KeyType;
- typedef size_t (*HASH_FUNC)(KeyType); // 计算哈希值的函数指针
- typedef struct BloomFilter
- {
- BitMap _bm;
- //size_t* _bm; //Reset 时将一个 query 用一个 32 位一个数据项保存信息, 如此可以表示更大的引用计数
- HASH_FUNC _hashfunc1; // 计算字符串的哈希值函数
- HASH_FUNC _hashfunc2;
- HASH_FUNC _hashfunc3;
- }BloomFilter;
- void BloomFilterInit(BloomFilter* bf, size_t range);
- void BloomFilterSet(BloomFilter* bf, KeyType key);
- //void BloomFilterReset(BloomFilter* bf, KeyType key);
- int BloomFilterTest(BloomFilter* bf, KeyType key);
- size_t BKDRHash(KeyType str)
- {
- register size_t hash = 0;
- while(size_t ch = (size_t)*str++)
- {
- hash = hash * 131 + ch;// 也可以乘以 31131131313131131313..
- }
- return hash;
- }
- size_t SDBMHash(KeyType str)
- {
- register size_t hash =0;
- while(size_t ch = (size_t)*str++)
- {
- hash = 65599 * hash + ch;//hash =(size_t)ch + (hash <<6) + (hash <<16) - hash;
- }
- return hash;
- }
- size_t RSHash(KeyType str)
- {
- register size_t hash = 0;
- size_t magic = 63689;
- while(size_t ch = (size_t)*str++)
- {
- hash = hash * magic + ch;
- magic*= 378551;
- }
- return hash;
- }
- void BloomFilterInit(BloomFilter* bf, size_t range)
- {
- assert(bf);
- BitMapInit(&bf->_bm, range);
- bf->_hashfunc1 = BKDRHash;
- bf->_hashfunc2 = SDBMHash;
- bf->_hashfunc3 = RSHash;
- }
- void BloomFilterSet(BloomFilter* bf, KeyType key)
- {
- assert(bf);
- // 假如 sort 123
- size_t hash1 = bf->_hashfunc1(key); // 得到字符串的 size_t 类型的一个哈希值
- size_t hash2 = bf->_hashfunc2(key);
- size_t hash3 = bf->_hashfunc2(key);
- BitMapSet(&bf->_bm, hash1%bf->_bm._range); // 算得的 hash 可能比 range 大, 产生越界访问; 故取模运算
- BitMapSet(&bf->_bm, hash2%bf->_bm._range);
- BitMapSet(&bf->_bm, hash3%bf->_bm._range);
- }
- int BloomFilterTest(BloomFilter* bf, KeyType key)
- {
- assert(bf);
- size_t hash1 = bf->_hashfunc1(key); // 得到字符串的 size_t 类型的一个哈希值
- if(BitMapTest(&bf->_bm, hash1%bf->_bm._range) == -1)
- return -1;
- size_t hash2 = bf->_hashfunc2(key);
- if(BitMapTest(&bf->_bm, hash2%bf->_bm._range) == -1)
- return -1;
- size_t hash3 = bf->_hashfunc2(key);
- if(BitMapTest(&bf->_bm, hash3%bf->_bm._range))
- return -1;
- return 0;
- }
来源: https://www.cnblogs.com/tp-16b/p/8605937.html