哈希表效率测试

结论似乎是 __gnu_pbds::gp_hash_table 更快。在没有 __gnu_pbds 的情况下手打似乎效率高超。

实验数据 1（各 600000 次操作，单位 ms，禁用优化）：

容器	insert	find	find（失败）	at	at（越界）	operator[]	operator[]（新建）
std::map<int, int>	289	150	213	157	1253	157	362
std::unordered_map<int, int>	136	30	28	31	1041	32	171
std::unordered_map<int, int, custom_hash>	121	29	24	32	1076	30	156
std::multimap<int, int>	265	149	214	N/A	N/A	N/A	N/A
std::unordered_multimap<int, int>	152	33	28	N/A	N/A	N/A	N/A
std::unordered_multimap<int, int, custom_hash>	167	43	11	N/A	N/A	N/A	N/A
__gnu_pbds::gp_hash_table<int, int>	69	12	10	N/A	N/A	14	64
__gnu_pbds::cc_hash_table<int, int>	89	15	7	N/A	N/A	13	86
self_implement_hash_table<int, int>	95	25	36	21	1006	23	104

经实验，__gnu_pbds::gp_hash_table<int, int> 的 find（失败）测试在大约 $660000$ 后速度会大量降低，本人尚未发现原因。

实验数据 2（各 1000000 次操作，单位 ms，开启 O2 优化）：

容器	insert	find	find（失败）	at	at（越界）	operator[]	operator[]（新建）
std::map<int, int>	89	49	29	51	1572	48	86
std::unordered_map<int, int>	60	9	11	9	1607	7	68
std::unordered_map<int, int, custom_hash>	69	10	14	10	1656	10	77
std::multimap<int, int>	82	48	26
std::unordered_multimap<int, int>	62	9	10
std::unordered_multimap<int, int, custom_hash>	76	14	6
__gnu_pbds::gp_hash_table<int, int>	23	<1	<1			1	>20000
__gnu_pbds::cc_hash_table<int, int>	60	5	2			4	76
self_implement_hash_table<int, int>	36	7	10	34	5319	9	41

operator[]（新建）是最后一个被运行的测试。即，容器在执行中间 5 种访问时大小都是 $600000$，而非 $120000$。

测试机配置：AMD Ryzen 5 3600 6-Core Processor 3.60GHz, 8.00 GB RAM

环境配置：Windows 10 企业版 LTSC 1809 (x64)

编译器配置：g++ (tdm64-1) 4.9.2（mingw-w64）

编译选项：-Wall -lm -O0/-O2 -DMIRAI_LOCAL -std=c++14 -fno-ms-extensions

测试代码：

#include <cstdio>
#include <unordered_map>
#include <map>
#include <chrono>
#include <cstdlib>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <algorithm>
#include <stdexcept>

