Hash Functions & Collision Resistance
Hash Functions map arbitrary-sized inputs to fixed-size digests for O(1) hash tables, bloom filters, rolling string hashes, and cryptographic integrity checks (SHA-256).
Difficulty: Medium · Interactive Visualizer · C++ / Python / Java / JS Code
Hash Functions & Collision Resistance
A Hash Function deterministically maps arbitrarily sized data (strings, integers, structs) to a fixed-width digest. Good hash functions fall into two distinct families:
1. Non-Cryptographic Hashes (FNV-1a, MurmurHash, xxHash, splitmix64, Rolling Hash): ultra-fast, uniform distribution, great for Hash Tables and Bloom Filters.
2. Cryptographic Hashes (SHA-256, BLAKE3): preimage-resistant and collision-resistant—used for digital signatures, Git commits, and password storage (with salting/Argon2).
Key Pitfall: Anti-Hash Tests in C++ std::unordered_map
GCC's default std::hash<int> is the identity function, so adversarial inputs (multiples of the internal prime bucket count) degrade std::unordered_map to $O(n^2)$! Passing a custom splitmix64 hash seeded with steady_clock eliminates anti-hash hacks completely!
---
Practice Problems
Intermediate
1. Anti-Hack splitmix64 Custom Hash & FNV-1a String Hash
Implement a fast collision-resistant splitmix64 integer hash (safe for unordered_map) and 64-bit FNV-1a string hash.
Approach: Apply splitmix64 bit-mixing shifts/multiplications with a runtime clock salt; compute 64-bit FNV-1a for strings.
<details>
<summary>Show C++ Solution</summary>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
struct SafeIntHash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15ULL;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t SALT = std::chrono::steady_clock::now().time_since_epoch().count();
return static_cast<size_t>(splitmix64(x + SALT));
}
};
uint64_t fnv1a64(const std::string& s) {
uint64_t h = 14695981039346656037ULL;
for (unsigned char c : s) { h ^= c; h *= 1099511628211ULL; }
return h;
}
int main() {
std::unordered_map<int, int, SafeIntHash> mp;
mp[42] = 100;
std::cout << mp[42] << " | fnv1a(\"hello\")=" << fnv1a64("hello") << "\n";
return 0;
}
</details>
---
Related Structures & Algorithms
- Hash Table, Bloom Filter, and Rolling Hash.