DataStructure/STL/pbds_faster_map.h

View this file on GitHub
Last update: 2023-10-22 16:42:38+08:00
Link: https://codeforces.com/blog/entry/60737
Link: https://codeforces.com/contest/1006/submission/41804666
Link: https://ideone.com/LhpILA

Code

// From https://codeforces.com/blog/entry/60737

// Note: it's probably useful to test if these tricks make unordered_map fast enough first:
// unordered_map<...> mp;
// mp.reserve(N);   // maybe use 2^x?
// mp.max_load_factor(0.25);

// Code copied from https://codeforces.com/contest/1006/submission/41804666
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

unsigned hash_f(unsigned x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}
struct chash {
    int operator()(int x) const { return hash_f(x); }
};

gp_hash_table<int, int, chash> mp;


// alternative hash function:
// Code copied from https://ideone.com/LhpILA
const ll TIME = chrono::high_resolution_clock::now().time_since_epoch().count();
const ll SEED = (ll)(new ll);
const ll RANDOM = TIME ^ SEED;
const ll MOD = (int)1e9+7;
const ll MUL = (int)1e6+3;

struct chash{
    ll operator()(ll x) const { return std::hash<ll>{}((x ^ RANDOM) % MOD * MUL); }
};

#line 1 "DataStructure/STL/pbds_faster_map.h"
// From https://codeforces.com/blog/entry/60737

// Note: it's probably useful to test if these tricks make unordered_map fast enough first:
// unordered_map<...> mp;
// mp.reserve(N);   // maybe use 2^x?
// mp.max_load_factor(0.25);

// Code copied from https://codeforces.com/contest/1006/submission/41804666
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

unsigned hash_f(unsigned x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}
struct chash {
    int operator()(int x) const { return hash_f(x); }
};

gp_hash_table<int, int, chash> mp;


// alternative hash function:
// Code copied from https://ideone.com/LhpILA
const ll TIME = chrono::high_resolution_clock::now().time_since_epoch().count();
const ll SEED = (ll)(new ll);
const ll RANDOM = TIME ^ SEED;
const ll MOD = (int)1e9+7;
const ll MUL = (int)1e6+3;

struct chash{
    ll operator()(ll x) const { return std::hash<ll>{}((x ^ RANDOM) % MOD * MUL); }
};