【基本情報】ハッシュ法を完全に理解する！過去問と一緒に解説！

この記事ではハッシュ法についてIT初心者にも分かりやすく解説します。

ハッシュ法

ハッシュ法ではデータの格納場所をハッシュ関数に従って決定して、そこに格納します。

基本情報ではハッシュ法に関する問題が出題されます。是非最後までご覧ください。

データをどうやって探す？
ハッシュ法
基本情報技術者試験での出題例
基本情報に関する他の記事

データをどうやって探す？

まず、皆さんに問題です。
下の配列のどこかのアドレスに「375」という数字データが格納されています。
どうすれば簡単に見つけられるでしょうか？
ちなみに、配列とはデータを格納する箱が沢山集まったもの、アドレスとはそれぞれの箱の番地だと考えて下さい。

色々な答えはあるかと思いますが、そもそも「375」がどこに格納されているか知ってたらわざわざ探す必要はないですよね。ただ、だからと言って、適当にアドレスを割り振っていたら、1個1個のデータがどこに入っているか覚えておくのが大変そうですね。

そこで、あるルールに沿ってデータの格納場所を決めるようにします。
例えば、「100で割った時の余りの数字のアドレスにデータを格納する」というルールを作っておけば、「375」はアドレス75に格納されているとすぐに分かります。
このように、データをあるルールに沿って格納しておくことで、簡単にデータを探索する方法をハッシュ法と言います。

ハッシュ法
あるルールに沿って格納しておくことで、簡単にデータを探索する方法

ハッシュ法

ハッシュではあるルールに沿ってデータの格納場所を決定しますが、格納場所を決めるルールをハッシュ関数、ハッシュ関数を使って求めた値をハッシュ値や関数値と言います。

ハッシュ法を使えば、データがどこのアドレスに格納されているか一発で分かります。データを格納する配列がどれだけ大きくても一発で分かるので、配列の大きさとデータ検索に掛かる時間に関係性はありません。

しかし、問題点もあって、「100で割った時の余りの数字のアドレスにデータを格納する」というルールだと「275」と「375」は同じ場所に格納することになってしまいます。このように格納場所が重複してしまうことを衝突と言います。衝突を回避する方法もありますが、基本情報では問われないので無理に勉強する必要はありません。

（おまけ）衝突を回避する方法
①チェイン法
衝突は1つの格納場所に1つのデータしか格納出来ないから起こります。
それなら1つの格納場所に複数のデータを格納できるようにすればOKですよね。これがチェイン法です。

②オープンアドレス法
衝突が起きた時、別のルールで再度格納場所を決める方法がオープンアドレス法です。例えば、衝突が起きた時は「元のデータに1を足した値を100で割り、その余りの数字のアドレスにデータを格納する」とルールを決めておきます。オープンアドレス法で衝突の頻度を下げることが出来ます。

オープンアドレス法を使うとデータの探索が少し面倒になるというデメリットもあります。

基本情報技術者試験での出題例

サンプル問題問7、令和元年度秋期問10

基本情報技術者
科目A サンプル問題問7、午前試験令和元年度秋期問10

10進法で5桁の数 a₁a₂a₃a₄a₅ をハッシュ法を用いて配列に格納したい。ハッシュ関数を mod(a₁＋a₂＋a₃＋a₄＋a₅，13) とし，求めたハッシュ値に対応する位置の配列要素に格納する場合，54321は配列のどの位置に入るか。ここで，mod(x，13) は，xを13で割った余りとする。