System.Collections.Generic.Dictionary =终极表现？
我正在编写一个haXe C＃目标，我一直在研究haXe的std库的性能差异，因此我们可以通过其跨平台代码提供最佳性能。
一个非常好的例子是哈希表代码。 我有点不情愿使用.NET的字典，因为它看起来很笨重（键/值对的结构可能占用大量的内存，因为内存对齐问题，除了它所持有的不必要的信息），并且因为在std上库没有对象哈希这样的东西，我真的以为我可以通过不必调用GetHashCode来压缩一点性能，并一直内联它。
同样很明显，Dictionary实现使用链表来处理冲突，这远非理想。
所以我们开始实现我们自己的解决方案，从IntHash（Dictionary）开始我们首先实现了Hopscotch哈希 ，但实际上并没有很好，但很明显它不支持非常好的哈希表，因为H通常是机器字，并且随着H /长度的增加，性能越差。
然后我们跳转到实现khash -inspired算法。 这个具有很大的潜力，因为它的基准测试令人印象深刻，并且它处理同一arrays上的冲突。 它还有一些很棒的东西，比如resize而不需要像我们那样需要两倍的内存。
基准令人失望。 当然，没有必要说我们的实现中的内存使用量远低于Dictionary的内存使用率。 但我希望也能获得不错的性能提升，但不幸的是情况并非如此。 它不是太低 – 不到一个数量级 – 但对于两组和得分，.NET的实现仍然表现得更好。
所以我的问题是：这是我们对C＃的最佳选择吗？ 我试着寻找任何自定义解决方案，似乎几乎没有。 有C5通用集合，但代码是如此混乱，我甚至没有测试。 我也找不到基准。
那么……是吗？ 我应该包裹Dictionary 吗？
谢谢！！！
我发现.NET Dictionary在大多数情况下表现良好，如果不是特别好的话。 这是一个很好的通用实现。 我经常遇到的问题是2千兆字节的限制。 在64位系统上，您不能向字典添加超过约8950万个项目（当键是整数或引用时，该值是引用）。 字典开销似乎是每个项目24个字节。
这种限制使自己以一种非常奇怪的方式出现。 Dictionary似乎通过加倍而增长 – 当它变满时，它会增加到下一个素数的容量，该素数至少是当前大小的两倍。 因此，字典将增长到大约4700万，然后抛出exception，因为当它试图加倍（到9400万）时，内存分配失败（由于2千兆字节的限制）。 我通过预先分配Dictionary来解决问题（即调用允许您指定容量的构造函数）。 这也加速了字典的填充，因为它永远不会增长，这需要分配一个新的数组并重新散列所有内容。
是什么让你说Dictionary使用链表进行冲突解决？ 我很确定它使用开放寻址，但我不知道它是如何进行探测的。 我想如果它进行线性探测，那么效果类似于链接列表的效果。
我们编写了自己的BigDictionary类来超过2 GB的限制，发现一个简单的开放式寻址方案，线性探测可以提供相当好的性能。 它没有Dictionary那么快，但它可以处理数以亿计的项目（如果我有内存，可以处理数十亿）。
也就是说，在某些情况下，您应该能够编写一个更快的特定于任务的哈希表，该表优于.NET词典。 但对于通用哈希表，我认为你很难比BCL提供的更好。
在设计“更好”的哈希表时需要考虑很多事情。 您尝试的自定义方法的原因之一是比.NET字典更慢或没有更好，因为哈希表的性能通常非常依赖于：
- 正在散列的数据
- 哈希函数的性能
- 表的加载因子
- 碰撞次数与非碰撞次数
- 用于冲突解决的算法
- 表中的数据量及其存储方式（通过指针/引用或直接在存储桶中）
- 数据的访问模式
- 插入/删除与检索的数量
- 需要在封闭的散列/开放寻址实现中resize
- 和许多其他因素……
有这么多东西要调整和调整，很难，没有大量的努力来提出一般的高性能（时间和速度）哈希表。 这就是为什么，如果你打算尝试创建一个自定义哈希表而不是一个内置到标准库（如.NET）中的哈希表，请准备花费无数个小时，并注意你的精心调整的实现可能只针对您正在散列的特定类型和数据量。
因此，不，.NET Dictionary不是用于任何特定目的的最终哈希表。 但是，考虑到字典使用的频率，我确信Microsoft BCL（基类库）团队执行了大量的分析，以选择他们为一般情况选择的方法。