是否有一种有效的方法来存储使用随机整数键的查找结构？

Question

我需要实现具有以下要求的查找结构：

• 键是随机的128位整数
• 值是64位
• 它将存储在磁盘上
• 它必须是可搜索的，而不是整个结构都驻留在内存中（我打算在内存中映射文件）
• 它必须是可变的，但是对磁盘的写入必须是增量的（必须不要求覆盖整个结构）

是否有一种有效的方法来实现所有这些？

请不要回答“不要使用UUID。”我在问一个具体的问题；更改需求会更改问题。

Answer 1

由于键和值均是固定字节数，因此可以将hashtable实现为文件。前几个字节包含当前的元素数和当前的容量，然后每个条目占用16 + 8字节（如果禁止将0用作键）或1 + 16 + 8字节（如果需要标志来指示是否）条目是否存在。

您可以对密钥进行哈希处理，然后使用算术算法查找文件中的正确位置，然后仅读取或写入所需的条目。要解决哈希冲突，linear probing可能最好避免搜索次数。由于密钥是随机的，因此不应该发生灾难性的碰撞堆积，并且哈希可以简单地采用密钥的最低

k位，其中当前容量为2 ^ k。

这占用O（

n

）空间，并允许以O（1）的平均时间进行查找，并以O（1）的摊销时间进行写入。有时，您必须调整哈希表的大小以增加写操作的容量。在这些情况下，这需要O（n）时间。如果在最坏的情况下需要O（1）进行写操作，则可以同时维护旧的和新的哈希表，在两者中进行查找，然后在每次写操作时，将两个条目从旧的复制到新的。如果容量始终增加2倍，则除分配大小为O（

n

）的空哈希表的开销外，这将提供未摊销的恒定时间写入。如果对于单个写入操作而言，创建特定大小的空白文件也太慢，那么您也可以在多次写入中分摊空白文件的创建。