1. paizaラーニングトップ
  2. レベルアップ問題集
  3. ハッシュメニュー(言語選択)
  4. 問題一覧
  5. ハッシュ関数とは

ハッシュメニューのサムネイル
ハッシュ関数とは (paizaランク D 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

(はじめに)
この問題集では、ハッシュ関数について扱います。

ハッシュ関数とは、データ (入力) に対して特定の計算をおこない、特定の範囲に収まる値 (固定長の出力) を得る関数のことを指します。このとき、入力のことを キー 、出力のことを 値・ハッシュ値・ダイジェスト値 などと呼びます。

ハッシュ関数は、以下の性質を持っていることが期待されます。

・ 同じ入力に対して、常に同じ出力を返す
・ 出力から入力を推測することが難しい
・ 出力が一様に分布している (出力値に偏りがない)


ハッシュ関数は、例えば以下の用途で使われています。

・ ハッシュテーブル
連想配列の内部で用いられているデータ構造で、最もシンプルなハッシュの応用例です。この問題集の最後で、実際に実装します。

・ オブジェクトの同一性判定
一部のプログラミング言語では、オブジェクトの同一性判定にハッシュが用いられています。オブジェクトを入力にとるハッシュ関数を用いて、2つのオブジェクトのハッシュ値を比較することによってオブジェクトが等しいかどうかを判定します。

・ ダイジェスト認証
Webアプリなどにおいて、ユーザIDやパスワードをそのままの形で送信してしまうと、通信を盗聴した第三者に情報が漏れてしまう可能性があります。そこで、これらの情報をそのまま送信する代わりに、これらの情報に対応するハッシュ値を送信するという手法がとられます。そうすれば、仮に通信が盗聴されたとしても、元のパスワードなどが第三者に知られることは(理論上は)無くなります。


では、ハッシュ関数の性質と応用例がわかったところで、実際にハッシュ値を計算してみましょう。

n 個の整数 x_1, x_2, ..., x_n と、整数 mod が与えられます。各 x_i について、以下のハッシュ関数を用いてハッシュ値を計算してください。

H(x) = x % mod

入力される値

n mod
x_1
x_2
...
x_n


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

n 行出力してください。i (1 ≦ i ≦ n) 行目には、x_i のハッシュ値 H(x_i) を出力してください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

H(x_1)
H(x_2)
...
H(x_n)

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 入力値はすべて整数
・ 1 ≦ n ≦ 100
・ 2 ≦ mod ≦ 10,000
・ 1 ≦ x_i ≦ 10,000 (1 ≦ i ≦ n)

入力例1

5 7
3
9
12
15
17

出力例1

3
2
5
1
3

問題一覧へ戻る

ページの先頭へ戻る