hashmap.hpp¶
提供竞赛用开放寻址哈希表；适合键值映射量大、希望避免标准哈希表常数或被构造冲突的场景。
Complexity: Time: Expected O(1) per map operation. Space: O(n).
AC 记录：associative_array, static_range_frequency。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: Expected O(1) per map operation.
/// Space: O(n).
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <unordered_map>
namespace noya {
/// @brief Randomized splitmix64 hash to prevent hash collision attacks.
/// Two xor-shift/multiply avalanche rounds spread nearby integer keys across
/// all bits, while a process-local time-derived offset makes adversarial keys
/// from one run useless in the next.
struct splitmix64_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 RND =
std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + RND);
}
};
/// @brief Unordered map with anti-hash randomized hash function.
template <typename K, typename V, typename Hash = splitmix64_hash>
using HashMap = std::unordered_map<K, V, Hash>;
} // namespace noya
#ifndef NOYA_HASHMAP_HPP
#define NOYA_HASHMAP_HPP 1
/// @complexity Time: Expected O(1) per map operation.
/// Space: O(n).
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <unordered_map>
namespace noya {
/// @brief Randomized splitmix64 hash to prevent hash collision attacks.
/// Two xor-shift/multiply avalanche rounds spread nearby integer keys across
/// all bits, while a process-local time-derived offset makes adversarial keys
/// from one run useless in the next.
struct splitmix64_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 RND =
std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + RND);
}
};
/// @brief Unordered map with anti-hash randomized hash function.
template <typename K, typename V, typename Hash = splitmix64_hash>
using HashMap = std::unordered_map<K, V, Hash>;
} // namespace noya
#endif // NOYA_HASHMAP_HPP
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <unordered_map>
/// @complexity Time: Expected O(1) per map operation.
/// Space: O(n).
namespace noya {
/// @brief Randomized splitmix64 hash to prevent hash collision attacks.
/// Two xor-shift/multiply avalanche rounds spread nearby integer keys across
/// all bits, while a process-local time-derived offset makes adversarial keys
/// from one run useless in the next.
struct splitmix64_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 RND =
std::chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + RND);
}
};
/// @brief Unordered map with anti-hash randomized hash function.
template <typename K, typename V, typename Hash = splitmix64_hash>
using HashMap = std::unordered_map<K, V, Hash>;
} // namespace noya