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

概要

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

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

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

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