从文件读取/写入 std::unordered_map 的更快方法

我正在与一些非常大的公司合作std::unordered_maps（数亿个条目）并且需要将它们保存到文件中或从文件中加载它们。我目前执行此操作的方法是迭代映射并一次读取/写入每个键和值对：

std::unordered_map<unsigned long long int, char> map;

void save(){
    std::unordered_map<unsigned long long int, char>::iterator iter;
    FILE *f = fopen("map", "wb");
    for(iter=map.begin(); iter!=map.end(); iter++){
        fwrite(&(iter->first), 8, 1, f);
        fwrite(&(iter->second), 1, 1, f);
    }
    fclose(f);
}

void load(){
    FILE *f = fopen("map", "rb");
    unsigned long long int key;
    char val;
    while(fread(&key, 8, 1, f)){
        fread(&val, 1, 1, f);
        map[key] = val;
    }
    fclose(f);
}

但由于有大约 6.24 亿个条目，从文件中读取地图需要 9 分钟。写入文件速度更快，但仍需要几分钟。有没有更快的方法来做到这一点？

C++ unordered_map实现必须全部使用chaining https://en.wikipedia.org/wiki/Hash_table#Separate_chaining。您可能希望对通用哈希表执行此操作有多种非常好的理由，对此进行了讨论here https://stackoverflow.com/questions/31112852/how-stdunordered-map-is-implemented.

这对性能有着巨大的影响。最重要的是，这意味着哈希表的条目可能分散在整个内存中，这使得访问每个条目的效率降低一个数量级（左右），如果可以以某种方式串行访问它们，就会出现这种情况。

幸运的是，您可以构建哈希表，当哈希表接近满时，可以对相邻元素进行近乎顺序的访问。这是使用完成的开放寻址 https://en.wikipedia.org/wiki/Hash_table#Open_addressing.

由于您的哈希表不是通用的，您可以尝试这个。

下面，我构建了一个简单的哈希表容器，具有开放寻址和线性探测 https://en.wikipedia.org/wiki/Linear_probing。它假设了一些事情：

1. 您的密钥已经以某种方式随机分布。这消除了对哈希函数的需要（尽管良好的哈希函数构建起来相当简单，即使伟大的哈希函数很困难）。

2. 您只能将元素添加到哈希表中，而不能删除它们。如果不是这种情况，您需要更改used向量成可以保持三种状态的东西：USED, UNUSED, and TOMBSTONE where TOMBSTONE是删除元素的声明，用于继续线性搜索探测或停止线性插入探测。

3. 您提前知道哈希表的大小，因此无需调整其大小/重新哈希。

4. 您不需要以任何特定顺序遍历元素。

当然，网上可能有各种优秀的开放寻址哈希表实现，可以解决上述许多问题。然而，我的表格的简单性使我能够传达重要的一点。

重要的一点是：我的设计允许哈希表的所有信息存储在三个向量中。即：内存是连续的。

连续内存分配速度快，读取速度快，写入速度快。其影响是深远的。

使用与我相同的测试设置之前的回答 https://stackoverflow.com/a/48410769/752843，我得到以下时间：

Save. Save time = 82.9345 ms
Load. Load time = 115.111 ms

保存时间缩短了 95%（快 22 倍），加载时间缩短了 98%（快 62 倍）。

Code:

#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <functional>
#include <iostream>
#include <random>
#include <vector>

const int TEST_TABLE_SIZE = 10000000;



template<class K, class V>
class SimpleHash {
 public:
  int usedslots = 0;

  std::vector<K> keys;
  std::vector<V> vals;
  std::vector<uint8_t> used;

  //size0 should be a prime and about 30% larger than the maximum number needed
  SimpleHash(int size0){
    vals.resize(size0);
    keys.resize(size0);
    used.resize(size0/8+1,0);
  }

  //If the key values are already uniformly distributed, using a hash gains us
  //nothing
  uint64_t hash(const K key){
    return key;
  }

  bool isUsed(const uint64_t loc){
    const auto used_loc = loc/8;
    const auto used_bit = 1<<(loc%8);
    return used[used_loc]&used_bit;    
  }

  void setUsed(const uint64_t loc){
    const auto used_loc = loc/8;
    const auto used_bit = 1<<(loc%8);
    used[used_loc] |= used_bit;
  }

  void insert(const K key, const V val){
    uint64_t loc = hash(key)%keys.size();

    //Use linear probing. Can create infinite loops if table too full.
    while(isUsed(loc)){ loc = (loc+1)%keys.size(); }

    setUsed(loc);
    keys[loc] = key;
    vals[loc] = val;
  }

  V& get(const K key) {
    uint64_t loc = hash(key)%keys.size();

    while(true){
      if(!isUsed(loc))
        throw std::runtime_error("Item not present!");
      if(keys[loc]==key)
        return vals[loc];

      loc = (loc+1)%keys.size();
    }
  }

  uint64_t usedSize() const {
    return usedslots;
  }

  uint64_t size() const {
    return keys.size();
  }
};

typedef SimpleHash<uint64_t, char> table_t;

void SaveSimpleHash(const table_t &map){
  std::cout<<"Save. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "wb");
  uint64_t size = map.size();
  fwrite(&size, 8, 1, f);
  fwrite(map.keys.data(), 8, size, f);
  fwrite(map.vals.data(), 1, size, f);
  fwrite(map.used.data(), 1, size/8+1, f);
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Save time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;
}

table_t LoadSimpleHash(){
  std::cout<<"Load. ";
  const auto start = std::chrono::steady_clock::now();
  FILE *f = fopen("/z/map", "rb");

  uint64_t size;
  fread(&size, 8, 1, f);

  table_t map(size);
  fread(map.keys.data(), 8, size, f);
  fread(map.vals.data(), 1, size, f);
  fread(map.used.data(), 1, size/8+1, f);
  fclose(f);
  const auto end = std::chrono::steady_clock::now();
  std::cout<<"Load time = "<< std::chrono::duration<double, std::milli> (end-start).count() << " ms" << std::endl;

  return map;
}

int main(){
  //Perfectly horrendous way of seeding a PRNG, but we'll do it here for brevity
  auto generator = std::mt19937(12345); //Combination of my luggage
  //Generate values within the specified closed intervals
  auto key_rand  = std::bind(std::uniform_int_distribution<uint64_t>(0,std::numeric_limits<uint64_t>::max()), generator);
  auto val_rand  = std::bind(std::uniform_int_distribution<int>(std::numeric_limits<char>::lowest(),std::numeric_limits<char>::max()), generator);

  table_t map(1.3*TEST_TABLE_SIZE);
  std::cout<<"Created table of size "<<map.size()<<std::endl;

  std::cout<<"Generating test data..."<<std::endl;
  for(int i=0;i<TEST_TABLE_SIZE;i++)
    map.insert(key_rand(),(char)val_rand()); //Low chance of collisions, so we get quite close to the desired size

  map.insert(23,42);
  assert(map.get(23)==42);

  SaveSimpleHash(map);
  auto newmap = LoadSimpleHash();

  //Ensure that the load worked
  for(int i=0;i<map.keys.size();i++)
    assert(map.keys.at(i)==newmap.keys.at(i));
  for(int i=0;i<map.vals.size();i++)
    assert(map.vals.at(i)==newmap.vals.at(i));  
  for(int i=0;i<map.used.size();i++)
    assert(map.used.at(i)==newmap.used.at(i));    
}