test/yosupo/ds/associative_array.test.cpp

View this file on GitHub
Last update: 2025-09-20 17:47:50+07:00
Problem: https://judge.yosupo.jp/problem/associative_array

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"

#include <bits/stdc++.h>
using namespace std;

#include "ds/hashmap.hpp"
#include "other/chash.hpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    hash_map<int64_t, int64_t, chash> m;
    m.set_load_factor(90);
    m.reserve(q);
    while (q--) {
        int t;
        int64_t k, v;
        cin >> t >> k;
        if (t == 0) {
            cin >> v;
            m[k] = v;
        } else {
            cout << m[k] << "\n";
        }
    }
}

#line 1 "test/yosupo/ds/associative_array.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/associative_array"

#include <bits/stdc++.h>
using namespace std;

#line 2 "ds/hashmap.hpp"

template<class K, class V, class Hash> struct hash_map_base {
    using u32 = uint32_t;
    using u64 = uint64_t;
    using node = pair<K, V>;

    u32 sz = 0, cap = 8, mask = cap - 1, load = 75;
    vector<node> data;
    vector<bool> used;
    V def_val{};

    hash_map_base() : data(cap), used(cap) {}

    void reserve(int n) { extend(100 * n / load); }
    int size() const { return sz; }
    bool empty() const { return sz == 0; }
    void set_default(V v) { def_val = v; }
    void set_load_factor(u32 nload) { load = nload; }

    V &operator[](const K &k) { return *emplace(k, def_val); }
    V *emplace(const K &k, const V &v) {
        u32 hash = chash(k);
        for (;;) {
            if (!used[hash]) {
                if (100 * sz >= load * cap) {
                    extend(cap + 1);
                    return emplace(k, v);
                }
                sz++;
                data[hash] = {k, v};
                used[hash] = true;
                return &data[hash].second;
            }
            if (data[hash].first == k) return &data[hash].second;
            ++hash &= mask;
        }
    }
    void erase(const K &k) {
        u32 hash = chash(k);
        for (;;) {
            if (!used[hash]) return;
            if (data[hash].first == k) {
                sz--;
                used[hash] = false;
                ++hash &= mask;
                for (; used[hash]; ++hash &= mask) {
                    auto [tmp_k, tmp_v] = data[hash];
                    sz--;
                    used[hash] = false;
                    emplace(tmp_k, tmp_v);
                }
                return;
            }
            ++hash &= mask;
        }
    }
    V *find(const K &k) {
        u32 hash = chash(k);
        for (;;) {
            if (!used[hash]) return nullptr;
            if (data[hash].first == k) return &data[hash].second;
            ++hash &= mask;
        }
    }

  private:
    void extend(int _n) {
        while (cap < _n) cap *= 2;
        mask = cap - 1;
        vector<node> d(cap);
        vector<bool> u(cap);
        for (int i = 0; i < used.size(); i++) {
            if (used[i]) {
                u32 hash = chash(data[i].first);
                while (u[hash]) ++hash &= mask;
                d[hash] = data[i];
                u[hash] = true;
            }
        }
        data.swap(d), used.swap(u);
    }
    u32 chash(const K &k) {
        static const u64 a = mt19937_64((u64)make_unique<char>().get())() | 1;
        return u32(a * Hash{}(k) >> 32) & mask;
    }
};
template<class K, class V, class Hash = hash<K>>
struct hash_map : hash_map_base<K, V, Hash> {
    using base = hash_map_base<K, V, Hash>;
    struct iter {
        hash_map &hm;
        int p;
        iter(hash_map &_hm, int _p) : hm(_hm), p(_p) {
            while (p < hm.cap && !hm.used[p]) p++;
        }
        bool operator!=(const iter &o) const { return p != o.p; }
        void operator++() {
            p++;
            while (p < hm.cap && !hm.used[p]) p++;
        }
        pair<K, V> &operator*() { return hm.data[p]; }
    };
    iter begin() { return {*this, 0}; }
    iter end() { return {*this, (int)base::cap}; }
};
struct _null_type {};
template<class K, class Hash = hash<K>>
struct hash_set : hash_map_base<K, _null_type, Hash> {
    using base = hash_map_base<K, _null_type, Hash>;
    struct iter {
        hash_set &hs;
        int p;
        iter(hash_set &_mp, int _p) : hs(_mp), p(_p) {
            while (p < hs.cap && !hs.used[p]) p++;
        }
        bool operator!=(const iter &o) const { return p != o.p; }
        void operator++() {
            p++;
            while (p < hs.cap && !hs.used[p]) p++;
        }
        const K &operator*() { return hs.data[p].first; }
    };
    iter begin() { return {*this, 0}; }
    iter end() { return {*this, (int)base::cap}; }
    void insert(const K &k) { base::emplace(k, {}); }
    template<class... Ts> void emplace(Ts &&...x) {
        base::emplace({forward<Ts>(x)...}, {});
    }
};
#line 2 "other/chash.hpp"

