【ハッシュメニュー】ハッシュテーブル(オープンアドレス法) (paizaランク C)-解答例-PHP編

2022年7月20日

【ハッシュメニュー】> 【ハッシュテーブルを使おう】STEP: 1 ハッシュテーブル(オープンアドレス法) (paizaランク C 相当) [難易度: 1524 ±37]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

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

入力値（例）
4
17
188
38
77777

出力値（例）
77777
-1
-1
-1
-1
-1
-1
17
188
38

解答例

<?php
    for ($i = 0; $i < 10; $i++) {
        $a[$i] = -1;
    }
    
    $n = trim(fgets(STDIN));
    for ($i = 0; $i < $n; $i++) {
        $x = trim(fgets(STDIN));
        
        $hash = $x % 10;
        
        while ($a[$hash] != -1) {
            $hash = ($hash + 1) % 10;
        }
        $a[$hash] = $x;
    }
    foreach($a as $value) {
        echo $value. "\n";
    }
?>

<?php

for ($i = 0; $i < 10; $i++) {

$a[$i] = -1;

}

$n = trim(fgets(STDIN));

for ($i = 0; $i < $n; $i++) {

$x = trim(fgets(STDIN));

$hash = $x % 10;

while ($a[$hash] != -1) {

$hash = ($hash + 1) % 10;

}

$a[$hash] = $x;

}

foreach($a as $value) {

echo $value. "\n";

}

解答例

カテゴリー