c# - 关于时间和空间: Bloom filter, Hash table和Dictionary哪个好？

Question

我需要在 C# 中存储 4000 个固定大小(8 个字符)的字符串，但我不知道关于添加和检索项目的空间和时间最好使用什么:布隆过滤器、哈希表或字典？如果有人可以帮助我，请帮助我

Answer 1

在这个问题中，您在 C# 中实际上只有两个数据结构，因为 C# 中的字典是使用哈希表实现的。所以我们将 Dictionary 和 HashTable 都称为哈希表。如果您使用其中之一，那么由于类型安全和性能，您可能需要 Dictionary，如此处所述:Why is Dictionary preferred over hashtable?但由于 Dictionary 是使用哈希表实现的，因此这两种方式都没有太大区别。

但真正的问题是哈希表(字典)与布隆过滤器。之前有人问过相关问题，What is the advantage to using bloom filters?他们还链接到关于 Bloom 过滤器的维基百科页面，该页面信息量很大:https://en.wikipedia.org/wiki/Bloom_filter答案的简短版本是布隆过滤器更小更快。然而，它们确实有与此相关的成本:它们并不完全准确。在哈希表中，始终存储原始字符串以进行精确比较。首先对值进行哈希处理，这会告诉您在表中的哪个位置查找。查看表格后，您可以根据要搜索的值检查位于该表中的值。在布隆过滤器中，您使用多个哈希来计算一组位置。如果所有这些位置都有 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%。

所以，实际上，在您的情况下，为了获得一点速度和一点时间而损失一些准确性的权衡是否值得，完全取决于您。实际上，对于绝大多数现实世界情况，任一选项都可能足够小且足够快。