ハッシュテーブルを使おう（オープンアドレス法） F#(Beta)編（paizaランク B 相当）

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

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

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

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

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

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

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

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

今回は前者の オープンアドレス法 を採用したハッシュテーブルを実装して、各クエリを処理してください。

ハッシュテーブルは要素数 1000 の配列とし、配列の各要素にはデータそのものを格納することとします。なお、各要素の初期値は -1 とします。

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

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

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

ハッシュ値が衝突した場合は、空いている添え字が見つかるまで H(p) ← (H(p) + 1) % mod による更新をおこなってください。

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

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

2 d
ハッシュテーブルにデータ d が格納されているかどうかを調べてください。
格納されているならデータ d がハッシュテーブルの先頭から何番目かを出力してください。
格納していないなら -1 と出力してください。
ただし、ハッシュテーブルの先頭のデータを 1 番目とします。