我应该使用哪种数据结构来存储散列值？
我有一个要存储到磁盘上的哈希表。该列表如下所示：
<16-byte key > <1-byte result>
a7b4903def8764941bac7485d97e4f76 04
b859de04f2f2ff76496879bda875aecf 03
etc...有100-500万个条目。目前我只将它们存储在一个文件中，每个条目17字节乘以条目数量。那个文件有几十兆字节。我的目标是以一种首先优化磁盘空间，然后优化查找时间的方式来存储它们。插入时间并不重要。
做这件事最好的方法是什么？我希望文件越小越好。多个文件也是可以的。帕特丽夏·特里？基数trie？
无论我得到什么好的建议，我都会去实现和测试。我会在这里发布结果，让所有人都能看到。
回答 5
Stack Overflow用户
发布于 2009-12-24 09:04:55
500万条记录大约是81MB -在内存中使用数组是可以接受的。
正如你所描述的问题--它更多的是唯一键而不是散列值。尝试使用哈希表来访问值(请查看this link)。
如果有我的误解，这是真正的哈希-尝试建立第二个哈希级别以上。
哈希表也可以成功地组织在磁盘上(例如，作为单独的文件)。
加法
搜索性能好、开销小的解决方案是：
- 定义了哈希函数，该函数从键生成整数值。
- 根据此函数生成的值对文件中的记录进行排序存储文件偏移量，其中每个哈希值将启动
- 以查找值：
4.1。使用函数计算它的散列
4.2。查找文件中的偏移量
4.3。从文件中读取记录，从该位置开始，直到找到关键字、未达到下一个关键字的偏移量或文件结束为止。
还有一些额外的事情必须指出：
- 散列函数必须快速才能有效
- 散列函数必须产生线性分布值或接近
- 散列值偏移量可以放置在分离的文件中
- 散列值偏移量表可以在应用程序开始时顺序读取整个排序的文件时动态产生，并在步骤4.3存储在存储器中
<代码>H120。记录必须按块读取，而不是逐个读取，才能生效。理想情况下，一次将具有计算哈希的所有值读取到内存中。
你可以找到一些散列函数here的例子。
Stack Overflow用户
发布于 2009-12-24 08:40:36
这种简单的方法是否可行，并将它们存储在sqlite database中？我不认为它会变得更小，但你应该会得到非常好的查找性能，而且它很容易实现。
Stack Overflow用户
发布于 2009-12-24 08:46:42
首先-如果你想优化磁盘空间，多个文件是不可以的，因为集群大小-当你创建大小约为100字节的文件时，每个集群大小的磁盘空间会减少-例如2kB。
其次-在你的情况下，我会将所有的表存储在一个二进制文件中，简单地按键中的字节值进行ASC排序。它会给你的文件长度正好等于条目数*17，这是最小的，如果你不想使用存档，其次，你可以使用非常快速的搜索与时间~log2(entriesNumber)，当你搜索关键字将文件分成两部分，并比较他们的边界上的关键字与所需的关键字。如果“边界键”较大，你需要文件的第一部分，如果较大，那么第二部分。并再次将所采取的部分分为两部分，等等。因此，您将需要大约log2(entriesNumber)读取操作来搜索单个键。
https://stackoverflow.com/questions/1957390
复制
腾讯云开发者
