您现在的位置:首页 --> 查看专题: Bloomfilter
今天,有个同学向我咨询大数据的一些面试题,其中一类比较有代表性比如判断是否在集合内,比如10个url,判断一个url是否在集合内,还比如有个1~100万个连续无序数字,随机取出里面的N个,求这N个数字等等。这类问题都需要一个大的数据集合,而且每个数据单元都很小,比如一个int 。很大程度上,这类问题可以用Bitmap或者Bloomfilter来做,基本思想就是开辟一块大内存,然后利用一个byte里的8个bit来实现按位标记元素。因为地址空间都是连续的,所以查找都是O(1)的。这里需要说的是,BloomFilter判断属不属于集合,在理论上是存在误判的,如果要求数据100%正确,则不要使用BloomFilter。
[ 共1篇文章 ][ 第1页/共1页 ][ 1 ]
近3天十大热文
- [416] Go Reflect 性能
- [32] 正态分布的前世今生(一)
- [18] 公钥私钥加密解密数字证书数字签名详解
- [17] 基于HTTP缓存轻松实现客户端应用的离线支持
- [16] osx平台上lol英雄联盟launcher启
- [14] 在JavaScript中什么时候使用==是正
- [14] Joomla反序列化漏洞的查漏补缺
- [14] 无锁HashMap的原理与实现
- [13] SSL多域名绑定证书的解决方案
- [12] rsync同步的艺术
赞助商广告