AntInLoop

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