hash - OpenCL 的完美散列

Question

我有一个大约 200 万个值的集合（静态，在编译时已知），每个值 20 个字节。我需要的是一种快速的 O(1) 方法来检查给定值是否在这个集合中。似乎带有位数组的完美散列函数是理想的，但我找不到一种简单的方法来创建它。有一些实用程序，例如 gperf，但它们太复杂了。此外，在我的情况下，不需要接近 100% 的负载系数，即使 10% 也足够了，但要保证没有碰撞。此功能的另一个要求是简单，无需太多条件：它将在 GPU 上运行。你对这个案子有什么建议？

Answer 1

在这里查看我的答案。问题有点不同，但可以根据您的需要定制解决方案。原始版本使用 100% 的负载系数，但可以轻松更改。它通过在启动时就地改组数组来工作（这可以在编译时完成，但这意味着编译生成的代码）。

WRT 哈希函数：如果您对 20 字节对象的内容一无所知，任何合理的哈希函数（FNV、Jenkins 或我的）都足够了。

Answer 2

在阅读了有关完美哈希的更多信息后，我决定不尝试实现它，而是使用 cuckoo hashtable。它要简单得多，最多需要 2 次访问表（或任何其他数字 >1，最常用的是 2..5）而不是 1 次才能实现完美哈希。