演習課題「オープンアドレス法の実装」
整数nが与えられ、さらにn個の整数 x_1からx_n が与えられます。
コードエリアには、オープンアドレス法でハッシュテーブルにx_1, x_2, ..., x_nのデータが格納するコードが記述されています。
ハッシュ値を再計算する部分のコードを書き加えて、コードを完成させてください。
ハッシュ値が衝突した場合には、ハッシュ値を1増加させてハッシュ関数で再計算してください。
期待する出力値
77777
-1
-1
-1
-1
-1
-1
17
188
38
＃08:オープンアドレス法の実装
このチャプターでは、オープンアドレス法の実装について学習します。
レベルアップ問題集「ハッシュメニュー」に収録されている「ハッシュテーブル(オープンアドレス法)」の問題を通して、ハッシュ値の衝突対策をしたハッシュテーブルを実装していきます。
入力
・整数n
・n個の文字列 x_1, x_2, …, x_n
出力
・ハッシュテーブルを表す配列の要素を0番目からすべて表示
・配列の要素数は10
import java.util.*;
public class Main {
// ハッシュ関数
static int H(int x) {
return x % 10;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// ハッシュテーブルの初期化
var table = new ArrayList<Integer>();
for(int i = 0; i < 10; i++){
table.add(-1);
}
int n = sc.nextInt();
for(int i = 0; i < n; i++){
int x = sc.nextInt();
int hash = H(x);
// オープンアドレス法
while (table.get(hash) != -1) {
hash = H(hash + 1);
}
// データの追加
table.set(hash, x);
}
for (int i = 0; i < 10; i++) {
System.out.println(table.get(i));
}
}
}