【科目B対策】ハッシュ法（ハッシュ探索）を擬似プログラミング言語で理解する

（科目Bの擬似言語）だと、「全コード」は (1) ハッシュ表を作る（格納） と (2) 探す（探索） の両方を含む形になります。

ハッシュ関数：x mod 10、ハッシュ表：配列 T[0..9]（空は EMPTY） として、衝突は“起きる”ところまで（解決法は試験範囲外になりやすい）を基本形にします。

1) 科目B向け：衝突解決なし（最小構成の全コード）

「衝突が起きたら格納失敗」とする、いちばんシンプルな形です。

// 定数
EMPTY ← -1

// ハッシュ関数
function Hash(x)
  return x mod 10
endfunction

// ハッシュ表の初期化
procedure InitTable(T)
  for i ← 0 to 9
    T[i] ← EMPTY
  endfor
endprocedure

// 格納（衝突解決なし）
function Insert(T, x)
  h ← Hash(x)
  if T[h] = EMPTY then
    T[h] ← x
    return true
  else
    // 衝突（コリジョン）
    return false
  endif
endfunction

// 探索
function Search(T, key)
  h ← Hash(key)
  if T[h] = key then
    return true
  else
    return false
  endif
endfunction

// メイン例（教科書データ）
procedure Main()
  declare T[0..9]

  InitTable(T)

  Insert(T, 32)
  Insert(T, 78)
  Insert(T, 51)

  print Search(T, 32)   // true
  print Search(T, 49)   // false（格納していない想定）
endprocedure

このコードで、科目B的に重要なポイントはこれです。

• h ← key mod 10 が 格納場所（要素番号） を決める
• 探索は 1回のアクセス＋1回の比較（速い理由）
• 弱点は Insert の else にある 衝突

2) 参考：衝突を解決する全コード（線形探索＝線形プロービング）

科目Bでは「衝突が起きる」は問われやすい一方、解決法の詳細は深追いされにくいです

（空きが見つかるまで 次の場所へずらして格納）

EMPTY ← -1

function Hash(x)
  return x mod 10
endfunction

procedure InitTable(T)
  for i ← 0 to 9
    T[i] ← EMPTY
  endfor
endprocedure

// 格納（線形プロービング）
function Insert(T, x)
  h ← Hash(x)

  for k ← 0 to 9
    idx ← (h + k) mod 10
    if T[idx] = EMPTY then
      T[idx] ← x
      return true
    endif
  endfor

  // 表が満杯
  return false
endfunction

// 探索（線形プロービング）
function Search(T, key)
  h ← Hash(key)

  for k ← 0 to 9
    idx ← (h + k) mod 10

    if T[idx] = EMPTY then
      // 途中で空が出たら、これ以上先には存在しない
      return false
    endif

    if T[idx] = key then
      return true
    endif
  endfor

  return false
endfunction

procedure Main()
  declare T[0..9]

  InitTable(T)

  Insert(T, 32)   // 2
  Insert(T, 42)   // 2で衝突 → 3へ
  Insert(T, 78)   // 8
  Insert(T, 51)   // 1

  print Search(T, 42)   // true
  print Search(T, 49)   // false
endprocedure

どっちを「科目Bの全コード」として覚えるべき？

• 試験の本筋（速い理由・衝突が起きる）に絞るなら → 1) 衝突解決なし
• 授業で「衝突したらどうする？」まで見せたいなら → 2) 線形プロービング