unordered_map
  • 板块学术版
  • 楼主dbxxx
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/1/16 20:18
  • 上次更新2023/10/24 03:56:33
查看原帖
unordered_map
120868
dbxxx楼主2023/1/16 20:18

想问一下采用了自定义哈希函数(如下,来自 https://codeforces.com/blog/entry/62393)的 unordered_map,常数大概多少?

struct my_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }

  // 针对 std::pair<int, int> 作为主键类型的哈希函数
  size_t operator()(pair<uint64_t, uint64_t> x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x.first + FIXED_RANDOM) ^
           (splitmix64(x.second + FIXED_RANDOM) >> 1);
  }
};

这是我朋友在 CF710F 的两份提交:

两份代码,上面是 unordered_map,下面是 map,并且采用了自定义的防卡哈希函数,为什么 unordered_map 会 TLE map 不会?

虽然我知道 unordered_map 的常数大但是他比 map 还大吗?

2023/1/16 20:18
加载中...