mmrz's library

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

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

ハッシュマップ
(data_structure/hash_map.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "data_structure/hash_map.hpp"

ハッシュマップ

使い方

hash_map<Key, Val, N, HashFunc> : $N$ 程度の種類を格納できるハッシュマップを用意。

1. $N$ は格納予定の量の $2$ 倍程度とするとよさそう
2. ハッシュ関数が無い型を使うときは HashFunc を定義する

概要

unordered_map の代用

Verified with

• verify/yosupo/associative_array.test.cpp
• verify/yukicoder/8016.test.cpp

Code

#pragma once

#include<bitset>
#include<cstdint>

template<typename Key, typename Val, uint32_t N, typename HashFunc = std::hash<Key>>
struct hash_map {
	static_assert(__builtin_popcount(N) == 1);
	Key key[N];
	Val val[N];
	std::bitset<N> use;
	
	static constexpr uint32_t shift = 64 - __builtin_ctz(N);
	static constexpr uint64_t r = 11995408973635179863ULL;

	Val& operator[](const Key & k) noexcept {
		uint64_t h = HashFunc{}(k);
		uint32_t hash = (h*r) >> shift;
		while(true){
			if(!use[hash]){
				key[hash] = k;
				use[hash] = 1;
				return val[hash];
			}
			if(key[hash] == k)return val[hash];
			(++hash) &= (N-1);
		}
	}
};

#line 2 "data_structure/hash_map.hpp"

#include<bitset>
#include<cstdint>

template<typename Key, typename Val, uint32_t N, typename HashFunc = std::hash<Key>>
struct hash_map {
	static_assert(__builtin_popcount(N) == 1);
	Key key[N];
	Val val[N];
	std::bitset<N> use;
	
	static constexpr uint32_t shift = 64 - __builtin_ctz(N);
	static constexpr uint64_t r = 11995408973635179863ULL;

	Val& operator[](const Key & k) noexcept {
		uint64_t h = HashFunc{}(k);
		uint32_t hash = (h*r) >> shift;
		while(true){
			if(!use[hash]){
				key[hash] = k;
				use[hash] = 1;
				return val[hash];
			}
			if(key[hash] == k)return val[hash];
			(++hash) &= (N-1);
		}
	}
};

Back to top page