关于时间和空间哪个最好:布隆过滤器,哈希表或字典？

Question

我需要在C#中存储4000字符串的固定大小(8-char),但我不知道在添加和检索项目的空间和时间方面最好用什么:Bloom过滤器,哈希表或字典？如果有人可以帮助我

Answer 1

在这个问题中,你实际上在C#中只有两个数据结构,因为C#中的字典是使用哈希表实现的.所以我们将Dictionary和HashTable都称为哈希表.如果您使用其中之一,那么您可能需要Dictionary,因为此处介绍了类型安全性和性能:为什么Dictionary优先于哈希表？ 但是,由于使用哈希表实现了字典,因此无论如何都不是一个巨大的差异.

但真正的问题是哈希表(字典)与布隆过滤器.之前有人问过相关问题,使用bloom过滤器有什么好处？ 他们还链接到Bloom过滤器上的维基百科页面,这是非常有用的信息:https://en.wikipedia.org/wiki/Bloom_filter答案的简短版本是Bloom过滤器更小更快.但是,他们确实有与此相关的成本:它们并不完全准确.在哈希表中,始终存储原始字符串以进行精确比较.首先,您对值进行哈希处理,这会告诉您表中的位置.一旦你查看了表格,然后根据你要搜索的值检查那里的值.在Bloom过滤器中,您使用多个哈希来计算一组位置.如果所有这些位置都有1,那么您可以考虑找到该字符串.这意味着有时会找到最初未插入的字符串.如果表太小,实际上,您可以达到饱和点,看起来您尝试过的任何字符串都在Bloom过滤器中.因为您知道要插入多少个字符串,所以可以适当调整表的大小以避免这种情况.

我们来看看所涉及的尺寸.为了使数字干净利落,我将假装你有4096个字符串.要拥有一个相对较低的冲突哈希表,您希望您的表至少与字符串数一样大.所以,实际上(假设32位(4字节)指针),在这种情况下,您将看到表的大小为4096*4字节= 16K,加上4096*(4 + 4 + 8)= 64K列表节点(下一个指针+字符串指针)和字符串.所以,总共可能大约80K,在大多数情况下你可能使用C#的内存可能不是很多.

对于Bloom过滤器,我们必须在我们的大小计算中确定我们想要的错误率.当我们谈论1%的错误率时,这意味着在没有插入Bloom过滤器的每100个字符串中,1将被错误地指示为存在.插入的字符串将始终正确显示为已插入.使用方程m = -n*ln(p)/(ln(2)^ 2),我们可以计算最小尺寸以给出一定的误差率.在该等式中,m是表中的槽数,p是错误率,n是要插入的字符串数.因此,如果我们将p设置为0.01(1%误差),那么我们得到大约9.6*4096位= 9.6*512字节= 4.8K,这显然相当小.但是,实际上,1%对于错误率来说有点高.更现实地说,我们应该寻找更像0.0001%的东西,它出现在28.8*4096b位= 28.8*512字节= 14.4K.显然,其中任何一个都远小于我们为哈希表计算的80K.但是,哈希表的错误率为0,明显小于1%或0.0001%.

所以,真的,在你的情况下,取决于你是否会因为获得一点速度和一点点时间而失去一些准确性是值得的.实际上,对于绝大多数现实世界的情况来说,任何一种选择都可能足够小且足够快.