像BKDRHash,APHash。DJBHash。JSHash,RSHash。SDBMHash,PJWHash。ELFHash等等。都是比較经典的。...经常使用字符串哈希函数有 BKDRHash。APHash。DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。对于以上几种哈希函数。...Hash函数 数据1 数据2 数据3 数据4 数据1得分 数据2得分 数据3得分 数据4得分 平均分 BKDRHash 2 0 4774 481 96.55 100 90.95 82.05 92.64...能够发现,BKDRHash不管是在实际效果还是编码实现中。效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。...hash &= ~x; } } return (hash & 0x7FFFFFFF); } // BKDR Hash Function unsigned int BKDRHash
常用字符串哈希函数有BKDRHash,APHash,DJBHash,JSHash,RSHash,SDBMHash,PJWHash,ELFHash等等。...数据1 数据2 数据3 数据4 数据1得分 数据2得分 数据3得分 数据4得分 平均分 BKDRHash...可以发现,BKDRHash无论是在实际效果还是编码实现中,效果都是最突出的。APHash也是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。...hash&=~x ; } } return(hash % M); } // BKDR Hash Function unsigned int BKDRHash
2个位置 具体实现 传递模板时,传入hash1 hash2 hash3 ,将K类型转换为整形 hash1 hash2 hash3 作为三种不同的映射方法 hash1 hash2 hash3 BKDRHash...算法在哈希中的 针对string情况使用过 , 当需使用字符串转化为整形时,将字符串中所有字符相加 ,用此确定对应的key 将BKDRHash作为缺省值 ,传给 hash1 点击查看详细解释:哈希 -...bitset v; v.set(10); cout << v.test(10) << endl; cout << v.test(15) << endl; } //仿函数 struct BKDRHash...= (hash << 5) + e; } return hash; } }; template< size_t N, class K = string, class Hash1 = BKDRHash
所以布隆过滤器可以实现为一个模板类,将模板参数 T 的缺省类型设置为 string: template <size_t N,size_t X = 5,class K=string, class HashFunc1 = BKDRHash...: bitset _bs; }; 这里布隆过滤器提供三个哈希函数,由于布隆过滤器一般处理的是字符串类型的数据,所以我们默认提供几个将字符串转换成整型的哈希函数:选取综合评分最高的 BKDRHash...、APHash 和 DJBHash这三种哈希算法: struct BKDRHash { size_t operator()(const string& key) { size_t
//xxx.xxx.89', '50~75'=>'http://xxx.xxx.90', '75~100'=>'http://xxx.xxx.91' 哈希算法如下: function BKDRHash
hash ^= (x >> 24); } hash &= ~x; } return hash; } 6.BKDR Hash unsigned int BKDRHash
_state(EMPTY) {} pair _kv; enum state _state; }; template <class K, class V, class Hash = BKDRHash...重新计算,映射到新表 /*vector newtables; newtables.resize(2 * _tables.size()); */ HashTable<K, V, BKDRHash...5.哈希表key值不能取模无法映射的解决方法(BKDRHash) 1. 上面举例子时,键值对的key值都是整型,整型当然可以完成映射,那如果是自定义类型string呢?...字符串哈希算法 template struct BKDRHash { size_t operator()(const K& key) { return (size_t)key...;//只要这个地方能转成整型,那就可以映射,指针浮点数负数都可以,但string不行 } }; template struct BKDRHash { size_t operator
第二步:寻找hash函数 获取几个hash函数,前辈们已经发明了很多运行良好的hash函数,比如BKDRHash,JSHash,RSHash等等。这些hash函数我们直接获取就可以了。...*/ public function BKDRHash($string, $len = null) { $seed = 131; # 31 131 1313 13131 131313 etc.....{ /** * 表示判断重复内容的过滤器 * @var string */ protected $bucket = 'rptc'; protected $hashFunction = array('BKDRHash
简单实现代码如下 这里使用3个哈希函数,分别为:BKDRHash、APHash和DJBHash。使用string为类型。...false; } //直到最后,说明该数据是存在的,返回true return true; } 整体代码如下: namespace my_BloomFilter { struct BKDRHash...return hash; } }; template<size_t N, size_t X = 5, class K = string, class HashFunc1 = BKDRHash
代码实现如下: #pragma once #include #include using std::bitset; using std::string; struct BKDRHash...size_t N, //数据范围 size_t X = 5, //每个元素最多消耗的比特位的位数 class K = string, //数据类型 class HashFunc1 = BKDRHash...它与哈希函数的个数有关,由于我们实现的版本中默认使用的是三个哈希函数,所以X的缺省值为5,但我们也可以显示传递X的值来增加/减少哈希冲突的概率,最后三个模板参数分别为三个哈希函数,这里我们使用的字符串哈希算法分别为BKDRHash
五.布隆过滤器完整代码 struct BKDRHash { size_t operator()(const string& str) { size_t hash = 0; for (auto...= (hash << 5) + ch; } return hash; } }; template<size_t N, class K=string, class Hash1= BKDRHash
,这会导致 哈希冲突 因此,单纯的累加每个字符的 ASCII 码值显得不够专业 有人专门对 字符串 进行研究,搞出了各种各样重复率较低的 字符串哈希算法 字符串哈希算法 在众多 字符串哈希算法 中,BKDRHash...一骑绝尘,各方面都非常优秀,因此这里我们选择 BKDRHash 算法作为 计算字符串值 的函数 BKDRHash 的核心就是 在原来值的基础上 * 131,再加上字符的 ASCII 码值 //模板的特化...GetKey { size_t operator()(const string& key) { //根据字符串,计算出数值并返回 size_t val = 0; //BKDRHash
hash &= ~x; } } return (hash & 0x7FFFFFFF); } // BKDR Hash Function unsigned int BKDRHash
private: Yohifo::bitset _bits; //位图结构 }; } 显然,这三个 哈希函数 的选择是十分重要的,我们在这里提供三种较为优秀的 哈希函数(字符串哈希算法),分别是 BKDRHash...、APHash 以及 DJBHash 函数原型如下(写成 仿函数 的形式,方便传参与调用): struct BKDRHash { size_t operator()(const std::string...并且三个 哈希函数 我们也已经有了,所以可以将 布隆过滤器 中模板添加上 缺省值 template<size_t N, class K = std::string, class Hash1 = BKDRHash...进行修改,结合 误判率 与 空间,选择较为折中的 6 作为 布隆过滤器 的长度 template<size_t N, class K = std::string, class Hash1 = BKDRHash
下面调用了三个综合评分最高的四个哈希算法(把字符串转化成整形)struct BKDRHash{size_t operator()(const string& key){size_t hash = 0;for...,//最多存储的数据个数size_t X=6,//平均存储一个数据要开辟6个映射位class K=string,//数据类型的模板参数---缺省值给string class HashFunc1=BKDRHash
#define _CRT_SECURE_NO_WARNINGS 1 #include using namespace std; struct BKDRHash { size_t...} return hash; } }; template<size_t N, size_t X = 5, class K = string, class HashFunc1 = BKDRHash
4.2 BloomFilter.h #pragma once #include //设置的仿函数 struct BKDRHash { size_t operator()(const...} return hash; } }; template<size_t N, size_t X = 5, class K = string, class HashFunc1 = BKDRHash
arithmetic operations in such expressions will use 32-bit modular arithmetic ignoring overflow 在实际中,BKDRhash...函数比较好 // BKDR Hash unsigned int BKDRHash(char *str) { unsigned int seed = 131; // 31 131 1313 13131 131313
k 为哈希函数个数,m 为布隆过滤器长度,n 为插入的元素个数,p 为误报率 所以根据公式,我这里使用的哈希函数为3个,空间就应该开插入元素个数的五倍左右 实现代码: struct _BKDRHash...{ //BKDRHash size_t operator()(const std::string& key) { size_t hash = 0; for (size_t i...magic *= 378551; } return hash; } }; template<size_t N,class K=std::string, class Hash1=_BKDRHash
2.4 布隆过滤器实现的基本结构 //想把类当函数使用 就要想到仿函数 //提供三个字符串哈希函数 struct BKDRHash { size_t operator() (const string...至于用多少个哈希函数 取决于实际的需求 //N表示最多会插入key的个数 template<size_t N, size_t X=6, class K=string, class Hash1= BKDRHash...2.13 布隆过滤器的整体代码实现 //想把类当函数使用 就要想到仿函数 //提供三个字符串哈希函数 struct BKDRHash { size_t operator() (const...至于用多少个哈希函数 取决于实际的需求 //N表示最多会插入key的个数 template<size_t N, size_t X=6, class K=string, class Hash1= BKDRHash
领取专属 10元无门槛券
手把手带您无忧上云