【今回学ぶこと】
・HashSetでremove()できない例を知る
・HashSetの内部動作を知る
・上記2点を知った上での解決方法を学ぶ(hashCord()のオーバーライド)
【そもそもHashSetとは・・・】
データをどのようにまとめて扱うかを取り決めた、データ構造の一種です。
格納したいデータが単独情報の集まりかつ、重複がNGで取り出す順序が不問の時に使用します。
詳細リンク：
【Java】コレクションクラス(Set関連クラス) - たなかのJava日記
【なぜかHashSetでremove()できない・・・】
以前、equals()を正しくオーバライドしていないクラスを「コレクション」に格納すると誤動作に繋がることを学びました。
なぜ誤作動に繋がるかを簡単に復習すると、
まずArrayListのremove()は、引数として渡したインスタンスと同じものを削除してとJVMに依頼するメソッドです。
依頼を受けたJVMはArrayListから同じものを探すため、equals()による等価判定を行います。
しかし、オーバライドしていないjava.lang.Objectクラスに定義されているequals()の中身は「ただの等値判定」ロジックです。
要は同じアドレスかどうかを判定して探しています。
つまり、eauals()で何をもってインスタンスを同じものと見なすかをオーバライドして決めておかないと、
remove()した時に等値判定(同じアドレスか)で削除対象を決めてしまうため、意図した削除ができません。
すでに親クラスでequals()が正しくオーバライドされているクラスを除き、
クラスを作ったら「何をもって同じ内容と見なすか」をequals()でオーバーライドしておく必要があります。
とのことでした。
詳細リンク：
【Java】インスタンスの等価判定(後編) - たなかのJava日記
しかし、たとえjava.lang.Objectクラスに定義されているequals()をオーバーライドしていても、Hash系のコレクションを使う場合では誤動作をするというのです。
以下がHashSetを使用してremove()できない例です。
package jp.co.mtanaka;
import java.util.HashSet;
import java.util.Set;
public class Sample3 {
public static void main(String[] args) {
Set<Hero> heroList = new HashSet<>();
Hero ultraman = new Hero("ウルトラマンティガ");
heroList.add(ultraman);
System.out.println("要素数=" + heroList.size());
ultraman = new Hero("ウルトラマンティガ");
heroList.remove(ultraman);
System.out.println("要素数=" + heroList.size());
System.out.println(ultraman);
}
}
package jp.co.mtanaka;
public class Hero {
public String name;
public Hero(String ultramanName) {
this.name = ultramanName;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if(!(obj instanceof Hero)) {
return false;
}
Hero hero = (Hero) obj;
if (!this.name.equals(hero.name)) {
return false;
}
return true;
}
@Override
public String toString() {
return "ウルトラマン(名前=" + this.name + ")";
}
}
実行結果：
要素数=1
要素数=1
ウルトラマン(名前=ウルトラマンティガ)
【なぜ削除できなかったのか・・・】
そのためには、HashSetの内部動作を知ることが必要です。
しかし、その前にArrayListのremove()について再再再復習させてください...
ArrayListのremove()は引数として渡したインスタンスと同じものを削除してとJVMに依頼するメソッドです。
依頼を受けたJVMはArrayListから同じものを探すためにequals()による等価判定を行います。
しかし、オーバライドしていないjava.lang.Objectクラスに定義されているequals()の中身は「ただの等値判定」ロジックです。
要は同じアドレスかどうかを判定して探しています。
つまり、eauals()で何をもってインスタンス同士を同じものと見なすかをオーバライドして決めておかないと、
remove()した時に等値判定(同じアドレスか)で削除対象を決めてしまうため、意図した削除ができません。
すでに親クラスでequals()が正しくオーバライドされているクラスを除き、
クラスを作ったら「何をもって同じ内容と見なすか」をequals()でオーバーライドしておく必要があります。
一方で、HashSetのremove()では少し異なります。
いきなり各要素にオーバライドしたequals()を使用して、等価(同じ内容か)判定することはしません。
何回も内部でnull判定から始まり、キャストしたり、各フィールドの等価判定を繰り返すことは非効率だからです。
特にフィールド数が多ければ多いほど、ひとつひとつの比較が負担になります。
つまり、equals()による等価判定には大きな計算コスト(時間)がかかるのです。
そこで一旦、他の方法で比較を行い、対象を絞ってから必要な箇所のみequals()で等価判定するのが、
HashSetやHashMapのようなHash系のコレクションクラスの特徴(仕様)になります。
【具体的にどのようにして、高速で削除の判断を行っていたのか】
先ほどもお伝えしたように、HashSetやHashMapのようなHash系のコレクションクラスでは、
2段階方式で目的(削除など)の要素を探し出しています。詳しくは以下の通りです。
１、高速だがあいまいな方法で、各要素に「だいたい同じか？」を問い合わせる
２、「だいたい同じ」な要素にだけ、equals()で「厳密に同じか？」を問い合わせる
「だいたい同じか？」を判定するためには、「ハッシュ値」というものを利用します。
【ハッシュ値とは】
一言で述べるなら、そのインスタンスの内容を数値として要約したものです。
Javaでは「すべてのオブジェクトは自身のハッシュ値を計算できるべきである」との考えから、
ObjectクラスにhashCode()メソッドが定義されています。返すのはint型の整数値です。
また、その数値自体に意味はありません。
hashCode()で得られる数字は、「ハッシュテーブル」というデータ構造で主に使われます。
ハッシュテーブルの中でデータを効率的に分類しつつ、
データを高速に検索するためのキー情報として、hashCode()で得られる数字を使うのです。
ハッシュテーブル以外では、例えばデータのキャッシュなどでも活用されます。
参考サイト：
ハッシュ値とは : JavaA2Z
【ハッシュ値の条件・ルールとは】
★同じ(等価)インスタンスからは、必ず同じハッシュ値が得られること
☆異なるインスタンスからはなるべく異なるハッシュ値が得られること
例：
String name = "ポッチャマ"; ⇒ ハッシュ値5000
String name = "ポッチャマ"; ⇒ ハッシュ値5000
同じ(等価)インスタンスならハッシュ値も必ず同じになる
String name = "ヤドン"; ⇒ ハッシュ値6666
String name = "ドッコラー"; ⇒ ハッシュ値6666
※異なるインスタンス(等価でない場合)でも、まれに同じハッシュ値になることもある
また、★について注意点があります。
要素がオブジェクトであった場合、オブジェクトでhashcode()が定義(オーバライド)されてなければ、
同じオブジェクト(アドレスが同じ=等値)でなければ、ハッシュ値は異なるものとして計算されてしまいます。
これはObjectクラスの標準実装でそのような処理になっているからです。
そのため、本来であれば等価(同じ内容)であるオブジェクトが異なるものとして(等価ではない)判定されてしまいます。
これまでの説明を踏まえると、
「HashSetやHashMapのようなHash系のコレクションクラス」の内部動作は以下になります。
１、HashSetやHashMapで操作(removeなど)をした場合、まず各要素のhashCode()呼び出す
２，ハッシュ値が同じかを判定する(ハッシュ値の比較は整数値の比較なので高速)
３、ハッシュ値が一致した要素にだけ、オーバライドしたequals()で等価判定を行う
これまでの説明やこの3点からわかるように、ObjectクラスのhashCode()を呼び出された際に
ハッシュ値の条件に従った値を返すのですが、我々でコントロールできていないことが問題です。
例えば、異なるインスタンス(等価でない場合)は、
まれに同じハッシュ値になることもあれば、違うハッシュ値になること。
また、要素がオブジェクトであった場合、
同じオブジェクト(アドレスが同じ=等値)でなければ、ハッシュ値は異なるものとして計算されてしまいます。
そのため、本来であれば等価(同じ内容)であるオブジェクトが異なるものとして判定されてしまうことなどです。
先ほどのコードで削除が出来なかったのは、
HeroクラスのhashCode()がオーバーライドされていなかったためです。
そのため、同じオブジェクト(アドレスが同じ=等値)でなければ、ハッシュ値は異なるものとして計算されてしまい、equals()を呼ぶまでもなく削除できなかったのです。
【hashCode()から正しい条件を満たすハッシュ値は返すようにすればよい】
結局は、Objectクラスから継承されるequals()やtoString()がそのままでは使い物にならなかったのと同じです。
Objectクラスから継承される標準のhashCode()も、条件を満たすハッシュ値を正しく返す作りにはなっていません。
よって、Heroクラスなどのクラスを開発する私たち自身がhashCode()を正しくオーバライドする必要があります。
その方法(ハッシュ値の計算アルゴリズム)は様々なものがありますが、一例を下記に記します。
package jp.co.mtanaka;
import java.util.Objects;
public class Hero {
public String name;
public Hero(String ultramanName) {
this.name = ultramanName;
}
@Override
public int hashCode() {
return Objects.hash(this.name);
}
}
package jp.co.mtanaka;
import java.util.HashSet;
import java.util.Set;
public class Sample3 {
public static void main(String[] args) {
Set<Hero> heroList = new HashSet<>();
Hero ultraman = new Hero("ウルトラマンティガ");
heroList.add(ultraman);
System.out.println("要素数=" + heroList.size());
ultraman = new Hero("ウルトラマンティガ");
heroList.remove(ultraman);
System.out.println("要素数=" + heroList.size());
System.out.println(ultraman);
}
}
実行結果：
要素数=1
要素数=0
ウルトラマン(名前=ウルトラマンティガ)
java.util.Objectsクラスのhashメソッドは、
任意の個数の引数を受け取り、その引数に基づきハッシュコードとして適切な整数値を生成してくれるAPIです。
通常は、そのクラス自身のすべてのフィールドを引数として引き渡すことが多いです。
【まとめ】
HashSetやHashMapのようなHash系のコレクションクラスで操作(removeなど)を行った際は、最初からequals()で等価判定はしないことになっています。
理由は、フィールド数に比例して時間がかかるためです。
目的(削除など)の要素を高速で探し出すためにはhashCode()をオーバーライドし、
ハッシュ値を適切に生成しておく必要があります。
具体的な実行手順は以下の通りです。
１、HashSetやHashMapで操作(removeなど)をした場合、まず各要素のオーバライドしたhashCode()呼び出す
２、オーバライドしたhashCode()では、任意の個数の引数を受け取り、その引数に基づきハッシュコードとして適切な整数値を生成してくれる
通常は、そのクラス自身のすべてのフィールドを引数として引き渡すことが多い
これで、同じインスタンス(等価)なら、必ず同じハッシュ値が得られるようになる
３，ハッシュ値が同じかを判定する(ハッシュ値の比較は整数値の比較なので高速)
４、ハッシュ値が一致した要素にだけ、オーバライドしたequals()で等価判定を行う
５、ここまで来て合致したら、目的の要素に対して操作を行う。
参考サイト：
equals,hashcodeについて
HashSetの利用とhashCodeメソッド、equalsメソッドの実装 - システムエンジニア兼IT講師の備忘録