想问一下采用了自定义哈希函数(如下,来自 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 还大吗?