データ構造の基礎知識　中編　ハッシュ

前回の続きです。

前回は配列、連結リストについて学習したので今回はハッシュについて学習します。

ハッシュとは?

key-value型のデータ構造であり、以下のような特徴を持ちます。

• 引数を１つ与えると数値の戻り値を１つ返す
• 同じ引数を与えた場合は必ず同じ値を返す
• 別の引数を与えた場合はなるべく違う値を返す(理論上、同じ値をとる可能性がある)

どのようにkeyと値を管理するのか?

1. あらかじめ配列を用意する
2. keyを入れるとある数字を返す関数を内部で用意する
3. keyによって変換された数字(例えば8)と対応する配列の場所(8番目)に値を入れる

ここの説明がわかりやすい
わわわIT用語辞典 ハッシュテーブル (hash table)

メリット

ある値への計算量がO(1)になる※厳密には違うが大体O(1)

デメリット

順番が保持されない

対策としてはkey自体が格納される連結リストを作っておき、順番を保持する。

衝突があり、再計算の必要がある。(リンク参照)