ハッシュテーブルを使おう（チェイン法） Java編（paizaランク B 相当）

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

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

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

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

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

ただし、データを格納する際にはハッシュの衝突に気をつける必要があります。衝突への対処については、大きく分けて2つの方法があります。

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

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

今回は後者の チェイン法 を採用したハッシュテーブルを実装して、各クエリを処理してください。

ハッシュテーブルは要素数 100 の配列とし、配列の各要素にはデータのリストを格納することとします。なお、各要素の初期値は空リストとします。各リストには複数のデータが含まれる可能性がありますが、格納された順番にデータが並ぶように実装してください。

ハッシュ関数 H は、入力で与えられるデータ d の長さを m として、

H(p) = (d の 1 文字目の文字コード * B1 + d の 2 文字目の文字コード * B2 + ... + d の m 文字目の文字コード * Bm) % mod

ただし、B = 7, mod = 100 とし、文字コードは ASCII に従って変換してください。

クエリは以下の形式で入力されます。

1 d
ハッシュテーブルにデータ d を格納してください。

2 x
ハッシュテーブルの先頭から x 番目 (1 ≦ x ≦ 100) に格納されているデータを左から格納された順番に全て出力してください。
格納されているデータが 1 つもない場合は -1 を出力してください。
ハッシュテーブルの添え字と x に 1 の差があることに注意してください。

3 d
ハッシュテーブルのデータ d を削除してください。