namespace mirai {

template <typename type>
class custom_hash {
};
template <>
class custom_hash<int> {
 public:
  std::size_t operator()(const int& x) const {
    return x ^ 0x14273913;
  }
};

std::unordered_map<int, int> umap;
std::unordered_map<int, int, custom_hash<int>> umap2;
std::unordered_multimap<int, int> ummap;
std::unordered_multimap<int, int, custom_hash<int>> ummap2;
std::map<int, int> map;
std::multimap<int, int> mmap;
__gnu_pbds::gp_hash_table<int, int> ghash;
__gnu_pbds::cc_hash_table<int, int> chash;

constexpr int MAXT = 123179;
std::vector<std::pair<int, int>> buckets[MAXT];

int main(int argc, char** argv) {
  std::printf("std::map<int, int>: \n");
  int ninsert = 600000, nat = 600000, nat2 = 600000, nopat = 600000, nopat2 = 600000, nfind = 600000, nfind2 = 600000;
  auto begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    map.insert({i, i});
  }
  auto end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    map.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    map.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nat; ++i) {
    map.at(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("at: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nat2; ++i) {
    try {
      map.at(i + 100000000);
    } catch (...) {}
  }
  end = std::chrono::steady_clock::now();
  std::printf("at2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat; ++i) {
    map[i];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat2; ++i) {
    map[i + 100000000];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat2: %lldms\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("std::multimap<int, int>: \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    mmap.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    mmap.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    mmap.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("std::unordered_map<int, int>:  \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    umap.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    umap.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    umap.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nat; ++i) {
    umap.at(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("at: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nat2; ++i) {
    try {
      umap.at(i + 100000000);
    } catch (...) {}
  }
  end = std::chrono::steady_clock::now();
  std::printf("at2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat; ++i) {
    umap[i];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat2; ++i) {
    umap[i + 100000000];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat2: %lldms\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("std::unordered_multimap<int, int>:  \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    ummap.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    ummap.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    ummap.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("std::unordered_multimap<int, int, custom_hash>:  \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    ummap.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    ummap.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    ummap.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("std::unordered_map<int, int, custom_hash>: \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    umap2.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    umap2.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    umap2.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nat; ++i) {
    umap2.at(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("at: %lldms \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nat2; ++i) {
    try {
      umap2.at(i + 100000000);
    } catch (...) {}
  }
  end = std::chrono::steady_clock::now();
  std::printf("at2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat; ++i) {
    umap2[i];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat2; ++i) {
    umap2[i + 100000000];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat2: %lldms\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("__gnu_pbds::gp_hash_table<int, int>: \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    ghash.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    ghash.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    ghash.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat; ++i) {
    ghash[i]; 
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat2; ++i) {
    ghash[i + 100000000];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat2: %lldms\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  std::printf("__gnu_pbds::cc_hash_table<int, int>: \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    chash.insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    chash.find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    chash.find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat; ++i) {
    chash[i];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat2; ++i) {
    chash[i + 100000000];
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat2: %lldms\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  
  
  auto insert = [](std::pair<int, int> kv) -> void {
    int idx = (kv.first ^ 0x14270817) % MAXT;
    for (auto &u : buckets[idx]) {
      if (u.first == kv.first) {
        u.second = kv.second;
        return;
      }
    }
    buckets[idx].push_back({kv.first, kv.second});
  };
  auto find = [](int key) -> std::vector<std::pair<int, int>>::iterator {
    int idx = (key ^ 0x14270817) % MAXT;
    for (auto i = buckets[idx].begin(); i != buckets[idx].end(); ++i) {
      if (i->first == key) {
        return i;
      }
    }
    return buckets[idx].end();
  };
  auto at = [](int key) -> std::pair<int, int> {
    int idx = (key ^ 0x14270817) % MAXT;
    for (auto &u : buckets[idx]) {
      if (u.first == key) {
        return u;
      }
    }
    throw std::out_of_range("");
  };
  auto opat = [](int key) -> std::pair<int, int> {
    int idx = (key ^ 0x14270817) % MAXT;
    for (auto &u : buckets[idx]) {
      if (u.first == key) {
        return u;
      }
    }
    buckets[idx].push_back({key, 0});
    return buckets[idx].back();
  };
  std::printf("self_implement_hash_table<int, int>: \n");
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= ninsert; ++i) {
    insert({i, i});
  }
  end = std::chrono::steady_clock::now();
  std::printf("insert: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    find(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    find(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("find2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind; ++i) {
    at(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("at: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nfind2; ++i) {
    try {
      at(i + 100000000);
    } catch (...) {}
  }
  end = std::chrono::steady_clock::now();
  std::printf("at2: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat; ++i) {
    opat(i);
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat: %lldms  \n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
  begin = std::chrono::steady_clock::now();
  for (int i = 1; i <= nopat2; ++i) {
    opat(i + 100000000);
  }
  end = std::chrono::steady_clock::now();
  std::printf("opat2: %lldms\n\n", std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count());
return 0;
}

}

int main(int argc, char** argv) {
  return mirai::main(argc, argv);
}