ハッシュテーブル(オープンアドレス法)

今回は paiza の「ハッシュテーブル(オープンアドレス法)」の問題に挑戦！

問題概要

• 目的
  • ハッシュ関数を使って
  • ハッシュテーブル（配列）にデータを格納する仕組みを実装する
• ハッシュ関数
  • H(x) = x % 10
• ハッシュテーブル
  • 要素数 10 の配列
  • 初期値はすべて -1
• データの格納方法
  • x % 10 を添字として配列に格納
  • もしすでに埋まっていたら衝突
    • (hash + 1) % 10 で次の場所を探す（オープンアドレス法）
• 最終出力
  • 全データを格納し終わったあとの配列の中身を
  • 添字 0 ～ 9 の順で出力

入力例:

4
17
188
38
77777

出力例:

77777
-1
-1
-1
-1
-1
-1
17
188
38

✅OK例：

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

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

rl.on('close', () => {
    const n = Number(lines[0]);
    const x = lines.slice(1).map(Number);
    
    const table = Array(10).fill(-1);
    
    function H(x) {
        return x % 10;
    }
    
    for (let i = 0; i < n; i++) {
        let hash = H(x[i]);
        
        if (table[hash] === -1) {
            table[hash] = x[i];
        }
        else {
            while (true) {
                hash = H(hash+1);
                if (table[hash] === -1) {
                    table[hash] = x[i];
                    break;
                }
            }
        }
    }
    
    table.forEach(t => console.log(t));
});

🔍コードの流れ

準備

• 入力を読み込む
• 要素数 10、初期値 -1 の配列を用意

データの挿入（ループ）

• 各 x_i について：
  • hash = x_i % 10 を計算
  • その添字が -1 なら、そのまま格納
  • すでに値が入っていたら：
    • (hash + 1) % 10 で次の添字へ
    • 空いている場所が見つかるまで繰り返す
    • 見つかったら格納して終了

出力

• 最後に配列の中身を、添字 0 ～ 9 の順に1行ずつ出力
  
  
  
  
  
  

📝まとめ

〇 衝突とは

17 % 10 = 7
77777 % 10 = 7

→ 同じ添字 7 を使おうとしてぶつかること

〇 オープンアドレス法（今回の方法）

• 衝突したら

(hash + 1) % 10

で次の添字を試す

• それでもダメならさらに次へ
• 空いている場所が見つかるまで探す