この記事では、ハッシュ法について、初心者にも分かりやすく、図解付きで丁寧に解説しています！
ハッシュ法
- ハッシュ法ではデータの格納場所(アドレス)をハッシュ関数に従って決定して、格納する。
ハッシュ法
まず、皆さんに問題です。下の配列に数字を格納しています。皆さんは以前に「375」を格納しました。どうすれば「375」を簡単に見つけられるでしょうか？
ちなみに、配列とはデータを格納する箱が沢山集まったもの、アドレスとはそれぞれの箱の番地だと考えて下さい。
色々な答えはあるかと思いますが、格納した数字からアドレスを計算できるようにしていたら簡単に探せますよね。
そこで、あるルールに沿ってデータの格納場所を決めるようにします。
例えば、「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なので、答えはイです。
令和6年度問2
基本情報技術者
科目A 令和6年度問2
キーが小文字のアルファベット1文字（a，b，…，zのいずれか）であるデータを，大きさが10のハッシュ表に格納する。ハッシュ関数として，アルファベットのASCIIコードを10進数表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。
ア a と i イ b と r ウ c と l エ d と x
正解は”エ”
ASCIIコードは、2進数がアルファベット順に割り当てられていると書いているので、例えば、a=00000000としたら、b=00000001、c=00000010、d=00000011・・・j=00001001、k=00001010・・・のようになると分かります。
これを10進数表記に変換したものをハッシュ表に格納していくので、こんな感じになります。この表を見ると、dとxが衝突していることが分かります。よって答えはエです。
今回の例ではa=00000000としましたが、a=00000001とかa=00000010としても同じようにdとxが衝突します。
ちなみに、本当はa=01100001だそうです。
平成31年度春期問18
基本情報技術者
午前試験 平成31年度春期問18
データ検索時に使用される，理想的なハッシュ法の説明として，適切なものはどれか。
ア キーワード検索のヒット率を高めることを目的に作成した，一種の同義語・類義語リストを用いることによって，検索漏れを防ぐ技術である。
イ 蓄積されている膨大なデータを検索し，経営やマーケティングにとって必要な傾向，相関関係，パターンなどを導き出すための技術や手法である。
ウ データとそれに対する処理を組み合わせたオブジェクトに，認識や判断の機能を加え，利用者の検索要求に対して，その意図を判断する高度な検索技術である。
エ データを特定のアルゴリズムによって変換した値を格納アドレスとして用いる，高速でスケーラビリティの高いデータ検索技術である。
正解は”エ”
スケーラビリティとは、システムを大きくしやすいかどうか表す指標です。ここで言うシステムはデータの格納場所ですね。
ハッシュ法はデータを特定のアルゴリズムで変換した値を格納アドレスに使います。また、データの格納場所が分かっているので高速で探索でき、データの格納場所を大きくしてもデータ探索に掛かる時間は変わりません。スケーラビリティが高いと言えますね。よって答えはエです。
平成30年度春期問7
基本情報技術者
午前試験 平成30年度春期問7
表探索におけるハッシュ法の特徴はどれか。
ア 2分木を用いる方法の一種である。
イ 格納場所の衝突が発生しない方法である。
ウ キーの関数値によって格納場所を決める。
エ 探索に要する時間は表全体の大きさにほぼ比例する。
正解は”ウ”
ハッシュ法はデータの関数値によって格納場所を決めます。
格納するデータが｛社員番号、社員氏名、連絡先、役職｝のような構造になっている場合は、社員番号のようなデータを一意に特定出来るキーを特定のアルゴリズムで変換すれば良さそうです。よって答えはウです。
