今回は「ハッシュ関数とは」の問題に挑戦！
問題概要
-
n個の整数と整数mod、 - 次の行に、
x_1, x_2, ..., x_nが与えられる。 - 各
x_iについて、以下のハッシュ関数を用いてハッシュ値を計算して出力する。
H(x) = x % mod
入力例:
5 7
3
9
12
15
17
出力例:
3
2
5
1
3
✅OK例：
const rl = require('readline').createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
const [n, mod] = lines[0].split(' ').map(Number);
const x = lines.slice(1).map(Number);
x.forEach(x => {
console.log(x % mod);
});
});
1️⃣ ハッシュ関数とは何か？
ハッシュ関数とは、データ (入力) に対して特定の計算をおこない、特定の範囲に収まる値 (固定長の出力) を得る関数。
かみ砕くと
どんなデータでも、決められた範囲の数値に変換する関数。
- 入力（キー）
- 数字・文字列・オブジェクトなど何でもOK
- 出力（値・ハッシュ値・ダイジェスト値）
- 「必ず同じサイズ・同じ範囲」に収まる数値
📌 重要なのは「情報を縮約する」関数だという点。
2️⃣ ハッシュ関数に期待される3つの性質
① 同じ入力 → 同じ出力
H(123) = 4
H(123) = 4 ← 必ず同じ
👉 これがないと「比較」や「検索」に使えない
② 出力から入力を推測しにくい
H(x) = 1234
この値だけ見ても、元の x が何かは分からない
📌 セキュリティ用途（パスワード）で超重要
③ 出力が一様に分布する
👉 特定の値に偏らず、まんべんなく散らばる
悪い例: 0 0 0 0 9 0 0
良い例: 1 7 3 9 4 2 8
3️⃣ ハッシュ関数の主な用途
① ハッシュテーブル
- 連想配列（Map / Object / Dictionary）の内部構造
- キー → 配列インデックスに変換
- キーを番号に変換して、配列として管理する仕組み
index = hash(key)
table[index] = value;
例 ）こんなオブジェクトがあったとする：
const score = {
"Alice": 95,
"Bob": 80,
"Charlie": 70
};
内部ではハッシュテーブルが使われていると仮定すると、
1.キー "Alice" をハッシュ関数に通す
index = hash("Alice") = 3
2.配列の番号 3 に値 95 を入れる
table[3] = 95
3.取り出すときも同じ
score["Alice"] → hash("Alice") → table[3] → 95
② オブジェクトの同一性判定
- 中身が同じかどうかをハッシュ値同士で比較
hash(A) === hash(B) → 同一の可能性が高い
📌 実体を全部比較しなくて済む
③ ダイジェスト認証（パスワード）
- パスワードそのものは送らない
- ハッシュ化した値だけを使う
password → hash(password)
👉 盗聴されても元のパスワードは分からない
4️⃣ この問題でやっていること
定義されているハッシュ関数
H(x) = x % mod
これは最も単純なハッシュ関数
- 入力: 任意の整数
x - 出力:
0 ～ mod-1
📌「配列サイズ mod に押し込む関数」
5️⃣ なぜ % mod がハッシュなのか？
x = 123456
mod = 100
H(x) = 56
- どんなに大きい数でも
- 決まった範囲に収まる
- 同じ
xなら必ず同じ結果
👉 ハッシュの最低条件を全部満たしている
📝まとめ
ハッシュ関数とは「データを決まった範囲の番号に変換する関数」