cplib-cpp

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub hitonanode/cplib-cpp

:heavy_check_mark: Fast hash map
(data_structure/fast_hash_map.hpp)

整数をキーとする固定容量の高速な連想配列．衝突は線形探索で解決する．ハッシュに使う乗数は実行時刻を seed として実行ごとに生成されるため，固定 seed を狙った衝突攻撃を受けにくい．

各スロットに世代番号を保持しており，clear() / reset() は現世代を更新するだけなので $O(1)$ で動作する．

使用方法

// N は 2 の冪で，格納する相異なるキー数以上にする．
HashMap<long long, long long, 1 << 20> mp;

mp.set(10, 20);  // key 10 に value 20 を設定
mp.get(10);      // 20（存在しないキーに対しては V{}）
mp.size();       // 1
mp.empty();      // false
mp.clear();      // 全要素を O(1) で削除

キーは 64 bit 以下の整数型でなければならない．計算量は set() / get() が平均 $O(1)$，clear() / reset() / size() / empty() が $O(1)$．格納する相異なるキー数が N を超えないようにする必要がある．

問題例

Verified with

Code

#pragma once

#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 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(); }
};
Back to top page