平成23年度特別 プロジェクトマネージャ 午前Ⅰ 問3

ハッシュ衝突条件を整理する視点

この問題では、用語をそのまま暗記して判断せず、比較している対象、成立条件、適用される範囲の三つに分けて読み取りましょう。それぞれの関係を整理し、文中の条件と対応づけて確認することが大切です。

この問題で問われていること

確認する観点を、用語の定義そのものではなく、問題文が示す二つの対象の関係と、条件がどの段階で成立するかの対応づけに絞りましょう。主語と比較対象を丁寧に読み、条件の結びつきを一つずつ確認してください。

視点

ハッシュに関する用語を読むときは、対象・条件・範囲を分け、文中でそれらがどのように結びついているかを整理します。似た表現の印象ではなく、条件の対応関係に注目しましょう。

確認ポイント

• 比較している対象が何かを、問題文の記号や説明に沿って書き分ける
• 条件が成立する場面と、前提として置かれている範囲を対応づける
• 似た用語や条件を混同していないか、文中の主語と関係を見直す

正解

エ

解説

小文字アルファベットのASCIIコードはアルファベット順に1ずつ増加します。各コードの10進表記の1の位を比較すると、dとxはいずれもハッシュ値が0となり、同じ格納位置を指すため衝突します。

理由

小文字のASCIIコードはaからzまでアルファベット順に連続して割り当てられています。ハッシュ値はその10進表記の1の位なので、異なる文字でも末位が同じなら同じハッシュ値となり、ハッシュ表で衝突します。

比較

dのASCIIコードは100で、1の位は0です。xのASCIIコードは120で、こちらも1の位は0です。したがって両者のハッシュ値は一致します。一方、他の組合せではASCIIコードの1の位が一致しません。

選択肢ア

これは不正解だよ。aのASCIIコードは97で、ハッシュ値は1の位の7です。iのASCIIコードは105で、ハッシュ値は5です。7と5は異なるため、同じハッシュ値にならず、この組合せでは衝突は起こりません。

選択肢イ

これは不正解だよ。bのASCIIコードは98なのでハッシュ値は8です。rのASCIIコードは114なのでハッシュ値は4です。両者の1の位が異なり、ハッシュ値も一致しないため、衝突する組合せではありません。

選択肢ウ

これは不正解だよ。cのASCIIコードは99で、ハッシュ値は9です。lのASCIIコードは108で、ハッシュ値は8です。末位が9と8で異なるため、異なる表位置に対応し、衝突は起こりません。

選択肢エ（正解）

これは正解だよ。dのASCIIコードは100でハッシュ値は0、xのASCIIコードは120でハッシュ値も0です。異なるキーが同じハッシュ値になるため、ハッシュ表への格納時に衝突が起こります。

学習のポイント

ASCIIコードの連続性と、10進表記の1の位によるハッシュ値の比較方法を理解しましょう。