[ 通常表示 ]  [ 簡易表示 ]  [ シンプル表示 ]

「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典イメージぴよ画像「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

ハッシュ表

pointこの用語のポイント

pointデータ構造だよ

pointキーと値のペアで管理するよ

スポンサーリンク

簡単に書くよ

ハッシュ表とは

「ハッシュテーブル」のこと。
つまり

データの入った箱に名札を付けて、名札と中身のデータをセットで管理するやり方
であり

キーと値の組み合わせを一つのかたまりとして管理するデータ構造
です。

image piyo

詳しく書くよ

※このページの説明は「ハッシュテーブル」の説明と、ほとんど同じです。既に「ハッシュテーブル」の説明をご覧になった方は、読んでもあまり意味は無いと思います。

箱があります。

ハッシュ表

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

ハッシュ表2

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

ハッシュ表3

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

このときの名札「愛媛みかん」を専門用語で「キー(key)」と言います。
中身「ミカン3つ」は「値(value)」です。

そして、このキーと値をセットで管理するデータ構造が「ハッシュ表」です。
ハッシュテーブル」とも呼ばれます。

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

「ハッシュ表とは何ぞや?」の説明は、これで終わりです。
「キーと値をペアで管理するデータ構造」がハッシュ表です。

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

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

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

ハッシュ表4

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

ハッシュ表5

配列の説明は、そんな感じですね。

少し話が逸れてしまいました。
ハッシュ表は、この配列を使って実現します。

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

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

ハッシュ表6

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

ハッシュ表7

補足として、ハッシュ関数さんは真面目なやつです。
同じ名前を入れると必ず同じ数字を返してくれます。

そのため「愛媛みかん」は必ず「3」になります。
4になったり10になったりは、しません。

「同じ名前を入れると必ず同じ数字」が大事です。
覚えておいてください。

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

ハッシュ表8

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

ハッシュ表9

これがハッシュ表の大まかな仕組みです。
もう一度まとめると「名札(キー)をハッシュ関数に放り込んで、出てきたハッシュ値を添字に持つ配列の要素に値を入れる」となります。

ハッシュ表10

こうすることで、キーと値をセットで管理することができるのです。

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

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

……で話が済めば良いのですが、もうちょっとだけ複雑です。

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

ハッシュ表11

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

ハッシュ表12

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

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

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

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

image piyo2

一言でまとめるよ

まぁ「ハッシュ表」って単語が出てきたら「キーと値のペアで管理するデータ構造なんだな~」と、お考えください。

一番上に戻るよ
スポンサーリンク