hash_map.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include<bits/stdc++.h> | ||
| 4 | // #include<bits/extc++.h> | ||
| 5 | #include <ext/pb_ds/assoc_container.hpp> | ||
| 6 | |||
| 7 | struct splitmix64_hash { | ||
| 8 | ✗ | static uint64_t splitmix64(uint64_t x) { | |
| 9 | // http://xorshift.di.unimi.it/splitmix64.c | ||
| 10 | ✗ | x += 0x9e3779b97f4a7c15; | |
| 11 | ✗ | x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; | |
| 12 | ✗ | x = (x ^ (x >> 27)) * 0x94d049bb133111eb; | |
| 13 | ✗ | return x ^ (x >> 31); | |
| 14 | } | ||
| 15 | |||
| 16 | ✗ | size_t operator()(uint64_t x) const { | |
| 17 | ✗ | static const uint64_t FIXED_RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); | |
| 18 | ✗ | return splitmix64(x + FIXED_RANDOM); | |
| 19 | } | ||
| 20 | }; | ||
| 21 | |||
| 22 | template <typename K, typename V, typename Hash = splitmix64_hash> | ||
| 23 | using hash_map = __gnu_pbds::gp_hash_table<K, V, Hash>; | ||
| 24 | |||
| 25 | template <typename K, typename Hash = splitmix64_hash> | ||
| 26 | using hash_set = hash_map<K, __gnu_pbds::null_type, Hash>; | ||
| 27 |