我有一个16位无符号整数的列表。
我唯一想知道的是列表中是否有数字。
我可以用一个比特向量来表示。如果我在列表中，我只设置位[I]。要知道列表中是否有一个数字y，我会查找bit[y]。这将永远给出正确的答案。
但我想保存记忆。并且使用更少的比特，但允许误报。I.e一个数字会被允许返回它在列表中，即使它不在。但没有假阴性。
根据我的理解，布隆过滤器可以做到这一点。我不明白的是，当我使用bloom过滤器计算器时，通过设置例如：的概率
- 400个条目(n(
- 400位(m(
- 1散列函数(k(
假阳性的概率不是零。例如https://hur.st/bloomfilter/
例如，如果我平均有400个不同的16位数字，并且希望使用尽可能少的空间，那么bloom过滤器是个好主意吗？
人们应该如何看待这种可能性？很明显，一个比特矢量给出了16k比特的完美结果。我可以使用bloom过滤器少多少空间，以及增加误报的成本。
有更好的东西可以解决我的问题吗。
Bloom Filter很可能是您所需要的合适对象。空间要求是问题所在：
- 您必须有足够的元素使其合理(至少值得存储哈希函数生成器(，并且
- 足够的比特来将假阳性减少到可接受的水平
换句话说，不要专注于使用尽可能小的空间；而应该专注于使用足够的空间。如果没有自定义的、专门的过滤器，你仍然会使用比任何东西都少的空间。