// Cuenta casillas revisadas por búsqueda, sin medir tiempo: linear probing, double hashing (sin
// agrupamiento primario) y encadenamiento, contra las fórmulas clásicas.
// Las claves son números al azar de 64 bits, con semilla fija, así que k mod m reparte bien.
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <random>
#include <vector>

namespace {

constexpr std::size_t kSlots = 1u << 20;
constexpr std::size_t kMask = kSlots - 1;
constexpr std::uint64_t kEmpty = 0;

struct Counts {
    double hit;
    double miss;
};

// Un número al azar distinto de kEmpty. No se fuerza ningún bit: eso dejaría casillas sin uso.
std::uint64_t draw(std::mt19937_64& rng) {
    std::uint64_t key = rng();
    while (key == kEmpty) {
        key = rng();
    }
    return key;
}

// El paso es impar, para que el probing visite todas las casillas de una tabla de 2^k.
std::uint64_t step_for(std::uint64_t key, bool linear) {
    return linear ? 1 : ((key >> 32) | 1);
}

Counts open_addressing(const std::vector<std::uint64_t>& keys, std::size_t n,
                       const std::vector<std::uint64_t>& absent, bool linear) {
    std::vector<std::uint64_t> table(kSlots, kEmpty);
    for (std::size_t k = 0; k < n; k++) {
        const std::uint64_t step = step_for(keys[k], linear);
        std::uint64_t i = keys[k] & kMask;
        while (table[i] != kEmpty) {
            i = (i + step) & kMask;
        }
        table[i] = keys[k];
    }
    std::uint64_t probes = 0;
    for (std::size_t k = 0; k < n; k++) {
        const std::uint64_t step = step_for(keys[k], linear);
        std::uint64_t i = keys[k] & kMask;
        probes++;
        while (table[i] != keys[k]) {
            i = (i + step) & kMask;
            probes++;
        }
    }
    const double hit = static_cast<double>(probes) / static_cast<double>(n);
    probes = 0;
    for (std::uint64_t key : absent) {
        const std::uint64_t step = step_for(key, linear);
        std::uint64_t i = key & kMask;
        probes++;
        while (table[i] != kEmpty) {
            i = (i + step) & kMask;
            probes++;
        }
    }
    return {hit, static_cast<double>(probes) / static_cast<double>(absent.size())};
}

// Con encadenamiento se cuentan nodos visitados: buscar sin éxito recorre toda la lista.
Counts chaining(const std::vector<std::uint64_t>& keys, std::size_t n,
                const std::vector<std::uint64_t>& absent) {
    std::vector<std::uint32_t> length(kSlots, 0);
    std::uint64_t nodes = 0;
    for (std::size_t k = 0; k < n; k++) {
        length[keys[k] & kMask]++;
        // Al insertar al final, la clave k-ésima se encontrará recorriendo esta cantidad de nodos.
        nodes += length[keys[k] & kMask];
    }
    const double hit = static_cast<double>(nodes) / static_cast<double>(n);
    nodes = 0;
    for (std::uint64_t key : absent) {
        nodes += length[key & kMask];
    }
    return {hit, static_cast<double>(nodes) / static_cast<double>(absent.size())};
}

}  // namespace

int main() {
    std::mt19937_64 rng(2026);
    std::vector<std::uint64_t> keys(kSlots);
    for (std::uint64_t& key : keys) {
        key = draw(rng);
    }
    std::vector<std::uint64_t> absent(200000);
    for (std::uint64_t& key : absent) {
        key = draw(rng);
    }
    std::printf("Con éxito: casillas o nodos revisados por búsqueda, promedio\n");
    std::printf("%5s %8s %8s %8s %8s\n", "alfa", "linear", "fórmula", "double", "cadenas");
    const double alphas[] = {0.25, 0.5, 0.7, 0.8, 0.9, 0.95, 0.99};
    std::vector<Counts> line;
    std::vector<Counts> twice;
    std::vector<Counts> chain;
    for (double alpha : alphas) {
        const std::size_t n = static_cast<std::size_t>(alpha * static_cast<double>(kSlots));
        line.push_back(open_addressing(keys, n, absent, true));
        twice.push_back(open_addressing(keys, n, absent, false));
        chain.push_back(chaining(keys, n, absent));
    }
    for (std::size_t a = 0; a < line.size(); a++) {
        const double alpha = alphas[a];
        const double formula = 0.5 * (1.0 + 1.0 / (1.0 - alpha));
        std::printf("%5.2f %8.2f %8.2f %8.2f %8.2f\n", alpha, line[a].hit, formula, twice[a].hit, chain[a].hit);
    }
    std::printf("\nSin éxito: casillas o nodos revisados por búsqueda, promedio\n");
    std::printf("%5s %8s %8s %8s %8s\n", "alfa", "linear", "fórmula", "double", "cadenas");
    for (std::size_t a = 0; a < line.size(); a++) {
        const double alpha = alphas[a];
        const double formula = 0.5 * (1.0 + 1.0 / ((1.0 - alpha) * (1.0 - alpha)));
        std::printf("%5.2f %8.2f %8.2f %8.2f %8.2f\n", alpha, line[a].miss, formula, twice[a].miss, chain[a].miss);
    }
    return 0;
}