茶业网站设计方案,买域名是什么意思,怎么建论坛网站,上海互联网企业100强文章目录1. 位图2. 位图代码3. 布隆过滤器 Bloom Filter4. 总结1. 位图
我们有1千万个整数#xff0c;整数的范围在1到1亿之间。如何快速查找某个整数是否在这1千万个整数中呢#xff1f;
当然#xff0c;这个问题可以用散列表来解决。可以使用一种特殊的散列表#xff0…
文章目录1. 位图2. 位图代码3. 布隆过滤器 Bloom Filter4. 总结1. 位图
我们有1千万个整数整数的范围在1到1亿之间。如何快速查找某个整数是否在这1千万个整数中呢
当然这个问题可以用散列表来解决。可以使用一种特殊的散列表那就是位图。申请一个大小为1亿、布尔类型true或者false的数组。将这1千万个整数作为数组下标将对应的数组值设置成true。比如整数5对应下标为5的数组值设置为true也就是array[5]true。查询某个整数K是否在这1千万个整数中的时候只需将array[K]取出来看是否等于true。如果等于true那说明1千万整数中包含这个整数K相反就表示不包含这个整数K。不过很多语言中提供的布尔类型大小是1个字节的并不能节省太多内存空间。实际上表示true和false只需要**一个二进制位bit**就可以了。我们可以借助编程语言中提供的数据类型比如int、long、char等类型通过位运算用其中的某个位表示某个数字。
2. 位图代码
#include iostream
#include cstring
using namespace std;
class BitMap
{char *bytes; //char是1字节8位int nbits;
public:BitMap(int n){nbits n;bytes new char [nbits/8 1];memset(bytes, 0, (nbits/81)*sizeof(char));}~BitMap(){delete [] bytes;}void set(int k){if(k nbits)return;int byteIndex k/8;int bitIndex k%8;bytes[byteIndex] | (1bitIndex);}bool get(int k){if(k nbits)return false;int byteIndex k/8;int bitIndex k%8;return (bytes[byteIndex] (1 bitIndex)) ! 0;}void print(){for(int i 15; i 0; --i)cout get(i) ;}
};
int main()
{BitMap bm(8);bm.set(8);cout bm.get(8) endl;bm.print();return 0;
}比如上面例子如果用散列表存储这1千万的数据数据是32位的整型数也就是需要4个字节的存储空间那总共至少需要40MB的存储空间。如果通过位图的话数字范围在1到1亿之间只需要1亿个二进制位1亿/8/1024/1024 12, 也就是12MB左右的存储空间就够了。
不过这里我们有个假设就是数字范围不是很大。如果数字的范围很大数字范围不是1到1亿而是1到10亿那位图的大小就是10亿个二进制位也就是120MB的大小消耗的内存空间不降反增
怎么办请布隆过滤器登场
3. 布隆过滤器 Bloom Filter
布隆过滤器就是为了解决刚刚这个问题对位图这种数据结构的一种改进。
还是刚刚那个例子数据个数是1千万数据的范围是1到10亿。 布隆过滤器的做法是我们仍然使用一个1亿个二进制大小的位图然后通过哈希函数对数字进行处理让它落在这1到1亿范围内。比如我们把哈希函数设计成f(x) x%n。其中x表示数字n表示位图的大小1亿也就是对数字跟位图的大小进行取模求余。 哈希函数会存在冲突的问题为了降低冲突概率可以设计一个复杂点、随机点的哈希函数。除此之外还有其他方法吗 我们来看布隆过滤器的处理方法。既然一个哈希函数可能会存在冲突那用多个哈希函数一起定位一个数据是否能降低冲突的概率呢 使用 K 个哈希函数对同一个数字进行求哈希值那会得到K个不同的哈希值我们分别记作X1X2X3……Xk 。我们把这 K 个数字作为位图中的下标将对应的BitMap[X1],BitMap[X2],BitMap[X3],……BitMap[Xk]都设置成true也就是说我们用 K 个二进制位来表示一个数字的存在。 当我们要查询某个数字是否存在的时候我们用同样的 K 个哈希函数对这个数字求哈希值分别得到Y1Y2Y3……Yk 。看这 K 个哈希值对应位图中的数值是否都为true都是true这个数字存在任意一个不为true说明这个数字不存在。 对于两个不同的数字经过 K 个哈希函数处理之后K 个哈希值都相同的概率就非常低了。尽管采用 K 个哈希函数之后两个数字哈希冲突的概率降低了但是这种处理方式又带来了新的问题那就是容易误判。看下面例子。 布隆过滤器的误判有一个特点那就是它只会对存在的情况有误判。 如果某个数字经过布隆过滤器判断不存在那说明这个数字真的不存在不会误判 如果某个数字经过布隆过滤器判断存在有可能误判有可能并不存在。不过只要我们调整哈希函数的个数、位图大小跟要存储数字的个数之间的比例那就可以将这种误判的概率降到非常低。 尽管布隆过滤器会存在误判但是这并不影响它发挥大作用。很多场景对误判有一定的容忍度。
4. 总结
布隆过滤器非常适合这种不需要100%准确的、允许存在小概率误判的大规模判重场景。比如统计一个大型网站的每天的UV数也就是每天有多少用户访问了网站就可以使用布隆过滤器对重复访问的用户进行去重。
布隆过滤器的误判率主要跟哈希函数的个数、位图的大小有关。往布隆过滤器中不停地加入数据之后位图中不是true的位置就越来越少了误判率就越来越高了。所以对于无法事先知道要判重的数据个数的情况我们需要支持自动扩容的功能。
当布隆过滤器中数据个数与位图大小的比例超过某个阈值的时候我们就重新申请一个新的位图。后面来的新数据会被放置到新的位图中。但是如果我们要判断某个数据是否在布隆过滤器中已经存在我们就需要查看多个位图相应的执行效率就降低了一些。
位图、布隆过滤器应用如此广泛很多编程语言都已经实现了。比如 Java 中的 BitSet 类就是一个位图Redis 也提供了 BitMap 位图类Google 的 Guava 工具包提供了BloomFilter 布隆过滤器的实现。
课后思考 1.假设我们有1亿个整数数据范围是从1到10亿如何快速并且省内存地给这1亿个数据从小到大排序
传统做法1亿个整数存储需要400M空间 位图算法数字范围是1到10亿用位图存储125M就够了然后将1亿个数字依次添加到位图中再将位图按下标从小到大输出值为1的下标排序就完成了时间复杂度为O(n)
