ハッシュテーブル(チェイン法) (paizaランク C 相当)

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

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

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

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

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

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

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

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

この問題では、後者の チェイン法 を採用し、ハッシュテーブルを実装してみましょう。

n 個の整数 x_1, x_2, ..., x_n が順に与えられます。ハッシュ関数 H(x) = x % 10 を用いて、この n 個の整数をハッシュテーブルに格納してください。ハッシュテーブルは要素数 10 の配列とし、配列の各要素にはデータのリストを格納することとします。なお、各要素の初期値は空リストとします。各リストには複数のデータが含まれる可能性がありますが、格納した順番にデータが並ぶように実装してください。最後に、ハッシュテーブルの状態を出力してください。

入力例 1 を用いて説明します。
最初に格納するデータは 17 です。このデータのハッシュ値は 17 % 10 = 7 ですから、配列の添字 7 の位置にあるリストにデータ 17 を格納します。リストは [17] となります。
次に格納するデータは 188 で、ハッシュ値は 8 となるので、添字 8 の位置にあるリストにデータ 188 を格納します。リストは [188] となります。
次に格納するデータは 38 で、ハッシュ値は 8 となるので、添字 8 の位置にあるリストにデータ 38 を格納します。リストは [188, 38] となります。
次に格納するデータは 77777 で、ハッシュ値は 7 となるので、添字 7 の位置にあるリストにデータ 77777 を格納します。リストは [17, 77777] となります。

以上で全データの格納が終了しました。最終的なハッシュテーブルの状態は、

[]
[]
[]
[]
[]
[]
[]
[17, 77777]
[188, 38]
[]

となります。