Most hash libraries treat hash functions as black boxes. Algebraic Hashing exposes their mathematical structure, letting you compose hash functions like algebraic expressions—with zero runtime overhead.
The Core Insight
Hash functions form an abelian group under XOR:
- Closure:
h₁ ⊕ h₂is still a valid hash function - Associativity:
(h₁ ⊕ h₂) ⊕ h₃ = h₁ ⊕ (h₂ ⊕ h₃) - Identity: XOR with zero
- Inverses: Each hash is its own inverse under XOR
This algebraic structure is the foundation for compositional hashing.
Why This Matters
1. Compile-Time Composition
Using C++20 concepts and template metaprogramming:
auto composed = fnv1a<> ^ sha256<>;
auto hash = composed("data"); // Zero runtime overhead
All composition resolves at compile time—no virtual dispatch, no function pointers.
2. Provable Properties
We prove that XOR composition preserves:
- Uniform distribution (under independence)
- Avalanche effect (bit changes cascade)
- Collision resistance (for cryptographic hashes)
3. Universal Interface
Works with any hash function—non-cryptographic (FNV-1a), perfect (FKS), or cryptographic (SHA-256). The algebra doesn’t care about the implementation.
Practical Use Cases
- Domain separation:
hash_user ^ hash_timestampprevents collision attacks across domains - Perfect hashing: FKS two-level scheme with pluggable base hash functions
- Composite keys: Hash multiple fields independently, then XOR
- Type-based hashing: Different hash functions for different types, composed generically
Connection to Oblivious Computing
This work shares DNA with my oblivious computing research: make mathematical structure explicit in the type system. Just as Bernoulli types enforce privacy invariants algebraically, algebraic hashing enforces compositional invariants through group theory.
Technical: Modern C++20 header-only library • Zero-cost abstractions via concepts • Production-ready implementations
Discussion