HashMap (data_structure/hash_map.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-05-03 16:45:01+09:00
• Include: #include "data_structure/hash_map.hpp"

HashMap は、キーと値のペアを格納する連想配列データ構造です。オープンアドレス法を用いて実装されています。

テンプレートパラメータ:

• K: キーの型。デフォルトは uint64_t。
• V: 値の型。デフォルトは uint64_t。
• f: キーのハッシュ値を計算する関数。uint64_t f(const K&) の形式である必要があります。デフォルトはキーそのものを返すラムダ式。
• e: 値の単位元を返す関数。V e() の形式である必要があります。operator[] で新しい要素が挿入される際にこの値で初期化されます。デフォルトは V{} を返すラムダ式。

使い方

コンストラクタ

HashMap(uint32_t _n = 8)

説明

初期バケットサイズ _n を指定して HashMap を構築します。バケットサイズは2の冪乗である必要があります。指定しない場合は8で初期化されます。

• _n: 初期バケットサイズ (2の冪乗)。

計算量

$O(_n)$

operator[]

V& operator[](const K& c)

説明

キー c に対応する値への参照を返します。キー c が存在しない場合は、新しく要素が挿入され、値は単位元 e() で初期化されます。

• c: アクセスまたは挿入するキー。
• 戻り値: キー c に対応する値への参照。

計算量

平均 $O(1)$、最悪 $O(N)$ (リハッシュ時を含む)

contains

bool contains(const K& c)

説明

キー c が HashMap に存在するかどうかを判定します。

• c: 検索するキー。
• 戻り値: キー c が存在すれば true、そうでなければ false。

計算量

平均 $O(1)$、最悪 $O(N)$

イテレータ

HashMap はイテレータをサポートしており、範囲ベースforループなどで要素を走査できます。イテレータは std::pair<const K&, V&> を参照します。

begin

Iterator begin()

説明

HashMap の最初の要素を指すイテレータを返します。

計算量

平均 $O(1)$、最悪 $O(N)$

end

Iterator end()

説明

HashMap の末尾の要素の次を指すイテレータを返します。

計算量

$O(1)$

Verified with

• test/associative_array.test.cpp

Code

#pragma once
#include <chrono>
#include <cstdint>
#include <vector>

template <typename K = uint64_t, typename V = uint64_t, auto f = [](const K& c) { return c; }, auto e = []() { return V{}; }>
struct HashMap {
    uint32_t n, s, shift;
    uint64_t r;
    std::vector<K> k;
    std::vector<V> v;
    std::vector<bool> u;
    HashMap(uint32_t _n = 8) : n(_n), s(0), shift(64 - std::__lg(n)), k(n), v(n), u(n) {
        r = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
        r ^= r >> 16;
        r ^= r << 32;
    }
    void reallocate() {
        n <<= 1;
        std::vector<K> nk(n);
        std::vector<V> nv(n);
        std::vector<bool> nu(n);
        --shift;
        for (int i = 0, size = u.size(); i < size; ++i) {
            if (u[i]) {
                uint32_t h = (f(k[i]) * r) >> shift;
                while (nu[h]) {
                    h = (h + 1) & (n - 1);
                }
                nk[h] = k[i];
                nv[h] = v[i];
                nu[h] = 1;
            }
        }
        std::swap(nk, k);
        std::swap(nv, v);
        std::swap(nu, u);
    }
    V& operator[](const K& c) {
        uint32_t h = f(c) * r >> shift;
        while (true) {
            if (!u[h]) {
                if (n <= s + (s >> 2)) {
                    reallocate();
                    return this->operator[](c);
                }
                k[h] = c;
                u[h] = 1;
                ++s;
                return v[h] = e();
            }
            if (k[h] == c) return v[h];
            h = (h + 1) & (n - 1);
        }
    }

    bool contains(const K& c) {
        uint32_t h = f(c) * r >> shift;
        while (true) {
            if (!u[h]) return false;
            if (k[h] == c) return true;
            h = (h + 1) & (n - 1);
        }
    }

    struct Iterator {
        HashMap* map;
        uint32_t idx;

        Iterator(HashMap* m, uint32_t i) : map(m), idx(i) {}

        std::pair<const K&, V&> operator*() {
            return {map->k[idx], map->v[idx]};
        }

        std::pair<const K&, V&> operator*() const {
            return {map->k[idx], map->v[idx]};
        }

        Iterator& operator++() {
            do {
                ++idx;
            } while (idx < map->n && !map->u[idx]);
            return *this;
        }

        bool operator==(const Iterator& other) const {
            return map == other.map && idx == other.idx;
        }

        bool operator!=(const Iterator& other) const {
            return !(*this == other);
        }
    };

    Iterator begin() {
        uint32_t i = 0;
        while (i < n && !u[i]) {
            ++i;
        }
        return Iterator(this, i);
    }

    Iterator end() {
        return Iterator(this, n);
    }
};

#line 2 "data_structure/hash_map.hpp"
#include <chrono>
#include <cstdint>
#include <vector>

template <typename K = uint64_t, typename V = uint64_t, auto f = [](const K& c) { return c; }, auto e = []() { return V{}; }>
struct HashMap {
    uint32_t n, s, shift;
    uint64_t r;
    std::vector<K> k;
    std::vector<V> v;
    std::vector<bool> u;
    HashMap(uint32_t _n = 8) : n(_n), s(0), shift(64 - std::__lg(n)), k(n), v(n), u(n) {
        r = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
        r ^= r >> 16;
        r ^= r << 32;
    }
    void reallocate() {
        n <<= 1;
        std::vector<K> nk(n);
        std::vector<V> nv(n);
        std::vector<bool> nu(n);
        --shift;
        for (int i = 0, size = u.size(); i < size; ++i) {
            if (u[i]) {
                uint32_t h = (f(k[i]) * r) >> shift;
                while (nu[h]) {
                    h = (h + 1) & (n - 1);
                }
                nk[h] = k[i];
                nv[h] = v[i];
                nu[h] = 1;
            }
        }
        std::swap(nk, k);
        std::swap(nv, v);
        std::swap(nu, u);
    }
    V& operator[](const K& c) {
        uint32_t h = f(c) * r >> shift;
        while (true) {
            if (!u[h]) {
                if (n <= s + (s >> 2)) {
                    reallocate();
                    return this->operator[](c);
                }
                k[h] = c;
                u[h] = 1;
                ++s;
                return v[h] = e();
            }
            if (k[h] == c) return v[h];
            h = (h + 1) & (n - 1);
        }
    }

    bool contains(const K& c) {
        uint32_t h = f(c) * r >> shift;
        while (true) {
            if (!u[h]) return false;
            if (k[h] == c) return true;
            h = (h + 1) & (n - 1);
        }
    }

    struct Iterator {
        HashMap* map;
        uint32_t idx;

        Iterator(HashMap* m, uint32_t i) : map(m), idx(i) {}

        std::pair<const K&, V&> operator*() {
            return {map->k[idx], map->v[idx]};
        }

        std::pair<const K&, V&> operator*() const {
            return {map->k[idx], map->v[idx]};
        }

        Iterator& operator++() {
            do {
                ++idx;
            } while (idx < map->n && !map->u[idx]);
            return *this;
        }

        bool operator==(const Iterator& other) const {
            return map == other.map && idx == other.idx;
        }

        bool operator!=(const Iterator& other) const {
            return !(*this == other);
        }
    };

    Iterator begin() {
        uint32_t i = 0;
        while (i < n && !u[i]) {
            ++i;
        }
        return Iterator(this, i);
    }

    Iterator end() {
        return Iterator(this, n);
    }
};

Back to top page