3

我有一个要存储到磁盘的哈希表。该列表如下所示：

<16-byte key                   > <1-byte result>
a7b4903def8764941bac7485d97e4f76 04
b859de04f2f2ff76496879bda875aecf 03
etc...

有 1-5 百万个条目。目前我只是将它们存储在一个文件中，每个条目 17 字节乘以条目数。那个文件有几十兆。我的目标是以一种首先优化磁盘空间然后优化查找时间的方式存储它们。插入时间并不重要。

做这个的最好方式是什么？我希望文件尽可能小。多个文件也可以。帕特里夏？基特里？

无论我得到什么好的建议，我都会实施和测试。我会把结果贴在这里给大家看看。

4

6 回答 6

4

您可以按键排序条目并进行二进制搜索。

固定大小的键和数据条目意味着您可以非常快速地从一行跳转到另一行，并且仅存储键和数据意味着您不会在元数据上浪费任何空间。

我认为您不会在磁盘空间上做得更好，并且查找时间为 O(log(n))。插入时间很长，但你说那没关系。

如果您真的愿意容忍较长的访问时间，请对表进行排序，然后将其分成一定大小的块并压缩它们。将每个块的 offset* 和开始/结束键存储在文件的开头部分中。使用此方案，您可以在线性时间内找到包含所需密钥的块，然后在解压缩块中执行二进制搜索。根据您愿意一次加载到内存中的文件量来选择块大小。

使用现成的压缩方案（如 GZIP），您可以根据需要调整压缩比；较大的文件可能会有更快的查找时间。

我怀疑节省的空间会很大，因为您的结构似乎主要是散列。如果它们实际上是散列，它们是随机的并且不会很好地压缩。排序将有助于提高压缩率，但不会增加很多。

*使用header查找要解压使用的block的偏移量。

于 2009-12-24T08:39:47.380 回答
3

500 万条记录，大约 81MB - 可以在内存中使用数组。

正如您所描述的问题 - 它比哈希值更独特的键。尝试使用哈希表来访问值（查看此链接）。

如果有我的误解并且这是真正的哈希 - 尝试在此之上构建第二个哈希级别。

哈希表也可以在磁盘上成功组织（例如作为单独的文件）。

添加

具有良好搜索性能和少量开销的解决方案是：

  1. 定义散列函数，从键中产生整数值。
  2. 根据此函数生成的值对文件中的记录进行排序
  3. 存储每个哈希值开始的文件偏移量
  4. 定位值：
    4.1。
    用函数4.2计算它的哈希值。
    在文件4.3中查找偏移量。从此位置开始从文件中读取记录，直到找到键或未到达下一个键的偏移量或文件结束。

还有一些额外的事情必须指出：

  • 哈希函数必须快速有效
  • 散列函数必须产生线性分布值或接近该值
  • 哈希值偏移表可以放在单独的文件中
  • 哈希值偏移表可以通过在应用程序开始时顺序读取整个排序文件并存储在内存中来动态生成
  • 在步骤 4.3。记录必须按块读取，而不是逐个读取，才能生效。理想情况下，一次将所有具有计算哈希值的值读取到内存中。

您可以在此处找到哈希函数的一些示例。

于 2009-12-24T09:04:55.397 回答
1

简单的方法会起作用并将它们存储在sqlite 数据库中吗？我不认为它会变得更小，但您应该获得非常好的查找​​性能，而且它很容易实现。

于 2009-12-24T08:40:36.053 回答
1

首先 - 如果你想优化磁盘空间，多个文件是不行的，因为集群大小 - 当你创建大小为 ~100 字节的文件时，每个集群大小的磁盘空间会减少 - 例如 2kB。

其次-在您的情况下，我会将所有表存储在单个二进制文件中，按键中的字节值简单地按 ASC 排序。它将为您提供长度完全等于entryNumber * 17的文件，如果您不想使用归档，则该文件的长度是最小的，其次，当您搜索关键分割文件时，您可以使用时间~log2（entriesNumber）非常快速分成两部分，并将其边界上的密钥与所需的密钥进行比较。如果“边界键”更大，则取文件的第一部分，如果更大，则取第二部分。并再次将部分分成两部分，等等。所以你需要关于 log2(entriesNumber) 读取操作来搜索单个键。

于 2009-12-24T08:46:41.510 回答
1

与文件设计一样，您对数据分布的了解（并告诉我们）越多越好。假设您的键值均匀分布在所有 16 字节键的集合中（如果您要存储哈希表，这应该是正确的），我建议结合其他人已经建议的内容：

  • 诸如此类的二进制数据属于二进制文件；不要让散列和值的简单表示为十六进制数字字符串这一事实欺骗您认为这是字符串数据；

  • 文件大小使得整个shebang可以保存在任何现代PC或服务器以及许多其他设备上的内存中；

  • 密钥的前 4 个字节将可能的密钥集划分为 16^4 (= 65536) 个子集；如果您的密钥均匀分布并且您有 5x10^6 个条目，那么每个子集大约有 76 个条目；所以创建一个文件，每个子集有 100 个条目；然后：

  • 在偏移量 0 处开始写入前导 4 个字节 0x0000 的所有条目；用 0 填充到总共 100 个条目（我认为是 1700 字节）；

  • 在偏移量 1700 处开始写入前导 4 字节 0x0001、pad、

  • 重复，直到你写完所有的数据。

现在，您的查找变成了计算文件偏移量的计算，然后扫描多达 100 个条目以找到您想要的条目。如果这还不够快，则使用 16^5 个子集，每个子​​集允许大约 6 个条目 (6x16^5 = 6291456)。我猜这会比二分搜索更快——但这只是一个猜测。

插入有点问题，您可以根据自己对数据的了解来决定新条目 (a) 是否需要对子集进行重新排序，或者 (b) 可以简单地添加到条目列表的末尾在该索引处（这意味着在每次查找时扫描整个子集）。

如果空间非常重要，您当然可以从条目中删除前 4 个字节，因为它们是通过计算文件中的偏移量来计算的。

我所描述的不是非常好，是一个哈希表。

于 2009-12-24T11:16:07.757 回答
1

您的密钥是 128 位，但如果您最多有 10^7 个条目，则只需 24 位即可对其进行索引。

  1. 你可以制作一个哈希表，或者

  2. 使用 Bentley 风格的展开二分搜索（最多 24 次比较），如

这是展开的循环（使用 32 位整数）。

int key[4];
int a[1<<24][4];

#define COMPARE(key, i) (key[0]>=a[i][0] && key[1]>=a[i][1] && key[2]>=a[i][2] && key[3]>=a[i][3])

i = 0;
if (COMPARE(key, (i+(1<<23))) >= 0) i += (1<<23);
if (COMPARE(key, (i+(1<<22))) >= 0) i += (1<<22);
if (COMPARE(key, (i+(1<<21))) >= 0) i += (1<<21);
...
if (COMPARE(key, (i+(1<<3))) >= 0) i += (1<<3);
if (COMPARE(key, (i+(1<<2))) >= 0) i += (1<<2);
if (COMPARE(key, (i+(1<<1))) >= 0) i += (1<<3);
于 2009-12-24T16:32:43.000 回答