快速的基于磁盘的哈希表？

Question

我有一组哈希(MD5的前64位,所以它们是非常随机分布的)我希望能够看到一个新的哈希是否在一个集合中,并将它添加到一个集合中.

集合不是太大,最大的将是数百万个元素,但是有数百个集合,所以我无法将它们全部保存在内存中.

到目前为止我有一些想法:

• 我试着将它全部保存在sqlite表中,但是一旦它无法适应内存中的所有内容,它就变得非常慢.
• 布隆过滤器听起来像是会有很高的错误率.我不介意微小的错误率(64位散列已经在4G元素集上发生了1次冲突),但错误率如1%则太高了.
• 保持文件中具有间隙的哈希的排序列表,并在没有足够的间隙时调整大小.哈希是均匀分布的,所以即使非常简单的方案也应该有效.

我错过了一些非常明显的东西吗 任何提示如何实现良好的基于​​磁盘的哈希表？

Answer 1

这是我最终使用的解决方案:

• 每套一个文件
• 文件包含2 ^ k个桶,每个256字节或32个8字节的条目
• 空条目刚刚清零(000 ...是一个有效的哈希值,但我并不关心2 ^ -64碰撞的可能性,如果一切都可以与哈希的本质相冲突).
• 每个哈希驻留在通过其前k位猜测的桶中
• 如果任何存储桶溢出,请将文件大小翻倍并拆分每个存储桶
• 一切都是通过mmap()访问的,而不是read()/ write()

它比sqlite快得令人难以置信,即使它是低级别的Perl代码,Perl实际上并不适用于高性能数据库.它不适用于任何比MD5分布更不均匀的东西,它假设一切都非常均匀,以保持实现简单.

我一开始尝试使用seek()/ sysread()/ syswrite(),而且速度很慢,mmap()版本真的要快得多.

Answer 2

我在描述您的确切问题/需求时遇到了一些麻烦,但它仍然让我想到了Git以及它如何在磁盘上存储SHA1引用:

获取给定哈希的十六进制字符串表示,例如" abfab0da6f4ebc23cb15e04ff500ed54".在哈希中键入两个第一个字符(ab在我们的例子中为" ")并将其放入目录中.然后,使用其余的(" fab0da6f4ebc23cb15e04ff500ed54"),创建文件,并将内容放入其中.

这样,通过自动索引,您可以在磁盘上获得相当不错的性能(取决于您的FS).此外,您可以直接访问任何已知的哈希,只需在两个第一个字符(" ./ab/fab0da[..]" 之后楔入目录分隔符)

如果我完全错过了球,我很抱歉,但运气好的话,这可能会给你一个想法.

Answer 3

听起来像Berkeley DB的工作.