ハッシュ関数を作ってみよう

今回は paiza の「ハッシュ関数を作ってみよう」の問題に挑戦！

問題概要

• 目的
  • 文字列を入力として
  • 0 以上 100 未満の整数を返す
  • オリジナルのハッシュ関数を作る
• 入力
  • 1行目：文字列の個数 n
  • 2行目以降：英小文字のみの文字列 s_1 ～ s_n
    • 長さは 1〜10 文字
• 出力
  • 各文字列に対するハッシュ値を 1 行ずつ出力
  • 値は必ず 0～99

入力例：

5
abc
bca
cab
aaa
abc

出力例：

14
11
11
6
14

✅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 s = lines.slice(1);
    
    const ans = [];
    
    for (let i = 0; i < n; i++) {
        const str = s[i];
        let hash = 0;
        
        for (let j = 0; j < str.length; j++) {
            hash += str.charCodeAt(j) - 96;
        }
        
        hash %= 100;
        ans.push(hash);
    }
    
    ans.forEach(a => console.log(a));
});

🔍コードの流れ

• 入力をすべて読み込む
• 各文字列について以下を実行：
  • ハッシュ値を 0 で初期化
  • 文字列を1文字ずつ見る
  • 各文字を数値（charCodeAt - 96）に変換して加算（1~26）
  • 合計値を 100 で割った余りにする
• 計算したハッシュ値を順番に出力

📝まとめ

① 同じ入力 → 同じ出力

• 毎回同じ計算をする必要がある
• ランダムは禁止

② 出力から入力を推測しにくい

• 文字列の長さだけ返す、はダメ寄り
• 文字の中身を使う方がよい

③ 出力が一様に分布する

• 全部 0 や同じ値に寄らない
• % 100 で範囲を固定するのが定石

今回作ったハッシュ関数

• 各文字を、a=1, b=2, …, z=26という数値に変換
• それらをすべて足し合わせる
• 最後に % 100 して 0〜99 に収める