我正在编写 Haxe C# 目标，并且一直在研究 Haxe 的 std 库的性能差异，以便我们可以通过其跨平台代码提供尽可能最佳的性能。
哈希表代码就是一个很好的例子。我有点不愿意使用 .NET 的字典，因为它看起来很庞大（由于内存对齐问题，键/值对的结构可能会占用大量内存，除了它保存的不必要的信息之外），并且因为在 std库中没有对象哈希这样的东西，我真的认为我可以通过不必调用 GetHashCode 并一直内联它来压缩一点性能。
而且很明显，Dictionary 实现使用链表来处理冲突，这远非理想。
所以我们开始实现我们自己的解决方案，从IntHash（字典）开始
我们首先实现了跳房子哈希，但结果确实不是很好，但很明显它不能很好地支持巨大的哈希表，因为 H 通常是机器字，并且随着 H / Length 的增加，性能越差。
然后我们开始实施khash- 启发算法。这个有很大的潜力，因为它的基准测试令人印象深刻，并且它可以处理同一阵列上的冲突。它还有一些很棒的功能，比如调整大小而不需要我们两倍的内存。
基准测试令人失望。当然，不用说我们的实现中的内存使用量比 Dictionary 的要低得多。但我也希望能获得不错的性能提升，但不幸的是事实并非如此。并没有低太多——不到一个数量级——但是对于 set 和 gets 来说，.NET 的实现仍然表现得更好。
所以我的问题是：这是我们对 C# 最好的吗？我尝试寻找任何自定义解决方案，但似乎几乎没有。有那个C5通用集合，但是代码太混乱了我什至没有测试。我也没有找到基准。
那么……是这样吗？我应该绕过去吗Dictionary<>?
我发现.NETDictionary在大多数情况下，即使不是特别好，也表现良好。这是一个很好的通用实现。我最常遇到的问题是 2 GB 的限制。在 64 位系统上，您不能向字典中添加超过大约 8950 万个项目（当键是整数或引用，并且值是引用时）。字典开销似乎是每个项目 24 字节。
这个限制以一种非常奇怪的方式为人所知。这Dictionary似乎是通过加倍来增长——当它满了时，它会增加下一个素数的容量，该素数至少是当前大小的两倍。因此，字典将增长到大约 4700 万，然后抛出异常，因为当它尝试加倍（达到 9400 万）时，内存分配失败（由于 2 GB 限制）。我通过预先分配来解决这个问题Dictionary（即调用让您指定容量的构造函数）。这也加快了填充字典的速度，因为它永远不需要增长，这需要分配一个新的数组并重新散列所有内容。
是什么让你这么说Dictionary使用链表来解决冲突？我很确定它使用开放寻址，但我不知道它是如何进行探测的。我想如果它进行线性探测，那么效果类似于使用链表得到的效果。
我们自己写的BigDictionary类突破了 2 GB 的限制，并发现带有线性探测的简单开放寻址方案可提供相当好的性能。它没有那么快Dictionary，但它可以处理数亿个项目（如果我有记忆的话，可以处理数十亿个项目）。
也就是说，你should能够编写更快的特定于任务的哈希表，在某些情况下其性能优于 .NET 字典。但对于通用哈希表，我认为您很难做得比 BCL 提供的更好。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
