科目Bのハッシュ表問題の解き方｜格納位置と衝突を表で追う

余りを計算するところまでは分かる。でも、ぶつかった値がどこへ行くのかで迷う。

科目Bでハッシュ表のコードを見て、格納される位置が分からなくなったことはありませんか？

値ごとに余りを計算し、ぶつかったら隣へずらし、表の端まで来たら先頭へ戻る。値が増えるたびに表の中身が変わるので、途中でどこまで埋まったのかを見失ってしまう人も多いのではないでしょうか。

大丈夫です。ハッシュ表の問題の多くは、1つの値を入れるたびに表を1行書き足していけば、確実に解けるように作られています。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。ハッシュ表を一から自分で作ることはまずありませんが、キーから値を取り出す連想配列やキャッシュの仕組みは、ほとんど毎日のように使っています。

以前、キャッシュのキーの作り方が偏っていて、特定のデータだけ取り出しが極端に遅くなったことがありました。原因は、多くのキーが同じ場所に集まっていたことで、キーごとの格納先を表に書き出してようやく気づけました。

この記事では、ハッシュ表の問題を、科目Bの解き方に合わせて5つの段階で紹介します。科目B全体の中で、こうしたアルゴリズムの問題がどんな位置にあるのかを先に確かめたい人は、親記事から読んでおくと流れがつかみやすくなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

ハッシュ表の問題は何を聞いているのか¶

最初に、ハッシュ表とは何かを短く押さえておきましょう。ハッシュ表とは、値そのものから格納する位置を計算して、配列に値を置いておく仕組みのことです。

位置を計算する式をハッシュ関数と呼びます。科目Bでは、値を表の大きさで割った余りに1を足す形がよく使われます。

ところが、違う値なのに同じ位置が計算されることがあります。これを衝突と呼び、衝突したときにどこへ置くかを決める処理が、問題の中心になります。

ハッシュ探索がなぜ速いのか、仕組みそのものを先に理解しておきたい人は、こちらの記事から読むと安心です。

【関連記事】擬似言語のハッシュ探索とは？線形探索より速くなる仕組みを解説

設問のパターンを表で整理する¶

ハッシュ表の設問は、聞かれ方がいくつかの型に分かれます。どの型なのかを最初に見極めると、追うべきものがはっきりします。

この記事では、出題されやすい格納後の状態と衝突の回数を中心に追います。探索の結果を問う型は、前の記事で扱った探索の流れと同じ考え方で解けます。

オープンアドレス法とチェイン法の違い¶

衝突の処理には、大きく分けて2つの方式があります。科目Bでは片方だけが出ることが多いので、問題文がどちらを使っているかを最初に確かめてください。

オープンアドレス法のうち、隣の位置を順に調べていく方式を線形探査法と呼びます。この記事の例題は、この線形探査法で書いています。

チェイン法の問題では、同じ位置にぶら下がる値を、連結リストの次の要素をたどる形で追います。連結リストのたどり方に不安がある場合は、こちらの記事も役に立ちます。

【関連記事】科目Bの連結リスト問題の解き方｜nextを図にして追う

まず目を付ける場所¶

ハッシュ表の考え方がつかめたら、次はコードのどこから読むかを決めます。この問題で目を付ける場所は3つです。

ひとつ目はハッシュ関数の式、ふたつ目は衝突したときに次の位置を決める式、みっつ目は値を入れる順番です。この3か所が決まれば、あとは機械的に表を埋めるだけです。

ハッシュ関数の式は何で割っているか¶

最初に確かめたいのが、何で割った余りを使っているかと、そこに1を足しているかどうかです。擬似言語の配列は要素番号が1から始まることが多いので、余りの0から始まる値を1つずらす必要があるからです。

余りの計算そのものに自信がない場合は、先に文法の記事で確かめておくと迷いません。

【関連記事】擬似言語の余り（剰余）と割り算がわからない人へ｜偶数判定と桁の取り出しを解説

次の位置の式は表の端で折り返すか¶

次に見るのが、衝突したときに idx を進める行です。単純に1を足すだけだと、表の最後の位置から先へはみ出してしまいます。

そのため、表の大きさで割った余りに1を足して、最後の位置の次を先頭に戻す書き方がよく使われます。表の最後の位置を代入して、先頭の1が返ってくるかを確かめてください。

値を入れる順番を必ずメモする¶

最後に見るのが、どの値をどの順番で入れるかです。オープンアドレス法では、先に入った値が場所を取るので、同じ値の集まりでも入れる順番が違うと表の中身が変わります。

問題文に並んでいる値を、入れる順に番号を振ってメモしておきましょう。トレース表もこの順番どおりに書いていきます。

例題：線形探査法で値を格納し衝突の回数を返す¶

ここからは、実際の例題で追い方を確かめます。この記事の例題は説明のために作成したもので、IPA の公開問題そのものではありません。

次のプログラムは、要素数10の大域変数の配列 table に値 key を格納し、衝突した回数を返す関数です。table の要素番号は1から始まり、最初はすべての要素に0が入っています。表に空きがある場合だけ呼び出すものとします。

