使用布隆过滤器有什么好处?
我正在阅读布隆过滤器，但它们看起来很傻.您可以使用布隆过滤器完成的任何事情，您都可以使用单个哈希函数而不是多个哈希函数，以更少的空间、更高效地完成，或者看起来就是这样.为什么要使用布隆过滤器，它有什么用处? 解决方案 来自维基百科: 布隆过滤器有很强的空间优于其他数据结构用于表示集合，例如自平衡二叉搜索树，尝试、哈希表或简单数组或条目的链接列表.最多其中至少需要存储数据项本身，可以需
..
bloom-filter相关内容
什么是异或过滤器?
有一种相对较新的数据结构 (2020)，称为 XOR 过滤器 被用作布隆过滤器的替代品. 什么是异或过滤器?与布隆过滤器相比，它有哪些优势?它是如何工作的? 解决方案 XOR 过滤器被设计为在预先知道要存储在过滤器中的所有项目的情况下替代布隆过滤器.与布隆过滤器一样，它代表一个集合的近似值，其中不允许出现假阴性，但允许出现假阳性. 与布隆过滤器一样，异或过滤器存储大量位.然而，
..
python位数组(高性能)
我正在设计一个布隆过滤器，我想知道 Python 中性能最高的位数组实现是什么. Python 的好处是它可以开箱即用地处理任意长度的整数，这就是我现在使用的，但我对 Python 内部结构的了解不够，不知道这是否是在 Python 中执行此操作的最佳方法. 我发现了 bitarray 但它处理了很多其他事情，比如切片，我不知道不需要.我只需要 & 和 | 和
..
查找大小为n的两个集合A和B之差的算法
有两个集合A和B，两个集合的大小均为n.如何用O(n)查找A中不在B(A-B)中的每个元素.我应该使用哪种数据结构(bloom过滤器?) 解决方案 鉴于两者都是集合，您应该使用集合/哈希集.这将让您计算O(1)中的contains/in操作.布隆过滤器不适用于此类问题-它们会告诉您某个元素是否绝对不在一组对象中，但仍有可能出现误报.最好使用常规的哈希集，因为您想要一个准确的答案. 给
..
非重复随机数
我需要生成大约9到1亿个非重复的随机数，范围从零到生成的数量不等，而且我需要非常快地生成它们.提出了一些类似问题的答案，只是简单地对数组进行改组以获得随机数，而提出的其他问题则使用布隆过滤器.问题是，哪一个效率更高?如果是布隆过滤器，该如何使用? 解决方案 您根本不需要随机数.您需要精确地将数字0到N-1随机排列. 简单地填充数组并改组应该很快.正确的Fisher-Yates洗牌是O
..
使用Python的现代，高性能Bloom过滤器?
我正在寻找一种Python中的生产质量Bloom过滤器实现，以处理相当多的项目(例如100M到1B的项目，其误报率为0.01％). Pybloom 是一种选择，但由于它会抛出DeprecationWarning错误，因此似乎正在显示其年龄定期使用Python 2.5. Joe Gregorio还具有实现. 要求是快速查找性能和稳定性.我也愿意为特别好的c/c ++实现创建Python接
..
为什么布隆过滤器需要多个哈希函数？
我不明白为什么bloom过滤器需要多个散列函数（比如SHA和MD5）。 为什么不只是例如，创建一个更大的 SHA散列，然后将其分解为多个部分并将它们视为单独的散列？在速度方面效率不是很高吗？解析方案 这个想法是使用几种不同但简单的哈希函数。如果你打算使用SHA或MD5等密码散列函数，那么你可以改变它的输入。是否更高效取决于你的散列函数的复杂程度。
..
对Bloom过滤器使用散列函数
布隆过滤器使用散列函数（或多个）在给定输入字符串X的情况下生成介于0和m之间的值。我的问题是如何使用散列函数以这种方式生成值，例如MD5散列通常用32长度十六进制字符串表示，我将如何使用MD5散列算法来生成介于0和m之间的值，我可以指定m？我现在正在使用Java，所以使用它提供的MessageDigest功能来做这件事的例子会很棒，但如何做的一般性描述也没关系。 谢谢 解决方案 您应
..
需要内存高效的方式来存储吨字符串（是：在Java中的HAT-Trie实现）
我正在处理大量的（5-20万）字符串键（平均长度为10个字符），我需要将它们存储在内存数据结构中在常量时间或接近常量的时间内支持以下操作： //如果输入存在于容器中，则返回true，否则返回false public boolean contains（String input） Java的HashMap被证明不仅仅是就吞吐量而言令人满意，但占用大量内存。我正在寻找一
..
数据流中的重复检测
我目前正在研究一种生成大量文本内容的流式API。正如预期的那样，API给出了很多重复，我们也有一个业务要求来过滤重复的数据。 我对数据中的重复检测做了一些研究流，并阅读关于稳定的布隆过滤器。稳定的绽放过滤器是数据流中重复检测的数据结构，其上限为假阳性率。 但是，我想识别几乎重复的内容，我也看了哈希算法，如LSH和MinHash，用于近邻问题和近似重复检测。 我有点困惑，寻找关于如
..
Bloom Filter：评估假阳性率
给定固定数量的位（例如，槽）（m）和固定数量的散列函数（k），如何计算理论假阳性率（p）？ 根据维基百科 http://en.wikipedia.org/wiki/Bloom_filter ，对于假阳性率（p）和项数（n），所需的位数（m）由下式给出： m = - n * l（p）/（l（2） ^ 2），并且最优数目的散列函数（k）由 k = m / n * l（2）给出。 > 从维基
..
有没有任何概率数据结构假阴性而不是假阳性？
我需要一个空间有效的概率数据结构来存储我已经计算的值。对我来说，计算价格便宜但空间不大 - 所以如果这个数据结构返回一个假的负数，我可以在一段时间内每隔一段时间重做一些工作，但是误报是不可接受的。所以我正在寻找的是与 Bloom filter 相反的。 解决方案 对于假阴性，您可以使用有损哈希表或LRUCache。 它是一个具有快速O（1）查找的数据结构，只会产生错误的否定。 如果您问
..
布鲁姆过滤器对面？
我试图优化一个基本上运行数百万个测试的软件。这些测试的生成方式可能会有一些重复。当然，我不想花时间运行我已经运行的测试，如果我可以有效地避免它。 所以，我正在考虑使用一个布鲁姆过滤器存储已经运行的测试。但是，Bloom过滤器对我来说是不安全的。它给出了错误的肯定。也就是说，它可能会报告我已经进行了一个我没有的测试。虽然这在我正在工作的情况下是可以接受的，但我想知道是否有相当于Bloom过滤器
..
使用布隆过滤器有什么优势？
我正在阅读绽放过滤器，他们似乎很傻。任何你可以用绽放过滤器完成的任务，你可以用更少的空间，更有效地完成，使用单个散列函数而不是多个，或者这就是它的样子。为什么要使用一个bloom过滤器，它是如何有用的？ 解决方案 从维基百科： 布鲁姆过滤器有一个强大的空间 优于其他数据结构 表示集合，例如 自平衡二叉搜索树， 尝试，哈希表或简单数组 或条目的链表。大多数 需要至少存储
..
Bloomfilter和Cassandra =为什么使用和为什么散列几次？
我阅读： http：/ /spyced.blogspot.com/2009/01/all-you-ever-wanted-to-know-about.html 我的问题： 1。）是正确的，Cassandra只使用bloom过滤器，找出最可能包含key的SST（Sorted String Table）因为可能有几个SST，Cassandra不知道在哪个SST可能是一个密钥？所以要加快这
..
C ++将dynamic_bitset存储到文件中
排序后续如何存储一个向量 基本上，我写一个bitset作为二进制文件，具有以下代码： boost :: dynamic_bitset :: block_type>过滤; vector :: block_type> filterBlocks（filter.num
..
如何散列函数的输出映射到bloomfilter指数？
谁能帮我提供的散列函数的输出是如何映射到布隆过滤指数的轮廓？这里是 bloomfilters 。概述 解决方案 在散列函数的输出是如何映射到布隆过滤器索引大纲 对于每个 K 的散列函数的使用，它们映射到在布隆过滤器有点就像哈希映射到散列桶中的哈希表。所以，很常见的，你可能有发言权的哈希函数生成的32位整数，然后用模％运营商变得有点指数 0℃;＆LT ; I＆LT; ñ，其中 N 是在你的
..
布鲁姆过滤器的使用
我在努力了解布隆过滤器的有效性。我得到它的基本逻辑，空间压缩，快速查找，误报等我只是不能把这个概念变成现实生活中的情况作为是有益的。一个常见的应用是在Web缓存使用布隆过滤器。我们使用布隆过滤器来确定一个给定的URL是否是在高速缓存中或没有。为什么我们不只是访问缓存来确定？如果我们得到一个肯定，我们仍然需要到高速缓存中检索网页（这可能不是在那里），但如果一个没有，我们可以得到使用缓存（这可能是
..