27

我有一组散列（MD5 的前 64 位，所以它们的分布非常随机），我希望能够查看一个新的散列是否在一个集合中，并将其添加到一个集合中。

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

到目前为止我的一些想法：

  • 我尝试将其全部保存在 sqlite 表中，但是一旦它无法将所有内容都放入内存中，它就会变得非常慢。
  • 布隆过滤器听起来像它们会有非常高的错误率。我不介意微小的错误率（64 位哈希已经在 4G 元素集上产生了 1 次冲突），但是像 1% 这样的错误率太高了。
  • 在文件中保留带有间隙的散列排序列表，并在我没有足够的间隙时调整大小。哈希是均匀分布的，所以即使是这样非常简单的方案也应该可以工作。

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

4

6 回答 6

19

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

  • 每组一个文件
  • 文件包含 2^k 个桶，每个 256 字节或 32 个 8 字节的条目
  • 空条目只是被清零（000... 是一个有效的哈希，但我不关心 2^-64 的碰撞机会，如果所有内容都可以与其他所有内容发生冲突，由于哈希的性质）。
  • 每个哈希都驻留在通过其前 k 位猜测的桶中
  • 如果任何桶溢出，文件大小加倍并拆分每个桶
  • 一切都通过 mmap() 访问，而不是 read()/write()

它比 sqlite 快得令人难以置信，尽管它是低级 Perl 代码，而且 Perl 真的不适合高性能数据库。它不适用于比 MD5 分布更不均匀的任何东西，它假设一切都将非常统一以保持实现简单。

我一开始用 seek()/sysread()/syswrite() 试过，很慢，mmap() 版本真的快很多。

于 2009-02-03T22:23:10.290 回答
12

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

取给定哈希的十六进制字符串表示，例如“ abfab0da6f4ebc23cb15e04ff500ed54”。将散列中的前两个字符（ab在我们的例子中为“”）切掉，并将其放入一个目录中。然后，使用其余的（“ fab0da6f4ebc23cb15e04ff500ed54”），创建文件，并将内容放入其中。

这样，您可以通过自动索引获得相当不错的磁盘性能（自然取决于您的 FS）。此外，您可以直接访问任何已知的哈希，只需在前两个字符（“ ./ab/fab0da[..]”）之后插入目录分隔符

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

于 2009-02-03T22:32:51.597 回答
6

听起来像是Berkeley DB的工作。

于 2009-01-30T11:07:15.867 回答
3

其他基于磁盘的散列算法/数据结构包括线性散列和可扩展散列。

于 2011-12-22T03:11:16.893 回答
1

我首先想到了两种算法：

  • 使用b-tree。
  • 通过使用散列的前 10 位索引到 1024 个单独文件中的一个来分离散列本身，每个文件都包含从这 10 位开始的所有散列的排序列表。这使您可以恒定时间跳转到应该适合内存的块，并在加载该块后进行 log(n) 搜索。（或者您可以使用 8 位散列成 256 个文件等）
于 2009-01-30T11:11:44.937 回答
0

由于对于散列，您必须使用随机访问，我怀疑任何数据库都会为您提供不错的性能。您最好的选择可能是增加磁盘缓存（更多 RAM），并获得具有非常高随机访问速度的硬盘（可能是固态磁盘）。

于 2009-01-30T13:01:40.800 回答