演習課題「チェイン法の実装」
整数nが与えられ、さらにn個の整数 x_1からx_n が与えられます。
コードエリアには、チェイン法でハッシュテーブルにx_1, x_2, ..., x_nのデータが格納するコードが記述されています。
ハッシュ値が衝突した場合にはリストの末尾にデータを追加するようにして、コードを完成させてください。
期待する出力値
0:
1:
2:
3:
4:
5:
6:
7: 17 777
8: 188 38
9:
＃09:チェイン法の実装
このチャプターでは、チェイン法の実装について学習します。
レベルアップ問題集「ハッシュメニュー」に収録されている「ハッシュテーブル(チェイン法)」の問題を通して、ハッシュ値の衝突対策をしたハッシュテーブルを実装していきます。
入力
・整数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<ArrayList<Integer>>();
for(int i = 0; i < 10; i++){
table.add(new ArrayList<Integer>());
}
int n = sc.nextInt();
for(int i = 0; i < n; i++){
int x = sc.nextInt();
int hash = H(x);
// チェイン法でのデータの追加
table.get(hash).add(x);
}
for (int i = 0; i < 10; i++) {
if (table.get(i).size() > 0) {
System.out.print(table.get(i).get(0));
}
for (int j = 1; j < table.get(i).size(); j++) {
System.out.print(" ");
System.out.print(table.get(i).get(j));
}
System.out.println();
}
}
}