ハッシュテーブル 【hash table】 ハッシュマップ / hash map / ハッシュ表

概要

ハッシュテーブル(hash table)とは、データ構造の一つで、標識(キー:key)と対応する値(value)のペアを単位としてデータを格納し、キーを指定すると対応する値を高速に取得できる構造。
ハッシュテーブルのイメージ画像

解説 キーと値のペアを格納できるデータ型は連想配列辞書ハッシュマップなどと呼ばれ、多くのプログラミング言語で利用できる。ハッシュテーブルはこうしたデータ型の実装方式としてよく利用される。

ハッシュテーブルではキーから一定の計算手順により固定長の整数値などに単純化された値を求め、これを添字として配列に値を格納・取得する。この計算手順をハッシュ関数、算出された固定長の値をハッシュ値と呼ぶ。

長いキー(任意の文字列データなど)を許容する場合、異なるキーから同じハッシュ値が得られることがあるが、配列の各要素はそれ自体が配列やリストになっており、複数の値を区別して格納できるようになっている。

ハッシュテーブルでキーを元に対応する値を得るには、ハッシュ値の計算と、ハッシュ値が衝突した場合に複数の要素から探索する時間しかかからず、配列内を全探索する必要がない。単純なリストや配列などに比べ極めて高速にデータを取得することができる。

(2020.2.13更新)

他の用語辞典による「ハッシュテーブル」の解説 (外部サイト)

資格試験などの「ハッシュテーブル」の出題履歴

▼ 基本情報技術者試験
令3修6 問8】 自然数をキーとするデータを,ハッシュ表を用いて管理する。キーxのハッシュ関数 h(x) を h(x) = x mod nとすると,任意のキーaとbが衝突する条件はどれか。
令2修1 問9】 16進数で表される9個のデータ1A,35,3B,54,8E,A1,AF,B2,B3を順にハッシュ表に入れる。ハッシュ値をハッシュ関数 f(データ) = mod(データ,8) で求めたとき,最初に衝突が起こるのはどのデータか。