基于磁盘的快速哈希表? [英] Fast disk-based hashtables?

问题描述

我有一组哈希(MD5的前64位，因此它们是非常随机分布的)，并且我希望能够查看是否有新的哈希，并将其添加到哈希中.

I have sets of hashes (first 64 bits of MD5, so they're distributed very randomly) and I want to be able to see if a new hash is in a set, and to add it to a set.

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

Sets aren't too big, the largest will be millions of elements, but there are hundreds of sets, so I cannot hold them all in memory.

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

Some ideas I had so far:

• 我尝试将所有内容都保存在sqlite表中，但是一旦它不能容纳所有内存，它就会变得非常慢.
• 蜂鸣器听起来好像有很高的错误率.我不介意微小的错误率(64位哈希已经在4G元素集上产生1次冲突)，但是像1％这样的错误率实在是太高了.
• 保留文件中带有空格的哈希排序列表，如果没有足够的空格，请调整大小.哈希是均匀分布的，因此，即使是非常简单的方案也可以使用.

我想念一些确实很明显的东西吗?有什么提示如何实现基于磁盘的良好哈希表吗?

Am I missing something really obvious? Any hints how to implement good disk-based hashtable?

推荐答案

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

Here's the solution I eventually used:

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

它只是比sqlite快得令人难以置信，尽管它是低级的Perl代码，而且Perl实际上并不适用于高性能数据库.它不能与MD5分布不均的任何事物一起使用，它假设一切都将极其统一以保持实现的简单性.

It's just unbelievably faster than sqlite, even though it's low-level Perl code, and Perl really isn't meant for high performance databases. It will not work with anything that's less uniformly distributed than MD5, its assuming everything will be extremely uniform to keep the implementation simple.

我最初是使用seek()/sysread()/syswrite()尝试过的，但是它非常慢，mmap()版本确实快得多.

I tried it with seek()/sysread()/syswrite() at first, and it was very slow, mmap() version is really a lot faster.

这篇关于基于磁盘的快速哈希表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！