我正在尝试制作一个简单的基于文件的哈希表。这是我的insert成员函数：
private: std::fstream f; // std::ios::in | std::ios::out | std::ios::binary
public: void insert(const char* this_key, long this_value) {
char* that_key;
long that_value;
long this_hash = std::hash<std::string>{}(this_key) % M;
long that_hash; // also block status
long block = this_hash;
long offset = block * BLOCK_SIZE;
while (true) {
this->f.seekg(offset);
this->f.read((char*) &that_hash, sizeof(long));
if (that_hash > -1) { // -1 (by default) indicates a never allocated block
this->f.read(that_key, BLOCK_SIZE);
if (strcmp(this_key, that_key) == 0) {
this->f.seekp(this->f.tellg());
this->f.write((char*) &this_value, sizeof(long));
break;
} else {
block = (block + 1) % M; // linear probing
offset = block * BLOCK_SIZE;
continue;
}
} else {
this->f.seekp(offset);
this->f.write((char*) &this_hash, sizeof(long)); // as block status
this->f.write(this_key, KEY_SIZE);
this->f.write((char*) &this_value, sizeof(long));
break;
}
}
}
测试了多达10M的键，对具有50,000,017个块的值对。 （二进制文件大小约为3.8GB）。
但是，具有5000万个键和250,000,013个块的测试速度非常慢...（在这种情况下，二进制文件大小超过19GB）。 1,000inserts通常需要4到5毫秒，但异常情况下会超过2,000毫秒。它变得越来越慢，然后需要40〜150ms ...（x10〜x30慢...）我绝对不知道...
seekg＆seekp和其他I / O操作是否受文件大小影响？ （虽然我找不到关于此问题的任何参考...）数据大小
通常磁盘驱动器块大小是2的幂，因此，如果您的数据块大小也是2的幂，则可以基本上消除数据块越过磁盘块边界的情况。
在您的情况下，64字节的值（如果您不需要存储散列，则为32字节）可能会稍微好一些。
插入顺序
您可以做的另一件事是提高性能，插入操作是增加哈希顺序，以减少必须从磁盘加载数据的时间。
[通常，在将数据读取或写入磁盘时，操作系统会一次读取/写入一个大卡盘（可能是4k），因此，如果您编写的算法是一种及时在本地写入数据的方法，则会减少数量时间必须实际将数据读取或写入磁盘。
鉴于您进行了大量插入，一种可能是一次处理插入，例如说1000个或什至10000个键/值对。本质上，您将在内存中存储数据并对其进行排序，一旦有足够的项目（或完成插入后），便会按顺序写入数据。
这样，您应该能够减少非常慢的磁盘访问。如果您使用传统的硬盘驱动器，因为移动磁头的速度很慢（在这种情况下，对其进行碎片整理可能会很有用），那么这可能更为重要。另外，请确保您的硬盘驱动器具有足够的可用空间。
在某些情况下，（在您的应用程序中）本地缓存也可能会有所帮助，特别是如果您知道如何使用数据。
文件大小与碰撞数
使用散列时，您希望找到文件大小和冲突之间的最佳结合点。如果您有太多的碰撞，那么您将浪费大量的时间，并且在某个时候几乎很难为每个插入位置找到空闲位置时，它可能会退化。
另一方面，如果文件非常大，则可能会遇到这样的情况，即您可能会在RAM中填充主要为空的数据，并且几乎所有插入操作仍需要用磁盘中的数据替换数据。
例如，如果您的数据为20GB，并且能够在内存中加载2GB，那么如果插入是随机的，则90％的时间您可能需要对硬盘的真正访问权限。
配置
很好的选项将取决于操作系统，它不在编程论坛的讨论范围之内。如果您要优化计算机，则应将其放在其他位置。
阅读
为了更好地理解操作系统（文件系统，缓存层…）和算法（外部排序算法，B-Tree和其他结构，这可能会有所帮助。
替代项