大域: 整数型の配列: table ← {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

○整数型: hashInsert(整数型: key)
  整数型: idx, count
  idx ← (key mod 10) ＋ 1
  count ← 0
  while (table[idx] が 0 と等しくない)
    count ← count ＋ 1
    idx ← (idx mod 10) ＋ 1
  endwhile
  table[idx] ← key
  return count

hashInsert は、まず10で割った余りに1を足して、最初に見る位置を決めます。その位置が埋まっていれば、衝突の回数を1つ増やして隣へ進み、空きが見つかったところに値を置きます。

では、23、41、13、50、33、39、19 の順に hashInsert を呼び出したとき、最後の 19 の戻り値と、19 が格納される位置はどうなるでしょうか？

トレース表で格納位置と衝突を追う¶

頭の中だけで7つの値を入れていくと、どの位置が埋まっているのかが分からなくなりがちです。そこで、値を1つ入れるごとに、最初に見る位置、調べた位置の順、格納した位置、戻り値をトレース表に書きます。

ポイントは、調べた位置を矢印でつないで全部書くことです。衝突の回数は、矢印の数と同じになります。

最後の行が問いの答えです。19 は3回衝突し、位置3に格納されるので、戻り値は3になります。

7行目を見てください。位置10が埋まっていたので、次の位置は (10 mod 10) ＋ 1 で1に戻っています。表の端で折り返したあと、50 と 41 にもぶつかり、ようやく空いていた位置3にたどり着きました。

すべて入れ終わったときの表の中身も、確かめておきましょう。

位置1から6までと位置10が、すき間なく埋まっています。このように線形探査法では値が固まりやすく、固まりの近くに来た値ほど遠くまで押し出されます。

トレース表の書き方そのものに慣れていない場合は、こちらの記事で基本から確認できます。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

入れる順番を変えると結果も変わる¶

同じ7つの値でも、19 を最初に入れていたらどうなるでしょうか。19 は衝突せずに位置10に入り、あとから来た 39 が位置10、1、2とぶつかって位置3まで押し出されます。

変わるのは位置3と位置10の値だけですが、選択肢ではこの小さな違いがそのまま別の答えになります。似た表が並んでいるときは、入れる順番を問題文と照らし合わせることが大切です。

探索の設問にも同じ表が使える¶

格納のあとに、ある値を探す設問が続くこともあります。探索でも、最初に見る位置と次の位置の式は格納と同じです。

たとえば、この表で 29 を探すと、位置10から 1、2、3、4、5、6 と進み、空いている位置7に当たって見つからないと分かります。見つからない場合の探索の流れは、探索問題の記事でも詳しく扱っています。

【関連記事】科目Bの探索問題の解き方｜線形探索と二分探索の見分け方

間違いやすい選択肢の見分け方¶

ハッシュ表の問題では、式の一部や数え方を少しだけずらした選択肢が並びます。どんな誤りが用意されやすいのかを知っておけば、選択肢を見た瞬間に候補を絞れます。

例題の 19 を使って、よくある誤りを表にまとめました。

1行目の誤りは、余りの値をそのまま要素番号に使ってしまうことで起きます。50 のように割り切れる値を代入すると、位置0という存在しない番号が出てくるので見分けられます。

3行目の位置7は、表の空きだけを見ると自然な答えに見えます。それでも、線形探査法は最初に見る位置から順に進む方式なので、位置10から始めて折り返す流れを外れた答えは正解になりません。

衝突の回数は矢印の数で数える¶

4行目のように、衝突の回数を1つ多く数えてしまう誤りはとても多いです。count が増えるのは、while の中、つまり位置が埋まっていたときだけです。

トレース表で、調べた位置を矢印でつないでおけば、矢印の数がそのまま衝突の回数になります。19 なら矢印は3本なので、戻り値は3です。

空欄の式は表の最後の位置で試す¶

次の位置の式が空欄になっているときは、表の最後の位置を代入してみるのが近道です。例題なら idx に10を入れて、1が出てくる式が正解です。

idx ＋ 1 なら11、idx mod 10 なら0になってしまいます。どちらも要素番号の範囲から外れるので、候補から外せます。

Giji Academy のシミュレーターで動かす¶

紙のトレース表で動きをつかんだら、最後は実際に動かして確かめましょう。値が増えるたびに表の中身が変わる処理ほど、動かして見る効果は大きくなります。

Giji Academy の擬似言語シミュレーターでは、擬似言語のコードを1行ずつ実行し、変数や配列の値が変わる様子を目で確かめられます。自分で書いたトレース表と見比べながら進めると、どの値で予想とずれたのかがすぐに分かります。

試すときは、まず例題の7つの値を順に入れて、19 が位置10から1へ折り返す瞬間を確かめてください。そのあと次の位置の式を idx ＋ 1 に書き換えて、範囲の外を見に行こうとする様子を見ると、折り返しの式の意味が体で分かります。

慣れてきたら、入れる順番を入れ替えて、表の中身がどう変わるかを試してみましょう。表の大きさを10から11に変えて、値の散らばり方を比べてみるのもおすすめです。

まずはGiji Academy の擬似言語シミュレーターで講座を選び、値が計算された位置に入り、ぶつかって隣へずれていく流れを確かめてみてください。

まとめ¶

科目Bのハッシュ表の問題は、特別な知識を問うものではありません。余りで最初の位置を決め、埋まっていたら決まった規則で隣へ進む、という手順を表に書いて追えば、落ち着いて解けます。

この記事でお伝えした5つの段階を振り返っておきましょう。

最初は、表の大きさが10くらいで、値が5つ前後の小さな問題で十分です。何度か表を書くうちに、余りを見ただけで、どこに固まりができるのかが分かるようになります。

調べた位置は矢印でつないで全部書く。次の位置の式は表の最後の位置で試す。 この2つを習慣にしておけば、ハッシュ表の問題にも自信を持って向き合えます。次にハッシュ関数を見かけたら、まずは表の端で何が起きるかから確かめてみてください。