ハッシュテーブル(オープンアドレス法) (paizaランク C 相当)

データのハッシュ値を添字として用い、データを表に格納するデータ構造をハッシュテーブルと呼びます。このデータ構造には、データの挿入や検索が O(1) でおこなえるという利点があります。

ハッシュテーブルの最もシンプルな実装は、以下のようなものです。

・ 前準備
ハッシュ関数と、配列を用意する (ハッシュ関数の出力の範囲が、配列の添字の範囲に収まるように)

・ データの挿入
データのハッシュ値を計算し、その値を添字として配列にデータを格納する

・ データの検索
データのハッシュ値を計算し、その添字の位置にデータがあるかどうかを調べる

ただし、データを格納する際にはハッシュの衝突に気をつける必要があります。衝突とは、異なるデータに対して同じハッシュ値が出力されることを指します。衝突への対処については、大きく分けて2つの方法があります。

・ オープンアドレス法
    衝突が解消されるまで、ハッシュ値を再計算する

・ チェイン法
    配列の要素をデータそのものではなくデータのリストとする。衝突した複数のデータを同じ場所に格納する

この問題では、前者の オープンアドレス法 を採用し、ハッシュテーブルを実装してみましょう。

n 個の整数 x_1, x_2, ..., x_n が順に与えられます。ハッシュ関数 H(x) = x % 10 を用いて、この n 個の整数をハッシュテーブルに格納してください。ハッシュテーブルは要素数 10 の配列とし、配列の各要素にはデータそのものを格納することとします。なお、各要素の初期値は -1 とします。ハッシュ値が衝突した場合は、空いている添字が見つかるまで H(x) ← (H(x) + 1) % 10 による再計算をおこなってください。最後に、ハッシュテーブルの状態を出力してください。

入力例 1 を用いて説明します。
最初に格納するデータは 17 です。このデータのハッシュ値は 17 % 10 = 7 ですから、配列の添字 7 の位置にデータを格納しようとします。添字 7 の位置にはまだいずれのデータも格納されていないので、ここにデータ 17 を格納します。
次に格納するデータは 188 で、ハッシュ値は 8 となります。添字 8 の位置にはまだいずれのデータも格納されていないので、ここにデータ 188 を格納します。
次に格納するデータは 38 で、ハッシュ値は 8 となります。添字 8 の位置にはすでにデータ 188 が格納されているため、データ 38 をこの位置に格納することはできません。従って、H(x) ← (H(x) + 1) % 10 を用いてハッシュ値を再計算します。すると、(8 + 1) % 10 = 9 となります。添字 9 の位置にはまだいずれのデータも格納されていないので、ここにデータ 38 を格納します。
次のデータ 77777 は、ハッシュ値が 7 となりますが、添字 7 の位置にはすでにデータ 17 が格納されています。H(x) ← (H(x) + 1) % 10 を用いて再計算すると 8 となりますが、添字 8 の位置にもすでにデータ 188 が格納されています。そこでさらに再計算すると 9 となりますが、この位置にもデータ 38 が格納されています。さらに再計算すると 0 となり、添字 0 の位置にはまだいずれのデータも格納されていないためここにデータ 77777 を格納します。

以上で全データの格納が終了しました。最終的なハッシュテーブルの状態は、77777, -1, -1, -1, -1, -1, -1, 17, 188, 38 となります。出力の際は、先頭から 1 要素ずつ改行区切りで、計 10 行で以下のように出力してください。

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