ハッシュテーブルの衝突 Scala編（paizaランク B 相当）

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

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

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

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

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

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

ハッシュ関数が異なると、衝突の起こりやすさも異なります。使用するデータに適したハッシュ関数を用いることが大切です。本問では、2 つのハッシュ関数を扱います。与えられるデータに対してどちらのハッシュ関数が適しているのか考えてみましょう。

日付を表す 8 桁の整数 d_1, d_2, ..., d_N が与えられます。以下の 2 種類のハッシュ関数 H1 と H2 を用いて得たハッシュ値を添え字としてそれぞれのハッシュテーブルに格納するとき、別の入力から得た値が既に添え字となっていた回数、つまりそれぞれの衝突する回数を出力してください。

H1(d_i) = d_i % 10000

H2(d_i) = d_i // 10000

ただし、% は剰余を計算する演算子、// は切り捨て除算をおこなう演算子を表しています。