template<class T, class D = void> struct _chash;
template<class T> inline void hash_combine(uint64_t &seed, const T &v) {
    seed ^= _chash<T>{}(v) + 0x9e3779b97f4a7c15 + (seed << 12) + (seed >> 4);
}
template<class T> struct _chash<T, enable_if_t<is_integral_v<T>>> {
    uint64_t operator()(T x) const {
        // uncomment to use with STL
        static const uint64_t RAND =
            mt19937_64((uint64_t)make_unique<char>().get())();
        x ^= RAND;
        (x ^= x >> 30) *= 0xbf58476d1ce4e5b9;
        (x ^= x >> 27) *= 0x94d049bb133111eb;
        x ^= x >> 31;
        return x;
    }
};
template<class T> struct _chash<T, void_t<decltype(begin(declval<T>()))>> {
    uint64_t operator()(const T &a) const {
        uint64_t h = 0;
        for (auto &x : a) hash_combine(h, x);
        return h;
    }
};
template<class... Ts> struct _chash<tuple<Ts...>> {
    uint64_t operator()(const tuple<Ts...> &a) const {
        uint64_t h = 0;
        apply([&h](auto &&...x) { (hash_combine(h, x), ...); }, a);
        return h;
    }
};
template<class T, class U> struct _chash<pair<T, U>> {
    uint64_t operator()(const pair<T, U> &a) const {
        return _chash<tuple<T, U>>{}(a);
    }
};
struct chash {
    template<class T> uint64_t operator()(const T &x) const {
        return _chash<T>{}(x);
    }
};
#line 8 "test/yosupo/ds/associative_array.test.cpp"

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    hash_map<int64_t, int64_t, chash> m;
    m.set_load_factor(90);
    m.reserve(q);
    while (q--) {
        int t;
        int64_t k, v;
        cin >> t >> k;
        if (t == 0) {
            cin >> v;
            m[k] = v;
        } else {
            cout << m[k] << "\n";
        }
    }
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	2_powers_00	AC	272 ms	36 MB
g++	c_sharp_killer_00	AC	197 ms	36 MB
g++	example_00	AC	5 ms	4 MB
g++	many_0set_00	AC	249 ms	36 MB
g++	many_0set_sparse_00	AC	82 ms	12 MB
g++	max_many_updates_00	AC	294 ms	36 MB
g++	max_random_00	AC	262 ms	36 MB
g++	max_random_01	AC	272 ms	36 MB
g++	max_random_02	AC	263 ms	36 MB
g++	py_killer_00	AC	215 ms	36 MB
g++	py_killer_01	AC	203 ms	36 MB
g++	random_00	AC	90 ms	12 MB
g++	random_01	AC	104 ms	12 MB
g++	random_02	AC	131 ms	20 MB
g++	sparse_keys_00	AC	92 ms	12 MB
g++	sparse_keys_01	AC	108 ms	12 MB
g++	unordered_map_killer_00	AC	248 ms	36 MB
g++	unordered_map_killer_01	AC	269 ms	36 MB
g++	unordered_map_killer_02	AC	255 ms	36 MB
g++	unordered_map_killer_03	AC	255 ms	36 MB
clang++	2_powers_00	AC	268 ms	36 MB
clang++	c_sharp_killer_00	AC	196 ms	36 MB
clang++	example_00	AC	5 ms	4 MB
clang++	many_0set_00	AC	255 ms	36 MB
clang++	many_0set_sparse_00	AC	84 ms	12 MB
clang++	max_many_updates_00	AC	289 ms	36 MB
clang++	max_random_00	AC	252 ms	36 MB
clang++	max_random_01	AC	268 ms	36 MB
clang++	max_random_02	AC	247 ms	36 MB
clang++	py_killer_00	AC	197 ms	36 MB
clang++	py_killer_01	AC	212 ms	36 MB
clang++	random_00	AC	92 ms	12 MB
clang++	random_01	AC	119 ms	12 MB
clang++	random_02	AC	136 ms	20 MB
clang++	sparse_keys_00	AC	91 ms	12 MB
clang++	sparse_keys_01	AC	107 ms	12 MB
clang++	unordered_map_killer_00	AC	261 ms	36 MB
clang++	unordered_map_killer_01	AC	324 ms	36 MB
clang++	unordered_map_killer_02	AC	258 ms	36 MB
clang++	unordered_map_killer_03	AC	244 ms	36 MB