定本 Cプログラマのためのアルゴリズムとデータ構造 2-2-5

ハッシュ法ですね。
hashing。

キーの値から添え字を得る関数をハッシュ関数という。

例えば、大きさ100の配列を使って、整数のキーをもつデータを扱うには
ハッシュ関数hash(key)を、h(key) = key % 100、などとして
ハッシュ値を得ればよいだろう。

ハッシュ法はハッシュ関数の実装によるけど、キーの衝突をなかなか避けられない。
たとえば、上記のハッシュ関数では100で割ったあまりをハッシュ値同じになるキーはすべて衝突してしまう。

キーが衝突したときに、同一のハッシュ値をもつデータをポインタでつないだり、(チェインとかいう)
または、完全に衝突しないようなハッシュ関数を生成したり（完全ハッシュ法とかいう）すればいい。

通常のはハッシュ関数は基本操作だけで実現できるから、O(1)になる。
ハッシュが衝突し、かつデータの個数が多めになると、衝突の解析にコストがかかる。

コストの大半は衝突や衝突の回避によって生まれる。
よってハッシュ関数の質を高めることがコスト削減につながる。
配列の大きさに対してデータの割合が8割をこえると、
ランダム値によるhashingでは衝突を起こし始める。
そうするとコストがO(1)を超えてしまう。

ハッシュ法はデータ格納領域を十分に用意できる場合には、
関数をそれほど工夫しなくても十分な効果を得られる。
また、関数の選択を正しく行えば、登録や探索のコストを
O(1)に収めたり、近づけたりできる。