test/1_library_checker/ds/HashMap.test.cpp

• View this file on GitHub
• Last update: 2026-08-25 20:45:59+07:00
• Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

• ds/HashMap.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#include "ds/HashMap.hpp"
#include <bits/stdc++.h>
using namespace std;

void solve() {
        int Q;
        cin >> Q;
        // minimize resizing
        HashMap<int64_t, int64_t> hash_map(Q);
        while (Q--) {
                int t;
                cin >> t;
                if (!t) {
                        int64_t k, v;
                        cin >> k >> v;
                        hash_map[k] = v;
                } else {
                        int64_t k;
                        cin >> k;
                        cout << hash_map[k] << '\n';
                }
        }
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        int t = 1;
        // cin >> t;
        while (t--) solve();

        return 0;
}

#line 1 "test/1_library_checker/ds/HashMap.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"
#line 2 "ds/HashMap.hpp"
#include <cassert>
#include <chrono>
#include <cstdint>
#include <vector>

template <typename K, typename V>
class HashMap {
        struct Node {
                K key;
                V val;
                bool exists = false;
        };
        std::vector<Node> table;
        uint32_t cap, size;
        uint64_t random_seed;
        static uint64_t splitmix64(uint64_t x) {
                // http://xorshift.di.unimi.it/splitmix64.c
                x += 0x9e3779b97f4a7c15;
                x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
                x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
                return x ^ (x >> 31);
        }
        uint32_t get_index(K key) {
                uint64_t hash = splitmix64((uint64_t)key + random_seed);
                return hash & (cap - 1);
        }
        void expand() {
                std::vector<Node> old_table = table;
                build(cap << 1);
                for (const auto &node : old_table) {
                        if (node.exists) {
                                uint32_t idx = get_index(node.key);
                                while (table[idx].exists) {
                                        idx++;
                                        idx &= (cap - 1);
                                }
                                table[idx] = {node.key, node.val, true};
                                size++;
                        }
                }
        }
public:
        HashMap(uint32_t n = 1 << 20) {
                uint32_t pw = 1;
                while (pw < n) pw <<= 1;
                build(pw);
        }
        void build(uint32_t n) {
                cap = n;
                size = 0;
                table.assign(cap, {});
                random_seed = std::chrono::steady_clock::now().time_since_epoch().count();
        }
        void insert(K key, V val) { (*this)[key] = val; }
        V &operator[](K key) {
                if (size >= cap / 2) expand();
                uint32_t idx = get_index(key);
                while (table[idx].exists) {
                        if (table[idx].key == key) {
                                return table[idx].val;
                        }
                        idx++;
                        idx &= (cap - 1);
                }
                table[idx] = {key, V{}, true};
                size++;
                return table[idx].val;
        }
        V get(K key, V default_val = V{}) {
                uint32_t idx = get_index(key);
                while (table[idx].exists) {
                        if (table[idx].key == key) {
                                return table[idx].val;
                        }
                        idx++;
                        idx &= (cap - 1);
                }
                return default_val;
        }
        int sz() { return size; }
};
#line 3 "test/1_library_checker/ds/HashMap.test.cpp"
#include <bits/stdc++.h>
using namespace std;

void solve() {
        int Q;
        cin >> Q;
        // minimize resizing
        HashMap<int64_t, int64_t> hash_map(Q);
        while (Q--) {
                int t;
                cin >> t;
                if (!t) {
                        int64_t k, v;
                        cin >> k >> v;
                        hash_map[k] = v;
                } else {
                        int64_t k;
                        cin >> k;
                        cout << hash_map[k] << '\n';
                }
        }
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(NULL);

        int t = 1;
        // cin >> t;
        while (t--) solve();

        return 0;
}

Back to top page