有没有一种有效的方法来存储使用随机整数键的查找结构？
Is there an efficient way to store a lookup structure that uses random integer keys?
我需要实现一个具有以下要求的查找结构：
- 密钥是随机的 128 位整数
- 值为 64 位
- 它将存储在磁盘上
- 它必须是可搜索的，而不需要整个结构驻留在内存中（我打算内存映射文件）
- 它必须是可变的，但写入磁盘必须是增量的（不得要求覆盖整个结构）
有没有一种有效的方法来实现所有这些？
请不要回答，"Don't use UUIDs."我问的是具体问题；更改要求会改变问题。
由于每个键和值都是固定数量的字节，因此您可以将 hashtable 实现为一个文件。前几个字节包含当前元素数和当前容量，然后每个条目占用 16 + 8 个字节（如果禁止将 0 作为键）或 1 + 16 + 8 个字节，如果你需要一个标志来指示是否条目是否存在。
您可以对密钥进行哈希处理，然后使用算法查找文件中的正确位置，然后只读取或写入您需要的条目。要解决散列冲突，linear probing 可能最好避免查找次数。由于密钥是随机的，因此不应发生灾难性的碰撞堆积，哈希可以简单地取密钥的最低 k 位，其中当前容量为 2^k.
这需要 O(n) space，并允许在 O(1) 的平均时间内查找，并在 O(1) 的摊销时间内写入。有时，您必须调整哈希表的大小以增加写入容量；在那些情况下这需要 O(n) 时间。
如果在最坏的情况下需要 O(1) 写入，您可以同时维护旧哈希表和新哈希表，在两者中进行查找，然后在每次写入操作时，将两个条目从旧哈希表复制到新哈希表新的。如果容量总是增加 2 倍，那么这将提供非摊销的恒定时间写入，除了分配大小为 O(n) 的空哈希表的成本。如果创建特定大小的空文件对于单个写入操作来说也太慢，那么您也可以在多次写入中分摊创建空文件。
我需要实现一个具有以下要求的查找结构：
- 密钥是随机的 128 位整数
- 值为 64 位
- 它将存储在磁盘上
- 它必须是可搜索的，而不需要整个结构驻留在内存中（我打算内存映射文件）
- 它必须是可变的，但写入磁盘必须是增量的（不得要求覆盖整个结构）
有没有一种有效的方法来实现所有这些？
请不要回答，"Don't use UUIDs."我问的是具体问题；更改要求会改变问题。
由于每个键和值都是固定数量的字节，因此您可以将 hashtable 实现为一个文件。前几个字节包含当前元素数和当前容量，然后每个条目占用 16 + 8 个字节（如果禁止将 0 作为键）或 1 + 16 + 8 个字节，如果你需要一个标志来指示是否条目是否存在。
您可以对密钥进行哈希处理，然后使用算法查找文件中的正确位置，然后只读取或写入您需要的条目。要解决散列冲突，linear probing 可能最好避免查找次数。由于密钥是随机的，因此不应发生灾难性的碰撞堆积，哈希可以简单地取密钥的最低 k 位，其中当前容量为 2^k.
这需要 O(n) space，并允许在 O(1) 的平均时间内查找，并在 O(1) 的摊销时间内写入。有时，您必须调整哈希表的大小以增加写入容量；在那些情况下这需要 O(n) 时间。
如果在最坏的情况下需要 O(1) 写入，您可以同时维护旧哈希表和新哈希表，在两者中进行查找，然后在每次写入操作时，将两个条目从旧哈希表复制到新哈希表新的。如果容量总是增加 2 倍，那么这将提供非摊销的恒定时间写入，除了分配大小为 O(n) 的空哈希表的成本。如果创建特定大小的空文件对于单个写入操作来说也太慢，那么您也可以在多次写入中分摊创建空文件。