快速查找哈希映射实现

Question

我正在LLVM之上实现一种编程语言。对于我的多态系统，我正在寻找一个超快字典的建议。我不关心插入时间，因为这些地图只写了十几次左右。但我在找超快的查找。

我对Python中的开放寻址dict实现做了一些研究，它看起来相当快(最好的情况下是几次转换和位掩码)。然而，我想做我的研究。有人知道超快的字典/hashmap实现吗？

在这种情况下，我的数据很可能是指针作为键，指针作为值。或者如果结果更好的话，我也许可以用整数作为键。任何关于这个主题的论文或讨论都是很棒的。

Answer 1

您可以快速查看"Cuckoo散列“--如果它有效，可以保证持续查找时间(与大多数散列方案(如开放寻址)不同)。当然，它也不是没有自己的问题，但考虑到您的插入/查找首选项，它可能值得研究。

关于wiki的文章：http://en.wikipedia.org/wiki/Cuckoo_散列

尽管你可能已经考虑过，线性探测也有它的优点--相对于按顺序扫描内存的OA，这当然比OA的随机访问快得多(当然，其他因素也会影响到这一点)。

最后，有一些方案可以创建完美的哈希表--它们的构造通常非常缓慢，但可以保证恒定的时间查找。

我不会链接到任何文件或文章，但搜索谷歌:杜鹃哈希，线性探测，完美散列