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

概要

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

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

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

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

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

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。