データをどうやって探す？
まず、皆さんに問題です。
下の配列のどこかのアドレスに「375」という数字データが格納されています。
どうすれば簡単に見つけられるでしょうか？
ちなみに、配列とはデータを格納する箱が沢山集まったもの、アドレスとはそれぞれの箱の番地だと考えて下さい。
色々な答えはあるかと思いますが、そもそも「375」がどこに格納されているか知ってたらわざわざ探す必要はないですよね。ただ、だからと言って、適当にアドレスを割り振っていたら、1個1個のデータがどこに入っているか覚えておくのが大変そうですね。
そこで、あるルールに沿ってデータの格納場所を決めるようにします。
例えば、「100で割った時の余りの数字のアドレスにデータを格納する」というルールを作っておけば、「375」はアドレス75に格納されているとすぐに分かります。
このように、データをあるルールに沿って格納しておくことで、簡単にデータを探索する方法をハッシュ法と言います。
ハッシュ法
あるルールに沿って格納しておくことで、簡単にデータを探索する方法
ハッシュ法
ハッシュではあるルールに沿ってデータの格納場所を決定しますが、格納場所を決めるルールをハッシュ関数、ハッシュ関数を使って求めた値をハッシュ値や関数値と言います。
ハッシュ法を使えば、データがどこのアドレスに格納されているか一発で分かります。データを格納する配列がどれだけ大きくても一発で分かるので、配列の大きさとデータ検索に掛かる時間に関係性はありません。
しかし、問題点もあって、「100で割った時の余りの数字のアドレスにデータを格納する」というルールだと「275」と「375」は同じ場所に格納することになってしまいます。このように格納場所が重複してしまうことを衝突と言います。衝突を回避する方法もありますが、基本情報では問われないので無理に勉強する必要はありません。
（おまけ）衝突を回避する方法
①チェイン法
衝突は1つの格納場所に1つのデータしか格納出来ないから起こります。
それなら1つの格納場所に複数のデータを格納できるようにすればOKですよね。これがチェイン法です。
②オープンアドレス法
衝突が起きた時、別のルールで再度格納場所を決める方法がオープンアドレス法です。例えば、衝突が起きた時は「元のデータに1を足した値を100で割り、その余りの数字のアドレスにデータを格納する」とルールを決めておきます。オープンアドレス法で衝突の頻度を下げることが出来ます。
オープンアドレス法を使うとデータの探索が少し面倒になるというデメリットもあります。
基本情報技術者試験での出題例
サンプル問題問7、令和元年度秋期問10
基本情報技術者
科目A サンプル問題問7、午前試験 令和元年度秋期問10
10進法で5桁の数 a1a2a3a4a5 をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a1＋a2＋a3＋a4＋a5，13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321は配列のどの位置に入るか。ここで，mod(x，13) は，xを13で割った余りとする。
ア 1 イ 2 ウ 7 エ 11
正解は”イ”
5桁の数字の各桁を足し合わせた値を13で割った余りが格納場所になります。
5+4+3+2+1=15を13で割った余りは2なので、答えはイです。
平成31年度春期問18
基本情報技術者
午前試験 平成31年度春期問18
データ検索時に使用される，理想的なハッシュ法の説明として，適切なものはどれか。
ア キーワード検索のヒット率を高めることを目的に作成した，一種の同義語・類義語リストを用いることによって，検索漏れを防ぐ技術である。
イ 蓄積されている膨大なデータを検索し，経営やマーケティングにとって必要な傾向，相関関係，パターンなどを導き出すための技術や手法である。
ウ データとそれに対する処理を組み合わせたオブジェクトに，認識や判断の機能を加え，利用者の検索要求に対して，その意図を判断する高度な検索技術である。
エ データを特定のアルゴリズムによって変換した値を格納アドレスとして用いる，高速でスケーラビリティの高いデータ検索技術である。
正解は”エ”
スケーラビリティとは、システムを大きくしやすいかどうか表す指標です。ここで言うシステムはデータの格納場所ですね。
ハッシュ法はデータを特定のアルゴリズムで変換した値を格納アドレスに使います。また、データの格納場所が分かっているので高速で探索でき、データの格納場所を大きくしてもデータ探索に掛かる時間は変わりません。スケーラビリティが高いと言えますね。よって答えはエです。
平成30年度春期問7
基本情報技術者
午前試験 平成30年度春期問7
表探索におけるハッシュ法の特徴はどれか。
ア 2分木を用いる方法の一種である。
イ 格納場所の衝突が発生しない方法である。
ウ キーの関数値によって格納場所を決める。
エ 探索に要する時間は表全体の大きさにほぼ比例する。
正解は”ウ”
ハッシュ法はデータの関数値によって格納場所を決めます。
格納するデータが｛社員番号、社員氏名、連絡先、役職｝のような構造になっている場合は、社員番号のようなデータを一意に特定出来るキーを特定のアルゴリズムで変換すれば良さそうです。よって答えはウです。
