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