赞
踩
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是由一个很长的bit数组和一系列哈希函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中
它是一种概率型数据结构,它能告知你一个元素大概率存在,或一定不存在。 ,常用与黑名单查找、垃圾邮件过滤、解决缓存穿透。
假设布隆过滤器由20位二进制、3个哈希函数组成,每个元素经过哈希函数处理都能生成一个索引位置
添加元素时,将每一个哈希函数生成的索引位置都设为1。
查找元素时,如果有一个哈希函数生成的索引位置不为1,就代表100%不存在。如果每一个哈希函数生成的索引位置都为1,就代表存在(存在错误率)
此时table内并没有存入cat ,查询 cat ,1 3 7 位置全为1, 产生误判。布隆过滤器的误判率本质是由于hash冲突造成的。
网上的推导过程很多,这里就直接给出结论
误判率 P 受到三个因素的影响:二进制个数 m、哈希函数个数 k、数据规模 n
误判率和数据规模都是我们手动给出,只要求二进制位的个数m、哈希函数的个数k,
例如:数据规模为1千万,误判率规定为千分之一。只需将其参数套入公式,就可得出m和k。
int hashCode(int val) //提供整形、浮点、字符串的哈希值。 { return val; } int hashCode(float val) { return *(int*)(&val); } int hashCode(double val) { unsigned long long tmp = *((long long*)&val); return ((tmp >> 32) ^ (tmp)); } int hashCode(const string& val) { int ret = 0; for (int i = 0; i < val.size(); i++) { //ret = ret * 31 + val[i]; ret = (ret << 5) - ret + val[i]; } return ret; } template<class T> class BloomFilter { public: BloomFilter(int n, double p) { assert(n > 0 && p > 0 && p < 1); double ln2 = log(2); bitSize = -(n * log(p) / (ln2 * ln2)); hashSize = bitSize * ln2 / n; int bitArrSize = (bitSize + 64 - 1) / 64; bitArr = new long long[bitArrSize]; //向上取整,还可以写成ceil(bitSize / 64) memset(bitArr, 0, bitArrSize * sizeof(long long)); } ~BloomFilter() { delete[] bitArr; } void put(const T& key) { assert(key); size_t hCode1 = hashCode(key); size_t hCode2 = hCode1 >> 16; for (int i = 1; i <= hashSize; i++) { int index = hCode1 + (i * hCode2); //尽可能的使index分布均匀 if (index < 0) //防止index为负数 index = ~index; index %= bitSize; //防止越界 int pos = index / 64; //设置index位置为1 int offset = index % 64; unsigned long long n = 1; bitArr[pos] = bitArr[pos] | (n << offset); int tmp = 1; } } bool contains(const T& key) { assert(key); size_t hCode1 = hashCode(key); size_t hCode2 = hCode1 >> 16; for (int i = `在这里插入代码片`1; i <= hashSize; i++) { int index = hCode1 + (i * hCode2); //尽可能的使index分布均匀 if (index < 0) //防止index为负数 index = ~index; index %= bitSize; //防止越界 int pos = index / 64; //设置index位置为1 int offset = index % 64; unsigned long long n = 1; if ((bitArr[pos] & (n << offset)) == 0) //为0直接返回 return false; } return true; } private: int bitSize; //bit位的个数 int hashSize; //hash函数个数 long long* bitArr; //bit数组 };
优点
缺点
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。