如何在辅助内存中实现不同的封闭散列变体？

Question

我真的不知道该怎么做，但是，除了它是在主内存中实现的，也就是堆，我如何才能将变体1,2或3或任何变体实现到辅助内存中，这就是我们正确操作文件的地方？

Answer 1

假设您的辅助内存具有相对较慢的寻道时间，如硬盘驱动器，通常您希望实现一个基于“存储桶”的封闭散列方案，其中存储桶可以相对较快地全部分页到主存中。通过这种方式，您通常不必为冲突或未存储的密钥执行昂贵的磁盘寻道。这并不是一件特别微不足道的事情，通常人们最终会使用经典的gdbm或others (也请参阅wikipedia)之类的库。

大多数存储桶方案都是基于extensible hashing的，有一种特殊的情况，用于尝试存储不适合存储桶的大键或数据。CiteSeer也是一个查找与可扩展散列相关的论文的好地方。(例如，请参阅链接论文的参考资料。)