hashmap.hpp¶
为 std::unordered_map 配置带随机偏移的 splitmix64 整数哈希；用于降低预先构造哈希冲突的风险，保留标准容器接口。
Complexity: Time: Expected \(O(1)\) per map operation. Space: \(O(n)\).
Source: Sebastiano Vigna (SplitMix64 mixing function)
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
// NOYA_HASHMAP_HPP
#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
/// @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
// NOYA_HASHMAP_HPP