一个很好的例子是哈希表代码.我有点不情愿使用.NET的字典,因为它似乎很庞大(由于内存对齐问题,key / value对的结构可能会占用大量的内存,除了它所持有的不必要的信息),因为在std图书馆没有像对象哈希这样的东西,我真的以为我可以通过不必调用GetHashCode,并且一直内联来挤压一点表现.
同样很明显的是,Dictionary实现使用一个链表来处理碰撞,这是远非理想的.
所以我们开始实现自己的解决方案,从IntHash(Dictionary)开始,
我们首先实现了Hopscotch hashing,但实际并没有很好的表现,但是很明显,它不会支持非常好的巨大哈希表,因为H通常是一个机器字,并且随着H / Length的增加,表现较差
然后,我们跳过了实现一个khash启发的算法.这一个有很大的潜力,因为它的基准是令人印象深刻的,它处理同一阵列的冲突.它也有一些伟大的事情,像调整大小,而不需要两倍的记忆.
基准令人失望.当然,没有必要说我们的实现的内存使用比Dictionary更低.但是,我希望能够获得良好的表现,但不幸的是,情况并非如此.它不是太低于一个数量级 – 但是对于这两个集合,.NET的实现仍然表现更好.
所以我的问题是：C#中最好的我试着寻找任何定制解决方案,似乎几乎没有.有一个C5通用集合,但代码是如此混乱,我甚至没有测试.我也没有发现基准.
那么是吗？我应该只是围绕Dictionary<>？
谢谢！！！
解决方法
这个限制使得自己以非常奇怪的方式知道.字典似乎增长了一倍 – 当它变满时,它增加了下一个素数的容量,至少是当前大小的两倍.因此,字典将增长到约4700万,然后抛出异常,因为当它尝试加倍(到9400万)时,内存分配失败(由于2 GB的限制).我通过预先分配Dictionary来解决问题(即调用允许您指定容量的构造函数).这也加速了字典的填充,因为它从来没有增长,这需要分配一个新的数组并重新进行一切.
什么让你说Dictionary使用链表进行碰撞解决？我很确定它使用开放式寻址,但我不知道它是如何做的.我猜,如果它是线性探测,那么效果类似于你会得到一个链表.
我们写了我们自己的BigDictionary类以获得超过2 GB的限制,发现一个直接的开放式寻址方案具有线性探测性能.它不如Dictionary一样快,但它可以处理数亿件物品(如果我有记忆数十亿).
也就是说,在某些情况下,您应该能够编写一个速度更快的任务特定的哈希表,其表现优于.NET字典.但是对于一个通用的哈希表,我认为你会很难做到比BCL提供的更好.
