hash_functions_demo.cpp

/**
 * Division method and multiplication method (Knuth) demos.
 */
#include <cmath>
#include <cstdint>
#include <iostream>

static std::uint64_t divisionHash(std::uint64_t k, std::uint64_t m) { return k % m; }

// Multiplication method: floor( m * (kA mod 1) ), A = (sqrt(5)-1)/2
static std::uint64_t multiplicationHash(std::uint64_t k, std::uint64_t m) {
    constexpr long double A = 0.618033988749894848204586834365638117720309179805762862135448L;
    long double frac = std::fmod(static_cast<long double>(k) * A, 1.0L);
    return static_cast<std::uint64_t>(std::floor(static_cast<long double>(m) * frac));
}

int main() {
    const std::uint64_t m = 97;
    std::cout << "Division h(k)=k%97:\n";
    for (std::uint64_t k : {1000, 2000, 3000, 12345, 99999}) {
        std::cout << "  k=" << k << " -> " << divisionHash(k, m) << "\n";
    }
    std::cout << "Multiplication method (m=97, A=golden ratio conjugate):\n";
    for (std::uint64_t k : {1000, 2000, 3000, 12345, 99999}) {
        std::cout << "  k=" << k << " -> " << multiplicationHash(k, m) << "\n";
    }
    return 0;
}