ハッシュテーブルを使おう

今回は paiza の「ハッシュテーブルを使おう」の問題に挑戦！

問題概要

🔹やること
チェイン法でハッシュテーブルを実装し、

• データの 挿入
• データの 検索
• 最後にテーブルの中身を出力
  を行う。

🔹ハッシュテーブル仕様

• 要素数：100
• 各要素：リスト（配列）
• 初期値：すべて空配列 []
• 衝突対策：チェイン法
  • 衝突した場合、同じインデックスの配列に追加

🔹ハッシュ関数

H(x) = (a * x + b) % 100

• 入力で a と b が与えられる
• 出力は 0〜99 の整数
• この値が 格納場所（添字）

🔹クエリの種類

① 1 x

• x をハッシュテーブルに追加する

② 2 x

• x がハッシュテーブルに存在するか調べる
• 出力：
  • あれば "Yes"
  • なければ "No"

🔹最終出力

• 全クエリ処理後
• ハッシュテーブルの状態を0〜99まで100行出力
• 各行にその添字のリストの中身を
  • スペース区切りで表示
  • 空なら空行

✅OK例：

const rl = require('readline').createInterface({ input: process.stdin });

const lines = [];
rl.on('line', line => lines.push(line));

rl.on('close', () => {
    const [a, b] = lines[0].split(' ').map(Number);
    const q = Number(lines[1]);
    const k = lines.slice(2).map(k => k.split(' ').map(Number));
    
    const table = Array.from({ length: 100 }, () => []);
    
    function H(x) {
        return (a * x + b) % 100;
    }
    
    for (let i = 0; i < q; i++) {
        const [num, x] = k[i];
        const index = H(x);
        
        if (num === 1) {
            table[index].push(x);
        } else {
            if (table[index].includes(x)) {
                console.log('Yes');
            } else {
                console.log('No');
            }
        }
    }
    
    table.forEach(t => console.log(t.join(' ')));
});

🔍コードの流れ

🔹① 入力の準備

• readline で標準入力を受け取る
• 入力された行を lines 配列に順番に保存
• 入力が終わったら処理を開始

🔹② 初期設定

• 1行目から a と b を取得（ハッシュ関数用）
• 2行目からクエリ数 q を取得
• 3行目以降をクエリ配列 k として取得
• 要素数100の配列 table を作る（各要素は空配列）

🔹③ ハッシュ関数の定義

• H(x) = (a * x + b) % 100
• 整数 x を 0〜99 のインデックスに変換する

🔹④ クエリ処理（q回繰り返し）

各クエリについて：

1. クエリ内容を [num, x] に分解
2. index = H(x) で格納場所を決定

• num === 1（挿入）
  • table[index] に x を追加（push）
• num === 2（検索）
  • table[index] に x が含まれているか確認
  • あれば "Yes"、なければ "No" を出力

🔹⑤ 最後にハッシュテーブルの状態を出力

• 0番から99番まで順番に
• 各バケットの中身をスペース区切りで出力
• 空なら空行を出力
  
  
  
  
  
  

📝まとめ

• ハッシュテーブルでは、データ x があるかどうかを調べるためにテーブル全体を探索する必要はない。
• なぜなら、ハッシュ関数は「同じ入力に対して必ず同じ出力」を返すからである。
• そのため、データ x は必ず添字 H(x) の場所に格納される。
• よって、検索時は H(x) のリストだけを確認すればよい。