HashMap
(data-structure/HashMap.hpp)

• View this file on GitHub
• Last update: 2023-03-13 02:01:43+09:00
• Include: #include "data-structure/HashMap.hpp"

説明

• HashMap<Key,Val,logn,initval>: Constructor

• operator[](i): $i$にあたる場所の値を取得

• count(i): すでに値が代入されているかの判定

Verified with

• test/yosupo/Data-Structure/Associative-Array.test.cpp

Code

#include <chrono>

template <class Key, class Val, int logn = 20, Val initval = Val()>
struct HashMap {
  using uint = unsigned int;
  using ull = unsigned long long;
  private:
  static constexpr unsigned int N = 1 << logn;
  Key *keys;
  Val *vals;
  bitset<N> flag;
  const ull r;
  static constexpr uint shift = 64 - logn;
  constexpr ull rng() const{
    ull m = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }
  public:
  HashMap() : keys(new Key[N]), vals(new Val[N]), r(rng()){}
  inline constexpr Val &operator[](const Key i) noexcept{
    uint hash = (ull(i) * r) >> shift;
    while(true){
      if(!flag[hash]){
        keys[hash] = i;
        flag[hash] = 1;
        return vals[hash] = initval;
      }
      if(keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (N - 1);
    }
  }
  inline constexpr bool count(const Key i) const noexcept{
    uint hash = (ull(i) * r) >> shift;
    while(true){
      if(!flag[hash]) return false;
      if(keys[hash] == i) return true;
      hash = (hash + 1) & (N - 1);
    }
  }
};

#line 1 "data-structure/HashMap.hpp"
#include <chrono>

template <class Key, class Val, int logn = 20, Val initval = Val()>
struct HashMap {
  using uint = unsigned int;
  using ull = unsigned long long;
  private:
  static constexpr unsigned int N = 1 << logn;
  Key *keys;
  Val *vals;
  bitset<N> flag;
  const ull r;
  static constexpr uint shift = 64 - logn;
  constexpr ull rng() const{
    ull m = chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
    m ^= m >> 16;
    m ^= m << 32;
    return m;
  }
  public:
  HashMap() : keys(new Key[N]), vals(new Val[N]), r(rng()){}
  inline constexpr Val &operator[](const Key i) noexcept{
    uint hash = (ull(i) * r) >> shift;
    while(true){
      if(!flag[hash]){
        keys[hash] = i;
        flag[hash] = 1;
        return vals[hash] = initval;
      }
      if(keys[hash] == i) return vals[hash];
      hash = (hash + 1) & (N - 1);
    }
  }
  inline constexpr bool count(const Key i) const noexcept{
    uint hash = (ull(i) * r) >> shift;
    while(true){
      if(!flag[hash]) return false;
      if(keys[hash] == i) return true;
      hash = (hash + 1) & (N - 1);
    }
  }
};

Back to top page