c# – 哪个最好的时间和空间：布鲁姆过滤器,哈希表或字典？

在这个问题中,你真的只有C#中的两个数据结构,因为C#中的字典是使用哈希表来实现的.所以我们将引用Dictionary和HashTable作为哈希表.如果你使用其中的一个,那么你可能希望Dictionary由于类型的安全性和性能如下所示： Why is Dictionary preferred over hashtable?但是作为一个字典是使用哈希表实现的,两者之间并不是很大的区别.

但真正的问题是哈希表(Dictionary)与Bloom过滤器.有人曾经问过相关的问题,What is the advantage to using bloom filters?他们还链接到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％的错误率时,这意味着在每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％.

那么真的,由你自己决定,在你的情况下,如何获得一定的准确性,一点点的速度和一点时间就是值得的.实际上,对于绝大多数现实世界的情况,任何一种选择都可能足够小,足够快.