data_structure/test/fast_hash_map.test.cpp

• View this file on GitHub
• Last update: 2026-09-05 01:34:00+09:00
• Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

• Fast hash map (data_structure/fast_hash_map.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#include "../fast_hash_map.hpp"
#include <cassert>
#include <iostream>

HashMap<unsigned long long, unsigned long long, 1 << 21> mp;

int main() {
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false);

    int Q;
    std::cin >> Q;
    while (Q--) {
        int type;
        unsigned long long key;
        std::cin >> type >> key;
        if (type == 0) {
            unsigned long long value;
            std::cin >> value;
            mp.set(key, value);
        } else {
            std::cout << mp.get(key) << '\n';
        }
    }

    mp.clear();
    assert(mp.empty());
    assert(mp.size() == 0);
    assert(mp.get(1) == 0);

    mp.set(1, 2);
    mp.set(1, 3);
    assert(mp.size() == 1);
    assert(mp.get(1) == 3);

    mp.reset();
    assert(mp.empty());
    assert(mp.get(1) == 0);

    HashMap<int, int, 1> one;
    assert(one.get(-1) == 0);
    one.set(-1, 4);
    assert(one.size() == 1);
    assert(one.get(-1) == 4);
    assert(one.get(0) == 0);
    one.clear();
    one.set(0, 5);
    assert(one.get(0) == 5);

    HashMap<int, int, 8> full;
    for (int i = 0; i < 8; ++i) full.set(i, i + 1);
    assert(full.size() == 8);
    for (int i = 0; i < 8; ++i) assert(full.get(i) == i + 1);
    assert(full.get(8) == 0);
    full.clear();
    full.set(8, 9);
    assert(full.size() == 1);
    assert(full.get(8) == 9);
}

#line 1 "data_structure/test/fast_hash_map.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#line 2 "data_structure/fast_hash_map.hpp"

#include <array>
#include <bit>
#include <cassert>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <random>
#include <type_traits>

// Fixed-capacity hash map for integer keys.
// N must be a power of two. At most N distinct keys can be stored.
template <typename K, typename V, std::size_t N> struct HashMap {
    static_assert(std::has_single_bit(N));
    static_assert(std::is_integral_v<K>);
    static_assert(sizeof(K) <= sizeof(std::uint64_t));

private:
    std::array<K, N> keys;
    std::array<V, N> values;
    std::array<std::uint32_t, N> versions{};

    std::uint32_t version = 1;
    std::size_t count = 0;
    std::uint64_t multiplier;

    static std::uint64_t make_multiplier() noexcept {
        // Use a nondeterministic seed
        std::mt19937_64 mt(std::chrono::steady_clock::now().time_since_epoch().count());
        return mt() | 1;
    }

    std::size_t hash(K key) const noexcept {
        if constexpr (N == 1) {
            return 0;
        } else {
            constexpr int shift = 64 - std::countr_zero(N);
            return (static_cast<std::uint64_t>(key) * multiplier) >> shift;
        }
    }

public:
    HashMap() : multiplier(make_multiplier()) {}

    void set(K key, V value) noexcept {
        std::size_t pos = hash(key);
        for (std::size_t step = 0; step < N; ++step) {
            if (versions[pos] != version) {
                keys[pos] = key;
                values[pos] = value;
                versions[pos] = version;
                assert(count < N);
                ++count;
                return;
            }
            if (keys[pos] == key) {
                values[pos] = value;
                return;
            }
            pos = (pos + 1) & (N - 1);
        }
        assert(false && "HashMap capacity exceeded");
    }

    V get(K key) const noexcept {
        std::size_t pos = hash(key);
        for (std::size_t step = 0; step < N; ++step) {
            if (versions[pos] != version) return V{};
            if (keys[pos] == key) return values[pos];
            pos = (pos + 1) & (N - 1);
        }
        return V{};
    }

    std::size_t size() const noexcept { return count; }
    bool empty() const noexcept { return count == 0; }

    void clear() noexcept {
        ++version;
        count = 0;
    }
    void reset() noexcept { clear(); }
};
#line 4 "data_structure/test/fast_hash_map.test.cpp"
#include <iostream>

HashMap<unsigned long long, unsigned long long, 1 << 21> mp;

int main() {
    std::cin.tie(nullptr), std::ios::sync_with_stdio(false);

    int Q;
    std::cin >> Q;
    while (Q--) {
        int type;
        unsigned long long key;
        std::cin >> type >> key;
        if (type == 0) {
            unsigned long long value;
            std::cin >> value;
            mp.set(key, value);
        } else {
            std::cout << mp.get(key) << '\n';
        }
    }

    mp.clear();
    assert(mp.empty());
    assert(mp.size() == 0);
    assert(mp.get(1) == 0);

    mp.set(1, 2);
    mp.set(1, 3);
    assert(mp.size() == 1);
    assert(mp.get(1) == 3);

    mp.reset();
    assert(mp.empty());
    assert(mp.get(1) == 0);

    HashMap<int, int, 1> one;
    assert(one.get(-1) == 0);
    one.set(-1, 4);
    assert(one.size() == 1);
    assert(one.get(-1) == 4);
    assert(one.get(0) == 0);
    one.clear();
    one.set(0, 5);
    assert(one.get(0) == 5);

    HashMap<int, int, 8> full;
    for (int i = 0; i < 8; ++i) full.set(i, i + 1);
    assert(full.size() == 8);
    for (int i = 0; i < 8; ++i) assert(full.get(i) == i + 1);
    assert(full.get(8) == 0);
    full.clear();
    full.set(8, 9);
    assert(full.size() == 1);
    assert(full.get(8) == 9);
}

Back to top page