您现在的位置:首页 --> 查看专题: Bloomfilter
今天,有个同学向我咨询大数据的一些面试题,其中一类比较有代表性比如判断是否在集合内,比如10个url,判断一个url是否在集合内,还比如有个1~100万个连续无序数字,随机取出里面的N个,求这N个数字等等。这类问题都需要一个大的数据集合,而且每个数据单元都很小,比如一个int 。很大程度上,这类问题可以用Bitmap或者Bloomfilter来做,基本思想就是开辟一块大内存,然后利用一个byte里的8个bit来实现按位标记元素。因为地址空间都是连续的,所以查找都是O(1)的。这里需要说的是,BloomFilter判断属不属于集合,在理论上是存在误判的,如果要求数据100%正确,则不要使用BloomFilter。
[ 共1篇文章 ][ 第1页/共1页 ][ 1 ]
近3天十大热文
- [11] 文言文白话文互转:文言文转白话文(现代文),
- [11] 解决 ubuntu 的 /etc/hosts
- [10] 用邻接表实现无向图
- [10] 海量数据面试题举例
- [9] 一个 VLA (可变长度数组)的实现
- [9] apt 的 update 和 upgrade
- [9] Http/2知识图谱
- [8] arduino-蓝牙各种版本类型及费用对比
- [8] 聚类算法之ISODATA
- [8] 为什么数组标号是从0开始的?
赞助商广告