c# - 在 C# 中有两个散列函数的字典？

Question

我有一个巨大的 (>>10m) 条目列表。每个条目都提供两个哈希函数:

• 廉价:快速计算散列，但其分布很糟糕(可能将 99% 的项目放在 1% 的散列空间中)
• 昂贵:计算需要很多时间，但分布也好很多

一个普通的字典让我只能使用这些哈希函数中的一个。我想要一个首先使用便宜的散列函数的字典，然后在冲突时检查昂贵的散列函数。

为此，在字典中使用字典似乎是个好主意。我目前基本上使用这个怪物:

Dictionary<int, Dictionary<int, List<Foo>>>;

我改进了这个设计，所以只有当实际上有两个相同的廉价散列项时才会调用昂贵的散列。

它非常适合我，工作完美无瑕，但它看起来像是本该在 6500 万年前就死去的东西。

据我所知，此功能不包含在基本框架中。我即将编写一个 DoubleHashedDictionary 类，但我想先了解您的意见。

至于我的具体情况:
第一个哈希函数 = 文件系统目录中的文件数(快)第二个哈希函数 = 文件大小的总和(慢)

编辑:

• 更改了标题并添加了更多信息。
• 添加了非常重要的遗漏细节

Answer 1

在您的情况下，您在技术上使用的是修改后的函数 (A|B)，而不是双重哈希。但是，根据您的“庞大”条目列表的大小和数据的特征，请考虑以下事项:

• 一个 20% 满度的哈希表，其分布不太好，发生冲突的可能性超过 80%。这意味着您的预期功能成本可能是:(0.8 昂贵 + 0.2 便宜)+(查找成本)。因此，如果您的表已满 20% 以上，则可能不值得使用 (A|B) 方案。

• 想出一个完美的哈希函数是可能的，但 O(n^3) 使得它不切实际。

• 如果性能极其重要，您可以通过在关键数据上测试各种哈希函数来为您的特定数据制作经过专门调整的哈希表。