JavaのHashSetを使う時に・・・
年末に「世界で戦うプログラミング力を鍛える150問」という本を読んでいるのですが、その問題を解いている時にJavaのHashSetの使用方法で少し悩んだ部分があったので、ここでメモを。
一般に、ハッシュテーブルというと、オブジェクトごとに振られたハッシュ値が等しいかどうかで、オブジェクトが等価であるかどうかを判定するものだと思い込んでいたので、JavaのHashSetでもそういう実装になっているのだろうと思い込んでいました。つまり、HashSetではオブジェクトが既にSet内に存在しているか、存在していないかをObjectクラスのメソッドであるhashCodeというメソッドの戻り値を用いて比較しているのだろうと思ったわけです。
ところが、次のようなコードを書いたところ、実行結果が期待しない結果になってしまいました。
import java.io.*;
import java.util.*;
public class Problem02_1 {
public static void main(String... args) {
new Problem02_1();
}
public Problem02_1() {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
List<Node> list = new LinkedList<Node>();
for(int i=0; i<n; i++) {
int data = scan.nextInt();
list.add(new Node(data));
}
deleteDups(list);
Iterator<Node> it = list.iterator();
while(it.hasNext()) {
System.out.printf("%d ", it.next().data);
}
System.out.println();
}
void deleteDups(List<Node> list) {
Set<Node> hash = new HashSet<Node>();
Iterator<Node> it = list.iterator();
while(it.hasNext()) {
Node n = it.next();
if(hash.contains(n)) {
it.remove();
} else {
hash.add(n);
}
}
}
}
class Node {
public int data;
public Node(int data) {
this.data = data;
}
public boolean equals(Node n) {
return (this.data == n.data);
}
public int hashCode() {
return this.data;
}
}
このコードは単にdataという1つの整数値のみを値として持つNodeクラスをLikedListに格納して、そこに重複した要素があれば、それを除去するというものなのですが、これを実行し、適当にdataの値を与えると次のようになりました。
5 // 連想配列の要素数
1 2 3 4 2 // Nodeの持つ値
1 2 3 4 2 // 出力された連想配列のNodeの値
つまり、同じハッシュ値を持つはずのNodeが削除されていないわけです。ここで、hashCodeメソッドが戻す値が違うのだろうか？とかいろいろと思いを巡らせたわけですが、どうもそうではないらしい。調べてみると、JavaのHashSetクラスはオブジェクトの等価判定にequalsメソッドも使っているようなのです。結局何が間違っていたかと言うと、Nodeクラスでオーバーライドすべきequalsメソッドは引数にNodeをとるものではなく、Objectをとるものでなくてはなりませんでした。
修正したNodeクラスのコードは次のようになります。
class Node {
public int data;
public Node(int data) {
this.data = data;
}
public boolean equals(Object o) {
Node n = (Node)o;
return (this.data == n.data);
}
public int hashCode() {
return this.data;
}
}
これを実行したところ正しく重複要素が削除されました。めでたしめでたし。