04 | 状态检索：如何快速判断一个用户是否存在？
该思维导图由 AI 生成，仅供参考
如何使用数组的随机访问特性提高查询效率？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了如何快速判断一个用户是否存在的技术方案，主要涉及了有序数组、二叉检索树、哈希表、位图和布隆过滤器。文章指出，位图和布隆过滤器在不要求100%判断正确的情况下，能够以O(1)时间代价实现高效的检索效率，并且具有高效的空间利用率。作者强调了在大型系统中广泛应用位图和布隆过滤器的重要性，例如在存储系统和搜索引擎中的应用。此外，文章还讨论了布隆过滤器的错误率问题，并提出了控制哈希函数个数的方法来降低错误率。总的来说，本文总结了位图和布隆过滤器在快速判断对象存在性方面的优势和适用场景，为读者提供了对这些技术特点的深入了解。
《检索技术核心 20 讲》，新⼈⾸单¥59
全部留言(30)
- 最新
- 精选
峰bitmap 是一个集合，每个元素在集合中有一个唯一不冲突的编号(用户自己保证，在数据库中这个编号可以是行号)，是双射关系。而布隆过滤器是一个不准确的集合，而且是一对多的关系，会发生冲突，也就是说布隆过滤器的为1的位可能代表多个元素，自然不能因为一个元素删除就把它干掉？，或者说他就不支持删除操作，感觉它要支持了，反而把它本身的优势给丢了。 1，其实对布隆过滤器是省了空间，我表示持怀疑态度，可能需要证明下，我可能更多的认为它是一种平衡单个hash 函数对数据分布有偏差性导致最差情况的数据冲突的概率大的一种方法。 2，bitmap 本身也有很多压缩方法，最有名的应该是roaringbitmap ，大家有兴趣可以了解下。作者回复: 你的思考很深入！ 1.对于布隆过滤器的删除问题，的确无法直接删除。但也有带引用计数的布隆过滤器，存的不是0，1，而是一个计数。其实所有的设计都是trade off。应该视具体使用场景而定。比如一个带4个bit位计数器的布隆过滤器，相比于哈希表依然有优势。 2.布隆过滤器是否省空间，要看怎么比较。 布隆过滤器 vs 原始位图: 原始位图要存一个int 32的数，就要先准备好512m的空间的长数组。布隆过滤器不用这么长的数组，因此比原始位图省空间。 布隆过滤器 vs 哈希表: 假设布隆过滤器数组长度和哈希表一样。但是哈希表存的是一个int 32，而布隆过滤器存的是一个bit，因此比同样长度的哈希表省空间。 当然，如果哈希表也改为只存一个bit的数组，那么他们的大小是一样的。这时候就是你说的多个哈希函数的作用场景了。 其实，你会发现，只存一个bit的哈希表，其实也可以看做是只有一个哈希函数的布隆过滤器。很多时候，布隆过滤器，哈希表，还有位图，它们的边界是模糊的。我们最重要的是了解清楚他们的特点，知道在什么场景用哪种结构就好了。 3.roaring bitmap是一个优秀的设计。我在基础篇的加餐中会和大家分享。在这里，我也说一下它和布隆过滤器的差异: 布隆过滤器 vs roaring bitmap: 所有的设计都是trade off。roaring bitmap尽管压缩率很高，还支持精准查找，但是它放弃的是速度。高16位是采用二分查找，array container也是二分查找。因此，在这一点上布隆过滤器是有优势的。此外，它还不能保证压缩空间，它的空间会随着元素增多而变大，极端情况下恢复回bitmap。 而布隆过滤器保持了高效的查找能力和空间控制能力，但是放弃了精准查找能力，精准度会随着元素增多而下降。 因此，尽管都是对bitmap进行压缩，但是两者的设计思路不一样，使用场景也不同。在不要求精准，但是要求快速和省空间的场景下，布隆过滤器是不错的选择。
2020-03-30642
每天晒白牙请教老师一个问题 假如我有3亿个连续id，如果使用BitMap存储，需要消耗 3亿/8/1024/1024 大约36MB 如果用 GuavaCache 的 BloomFilter，在默认误判率0.03的情况下，占用内存约261MB BloomFilter<CharSequence> filter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions); 其中 expectedInsertions 代表预估数量即3亿，通过查看源码，BloomFilter 根据预估数量和误判率计算bit数组的公式 m=-n*ln(fpp)/(log2)^2 long m = (long) (-expectedNum * Math.log(fpp) / (Math.log(2) * Math.log(2))); expectedNum就是3亿，计算出来的m为2189532251，大于3亿，这个结果感觉说不通，BloomFilter 通过使用多个哈希函数，应该需要的数组长度小于3亿才对呀，而BloomFilter是用long型的数组实现，所以会根据计算出来的m计算long数组的大小int longNum = Ints.checkedCast(LongMath.divide(m, 64, RoundingMode.CEILING));计算出来是34211442，占用内存是261MB 所以，同样3亿个连续id，使用Guava 的BloomFilter占用的内存反而比使用BitMap内存大，通过学习这篇文章，我觉得结果应该是相反的，我有点蒙了，请老师帮忙指点下作者回复: 是这样的，紧凑的bitmap其实是最省空间的，比bloomfilter和roaring bitmap都更省空间。 你的这个例子中，其实默认是“3亿个连续的数据紧凑地存在bitmap中，没有一丝空间浪费”。在这样的情况下，由于没有一丝空间浪费，因此，无论是使用bloomfilter，还是roaring bitmap，都不可能更省空间。 但是，如果不是“连续紧凑的”3亿个数据呢？比如说间隔很稀疏，要间隔十个元素才会出现一个值，那么你的bitmap就需要36mb*10=360mb才能存储这三亿个元素了。这就比你使用bloomfilter更多了。 因此，在数据不是连续紧凑出现的前提下，bloomfilter和roaring bitmap才能发挥它们的优势，反之，如果是连续紧凑的元素存储，直接使用bitmap更合适。
2020-07-0916
阿斯蒂芬刚看完时有点“混乱”，搞不清楚哈希表、位图、布隆过滤器的核心区别在哪，翻了评论和老师解答后（特别是@峰)才逐渐明晰，区别核心的不同仍然是应用场景以及其中衍生的一个“阈值”： 老师讲的元素是否存在，比较学术风，换个业务场景来看，假设有个网站，用户id是64位长整整型，需要记录每天有哪些用户登陆了，假设用户总量1亿，日活有5千万，则如果使用普通的集合或者哈希表存储用户id，64*10^8=400M，这还是一天的登录数据，但是如果用位图，则是 1*10^8 = 12.5M 即可。400 / 12.5 = 32，也就是老师讲的 1/32 的空间消耗。 在这个场景下，位图看起来是吊打集合与散列表，但是如果日活只有可怜的10万，这时候重新计算，使用集合或散列表，64*10^8 = 800k，而位图则依然是12.5M。这时候位图被吊打，就是因为场景下其实有个关键的阈值：用户数据规模大小与日活大小。 总结来看，节省哈希函数的耗时，是位图固有的优势，而是否节省空间，则只有分析过数据的实际场景，才能决策出合适的数据存储方案，使检索达到空间和时间的最佳。 正好回复评论区@gogo同学问的什么语言有位图的实现：Redis的Bitmap就是位图实现的一种，而且还提供了位图的交集差集等api，值得一看。以上的场景也是参考Redis书籍描述的。 至于布隆过滤器，刚开始因为觉得既然都使用了哈希函数，那本质上和散列表不就是一样了？同样是刷了评论区才反应过来，重点在于K个哈希函数，不仅仅是在概率上降低了哈希冲突，而且因为需要K个位置来确定一个元素，所以可以用更小的范围来映射同样的数据规模，因此布隆过滤器在时间和空间的平衡上，感觉算是最折中的，不知这样理解是否合适，还望老师指点。 另外搬运Wiki上一段关于布隆过滤器优点的描述，我觉得切入点不错，还考虑到了（硬件以及数据安全性）： 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 O(k)。另外，散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。作者回复: 你的理解没错，其实我在几个评论中都有说，其实哈希表，位图，布隆过滤器的边界很模糊，可以相互转换。 布隆过滤器和和哈希表相比，有两个区别，一个是每个位置存储的是一个bit，不是一个具体value；另一个是同时使用k个哈希函数。 但如果我们将布隆过滤器和哈希表都改一下，比如说布隆过滤器的k取值为1，然后哈希表也不存具体value，而是存一个bit表示元素是否存在，那么它们就是完全一样了。你说这样的数据结构是叫做哈希表好?还是叫做布隆过滤器好? 因此，只要你能明白它们各自的特点，能在合适的场景使用合适的方案就好了。
2020-04-13313
aoe看了大家的留言，老师的回复，感慨一下：原来布隆过滤器不能随便删，可以周期性重构数据！作者回复: 对的，数据变化不频繁的情况下，周期性重建就好。
2020-04-0210
徐洲更因为同一个ID经过哈希函数会得到多个位置，不同的ID可能会有一些位置overlap。如果ID A和B刚好有一个位置重合，那么删除A的时候，如果直接将它对应的位置清零，就导致B也被认为是不存在。因此bloom filter删除操作很麻烦作者回复: 是的。bloom filter的删除会很麻烦。我们一般用在数据不删除的场景中（比如文中举的注册ID的场景）。 如果真要删除，可以使用上一课提到的re－hash的思路重新生成。（因为bloom filter本来就允许错误率，因此可以周期性重新生成）。 此外，还可以将bloomfilter改造成带引用计数的。
2020-03-3037
真名不叫黄金如果布隆过滤器要支持删除，那么就必须支持计数，那么相应地会增加占用存储空间，因为不能再用一个bit表示了。 因此不需要支持删除的布隆过滤器是将它节省空间的优势发挥到了极致，在基于LSM Tree的数据库中，就会使用布隆过滤器，这种基于追加写的数据结构本身查询会变慢，但恰巧由于它是追加写，不存在删除问题，因此可以生成布隆过滤器加速查找，因此布隆过滤器与LSM Tree是一个很适合的组合～作者回复: 你说得很对。许多系统设计中，都会尽量避免删除操作，因此，对于这类系统而言，搭配布隆过滤器是非常合适的。 至于数据删除问题，其实就和lsm树一样，采用批量更新的方式就好，对于布隆过滤器而言，就是重新生成一次。
2020-04-126
piboyecbf可以支持删除操作，但是取多少bit是怎么计算的？作者回复: 当使用count bloomfilter的时候，bit位的取值越大，count溢出的概率就会越低。 bit的位数的溢出率是有公式的(这里不好编辑公式，可以网上搜)。当位数取4的时候，溢出率小于1.37*(10^－15)*m，其中m为数组大小。这是一个很小的概率了。因此一般取4就好了。而如果想要更小，比如取2，那按公式推出来溢出率其实非常高。因此一般都会取4。
2020-09-234
CycleGAN老师非常有条理脉络清晰，评论也非常认真，受益匪浅作者回复: 谢谢支持。由于篇幅限制，我相信文章中总会有没有说清楚的地方，因此评论区是我认为一个很重要的补充环节。 此外，我还会在部落中会对文章的内容进行一些简单的延伸描述。这部分内容可以通过我的个人主页看到。希望对大家有所帮助。
2020-04-204
mickey如果位图中一个元素被删除了，我们可以将对应 bit 位置为 0。但如果布隆过滤器中一个元素被删除了，我们直接将对应的 k 个 bit 位置为 0，会产生什么样的问题呢？为什么？ 因为这样可能导致其他存在的元素的bit值置为0，从而导致已经存在的元素被后续判断为不存在。作者回复: 是的。因此布隆过滤器不能直接删除元素。如果真有删除的需求，就需要重新生成布隆过滤器。
2020-06-231- ヾ(◍°∇°◍)ﾉﾞ用户的id作为数组下标，需要id事先被约定过已知的吧？一般用户注册的id未知的吧，那么怎么事先会有一个已用户id作为下标的数组呢？不是很理解。望老师在细说一下
作者回复: 一般用户注册的ID是未知的，但是会有一个范围。比如说，如果系统有限定最多只会有一万个用户的话，那么ID就一定在一万之内;再比如说，如果用户的ID的数据类型是int32的话，那么最大值也就是2^32，用一个512m字节的位图就肯定可以表示。 因此，我们可以通过ID的范围，来提前生成好足够大的数组或位图，这样就可以直接使用ID作为数组下标，而不用担心数组越界问题。
2020-06-091