基本情報 令和6年度 科目A 問2：テクノロジ系に関する問題

答えは d（dとx） です。

ハッシュ表＝引き出しが10個あるロッカー。各文字（a〜z）にはASCIIという番号が付いていて、その番号の1の位で「何番ロッカーに入れる？」を決めます。同じロッカーに2人入っちゃうのが「衝突」。

• a=97（1の位7）、i=105（5）→違う
• b=98（8）、r=114（4）→違う
• c=99（9）、l=108（8）→違う
• d=100（0）、x=120（0）→同じ！ 衝突！

👉 覚え方：a=97から順に+1ずつ。dは100番、xは120番、どっちも0で終わる。

ひと言：ASCIIの並びは辞書順なので a=97、b=98、c=99…で数えれば暗算でいける。

なぜこれが正解か

正解は d。小文字アルファベットのASCII（10進）は a=97から始まり連続：

| 文字 | ASCII | 1の位 |

|------|-------|------|

| a | 97 | 7 |

| b | 98 | 8 |

| c | 99 | 9 |

| d | 100 | 0 |

| i | 105 | 5 |

| l | 108 | 8 |

| r | 114 | 4 |

| x | 120 | 0 |

衝突＝ハッシュ値が一致すること。dとxの1の位がともに0で衝突。

各選択肢の解説

• a（a=7, i=5）：不一致。
• b（b=8, r=4）：不一致。
• c（c=9, l=8）：不一致。
• d（d=0, x=0）：一致 → 衝突。

覚え方・ひっかけ注意

a=97の暗記が最大の鍵（大文字A=65、数字0=48と合わせて3点暗記）。アルファベットの連番性から d=100、x=120 などキリの良い数値も導きやすい。衝突回避策（チェイン法・オープンアドレス法）と合わせて出題されるので、ハッシュ関数の良し悪し＝衝突率の低さと理解しておく。

理論的背景・仕組みの詳細

ハッシュ法はキーをハッシュ関数で整数化し、配列添字としてO(1)平均探索を実現するデータ構造。本問のように「ASCIIの下位桁を取る」は mod 演算（mod 10）と等価で、極めて単純なハッシュ関数。良いハッシュ関数の条件は (1) 計算が高速、(2) 均等分散（衝突が起こりにくい）、(3) 雪崩効果（入力の小変化で大きく変わる）。本問の関数は連続整数キー（a〜z＝97〜122）に対して規則的衝突を生むため、実用上は劣悪。

実務での使われ方・関連規格/法令

汎用ハッシュは MurmurHash3、xxHash、FNV-1a が高速で広く使われる。暗号学的用途には SHA-2、SHA-3、BLAKE3。ハッシュテーブルの実装ではJavaのHashMap（赤黒木フォールバック）、Pythonのdict（オープンアドレス＋オープン探索）、Rustのhashbrown（SwissTable・SIMD最適化）が代表例。Hash DoS攻撃対策として SipHash や乱数seedを毎起動変えるテクニックが標準化（PythonのPYTHONHASHSEED、RubyのHash randomization）。データベース系ではコンシステントハッシュ（Cassandra、DynamoDB、CDN）が水平分散の基盤。

試験での位置づけ

FE科目Aのデータ構造・アルゴリズム領域で毎回1〜2問出題。本問のようなハッシュ衝突計算、チェイン法/オープンアドレス法の格納手順、平均探索回数の計算が定番。応用情報技術者ではBツリーとの比較、Bloomフィルタの誤判定確率、整数mod素数を選ぶ理由（合成数だと周期的衝突）まで踏み込む。データベーススペシャリストではハッシュインデックスとB+木インデックスの使い分けが出題。

選択肢の発展補足

衝突解決法は2系統：(1) チェイン法（オープンハッシュ）＝同じハッシュ値を連結リストで保持、最悪O(n)だが実装簡単。(2) オープンアドレス法＝衝突時に別スロットへ→線形探索（プライマリクラスタリング発生）、二次探索、ダブルハッシュなど。負荷係数（load factor）は 0.7〜0.75 でリハッシュするのが定石（Java HashMapは0.75）。本問の関数は{a=7, k=7, u=7}のように10刻みで衝突するため、実用ではASCII全32文字をビット混合する関数に改善すべき。なお、近年のC++26やJavaのValhalla計画でvalue typesとidentity-less hashの議論が進んでおり、ハッシュ設計はモダン言語設計の最前線でもある。