「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

箱があります。



中にミカンを3つ入れます。



箱に「愛媛みかん」という名札を付けます。



これで「愛媛みかん」という名札と「ミカン3つ」が関連付きましたよね。
「愛媛みかん」という名札を探せば、中身の「ミカン3つ」を見つけられます。

このときの名札「愛媛みかん」を専門用語で「キー（key）」と言います。



中身の「ミカン3つ」は「値（value）」と言います。



そして

「キー」と「値」をセットで管理するデータ構造

が「ハッシュ表」です。
「ハッシュテーブル」とも呼ばれます。



ハッシュ表は、キーを指定すれば対応する値をサクっと取得できるデータ構造です。
例えば連想配列を実現する仕組みとして、よく使われています。

以上で「ハッシュ表とは何ぞや？」の説明は終わりです。

キーと値をペアで管理するデータ構造

がハッシュ表です。

それでは次に、実際のハッシュ表の仕組みを見てみましょう。

ハッシュ表の中身は、大雑把に言えば配列です。

ちなみに配列は「データを入れておく箱の集まり」ね。
ミカン箱（変数）がたくさん集まったものだと思ってください。



あと、ついでなので書いておくと、それぞれのミカン箱は「配列の要素」と言います。
ミカン箱に割り振られている番号は「配列の添字」と言います。



配列の説明は、そんな感じです。
話を本題に戻します。

ハッシュ表は配列を使って実現します。

先程と同じように「愛媛みかん」という名札を付けた箱に「ミカン3つ」を入れる例で見ていきますね。

まずは名札「愛媛みかん」に注目してください。



この名札「愛媛みかん」を「ハッシュ関数」と呼ばれる関数に放り込むと、適当な数字になって出てきます。



補足として、ハッシュ関数さんは、とても真面目なやつです。
同じ名前を入れると必ず同じ数字を返してくれます。
そのため「愛媛みかん」は必ず「3」になります。
「4」になったり「10」になったりはしません。
「3」です。

同じ名前を入れると必ず同じ数字になる

は大事なポイントです。
覚えておいてください。

次に、ハッシュ関数から出てきた数字「3」に注目してください。
この「3」を専門用語で「ハッシュ値」と呼びます。



名札「愛媛みかん」をハッシュ関数に放り込んだら出てきたハッシュ値の「3」ですが、こいつを配列の添字と捉えるのです。
配列の添字が「3」の要素に値「ミカン3つ」を入れます。



これがハッシュ表の大まかな仕組みです。

名札（キー）をハッシュ関数に放り込んで、出てきたハッシュ値を添字に持つ配列の要素に値を入れる

のです。



「名札『愛媛みかん』の箱に何が入ってるか知りたいんだけど」と言われたら、名札「愛媛みかん」をハッシュ関数に放り込んで、返ってきたハッシュ値が添字になっている箱の中身を見ます。
このような手順を踏むことで、ハッシュ表さんはキーと値を紐付けています。

簡単ですね。
めでたし、めでたし。

……で話が済めば良いのですが、実は、もう少しだけ複雑です。

先程「ハッシュ値を添字に持つ配列の要素に値を入れる」と書きました。
ハッシュ関数の悩ましいところとして、違う名札を入れても同じハッシュ値になってしまうことがあるのです。
例えば「愛媛みかん」のハッシュ値が「3」だったのに対し「和歌山みかん」のハッシュ値も「3」になる場合があります。



これは困りますね。
和歌山みかんを添字「3」の箱に入れようと思ったら、すでに愛媛みかんが入っている状況になりかねません。



このように「あれ？入れようと思ったらもう別のが入ってるよ」な状況を「衝突 （collision）」と言います。
衝突が起こった場合は何らかの対処が必要になります。
対処方法は、大雑把に分類すると「別の場所に入れる」か「同居する」かです。
話が複雑になるので、衝突の回避方法については、ここでは細かく触れません。
興味がある方は他のところで情報を補完してください。

そんな感じです。
長くなったので、最後にもう一度まとめておきますね。

ハッシュ表はキーと値のペアでデータを管理します。
仕組みとしては配列です。
キーをハッシュ関数に放り込み、返ってきたハッシュ値を添字とする配列の要素に値を突っ込むことで、キーと値の紐付けを管理しています。
別のキーをハッシュ関数に放り込んでも同じハッシュ値になることがあります。
これを「衝突」と言います。
衝突が起こったら、何とかして収まるようにします。

これがハッシュ表さんです。