我有一组哈希值(MD5 的前 64 位，因此它们分布非常随机)，我希望能够查看新哈希值是否在一组中，并将其添加到一组中。
集合不太大，最大的元素有数百万个，但是集合有数百个，所以我无法将它们全部保存在内存中。
到目前为止我的一些想法:
- 我尝试将所有内容都保存在 sqlite 表中，但是一旦它无法容纳内存中的所有内容，它就会变得非常非常慢。
- 布隆过滤器听起来错误率非常高。我不介意微小的错误率(64 位哈希已经在 4G 元素集上产生了 1 次冲突)，但像 1% 这样的错误率太高了。
- 在文件中保留带有间隙的哈希值的排序列表，并在间隙不足时调整大小。哈希值是均匀分布的，因此即使是非常简单的方案也应该有效。
我是否遗漏了一些非常明显的东西？关于如何实现良好的基于磁盘的哈希表有任何提示吗？
最佳答案
这是我最终使用的解决方案:
- 每组一个文件
- 文件包含 2^k 个桶，每个桶 256 字节或 32 个 8 字节条目
- 空条目只是被清零(000...是一个有效的散列，但我不关心 2^-64 的碰撞机会，如果一切都可以与其他一切发生冲突，根据散列的本质)。
- 每个哈希都驻留在通过其前 k 位猜测的存储桶中
- 如果任何存储桶溢出，则将文件大小加倍并拆分每个存储桶
- 所有内容都是通过 mmap() 访问的，而不是 read()/write()
它比 sqlite 快得令人难以置信，尽管它是低级 Perl 代码，而且 Perl 确实不适合高性能数据库。它不适用于任何比 MD5 分布更不均匀的东西，它假设一切都非常均匀以保持实现简单。
一开始我用seek()/sysread()/syswrite()尝试过，速度很慢，mmap()版本确实快很多。
关于hashtable - 基于磁盘的快速哈希表？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/495161/