Javaを陰から支えるhashCode、その仕組みと実装方法を基礎から紹介
Object.hashCodeは、呼び出されたインスタンスの特徴を表す「ハッシュ値」を返すメソッドです。
このハッシュ値はHashMapやHashSetなどのJava標準APIにあるクラスの多くで使われます。そして、hashCodeはObject.equalsと実に深い関係があるものなのです。
ですから、hashCodeとequalsがしっかり実装されていないと、それらのクラスが動いてほしいように動いてくれません。hashCodeとequalsは一心同体ともいえるメソッドなのです。
この記事では、そんな大事なメソッドhashCodeについて、考え方と実例を交えながら、初心者向けにお伝えします。
※この記事のサンプルは、Java 11の環境で動作確認しています
目次
１．hashCodeはインスタンスの特徴を表す数字を得るもの
皆さんは、MD5やSHA-2のようなハッシュ関数と言うものをご存じでしょうか。簡単に言えば、何かのモノから一つの数字を作り出すアルゴリズムのことです。同じモノならいつでもどこでも同じ数字になりますし、違うモノ同士は同じ数字になるべくならないように仕様が設計されています。
【参考】
https://ja.wikipedia.org/wiki/ハッシュ関数
→ハッシュ関数とは何か、が説明されています。
Javaでもインスタンスのハッシュ関数と呼べるものがあります。それがintを戻すObject.hashCodeです。インスタンスのhashCodeを呼び出すと、インスタンス自身の特徴が反映されたintの数字、すなわちハッシュ値が戻ってきます。
public int hashCode() 戻り値: このオブジェクトのハッシュ・コード値。
hashCodeはequalsと同じく、すべてのクラスのスーパークラスであるObjectのメソッドなので、すべてのクラスで使えます。これをJavaの内部では色々と活用しているのです。
String str1 = "あいうえお"; String str2 = "あいうえおA"; // 中身がちょっと違うだけでも… int hashCode1 = str1.hashCode(); int hashCode2 = str2.hashCode(); System.out.println(hashCode1); // → -1095354298 System.out.println(hashCode2); // → 403755195、全然違う数字になる!!
２．hashCodeは主にハッシュテーブルで活用する
hashCodeで得られる数字は、「ハッシュテーブル」というデータ構造で主に使われます。ハッシュテーブルの中でデータを効率的に分類しつつ、データを高速に検索するためのキー情報として、hashCodeで得られる数字を使うのです。ハッシュテーブル以外では、例えばデータのキャッシュなどでも活用されます。
【参考】
https://ja.wikipedia.org/wiki/ハッシュテーブル
→ハッシュテーブルとは何か、が説明されています。
ハッシュテーブルは、JavaではHashMapやHashSetの内部で使われています。ですから、HashMapのキー、HashSetの値に使うクラスでhashCodeが適切に作られていなければ、これらのハッシュテーブルを使うクラスが予想どおりに動いてくれないのです。
３．hashCodeはしっかりとオーバーライドする
hashCodeがきちんと作られているかいないかで、大きく違いが出てきます。
hashCodeは抽象メソッドではないので、Objectでのデフォルト実装は一応ありますが、それぞれのクラスのことを考えてくれたハッシュ値を戻してはくれないのです。
// Java 11のObjectのソースコードから抜粋、nativeメソッドを呼び出しているだけ
public native int hashCode();３-１．hashCodeをオーバーライドしないと駄目な例
例えば、hashCodeをオーバーライドしないと以下のような動きの違いが出てきます。
もちろん後者が意図どおりの動きなのですが、hashCodeをオーバーライドしているかいないかだけで、処理結果が全然違ってきてしまうのです。
import java.util.HashMap;
class HashCodeSample1 {
int id;
HashCodeSample1(int id) {
this.id = id;
}
public boolean equals(Object obj) {
return id == ((HashCodeSample1) obj).id;
}
// このクラスではhashCodeをオーバーライドしていない
public static void main(String[] args) {
HashCodeSample1 sample1 = new HashCodeSample1(1);
HashCodeSample1 sample2 = new HashCodeSample1(1);
System.out.println(sample1.equals(sample2)); // → true、sample1とsample2は意味的には同じ
System.out.println(sample1.hashCode()); // hashCodeは、sample1とsample2では違う値
System.out.println(sample2.hashCode());
HashMap<HashCodeSample1, String> hashMap = new HashMap<>(); // HashMapを作って…
hashMap.put(sample1, "猫"); // sample1をキーに値を設定して…
String value = hashMap.get(sample2); // 意味的に同じsample2で値を取り出すと…
System.out.println(value); // → null、値である"猫"が取り出せない!!
}
}import java.util.HashMap;
class HashCodeSample2 {
int id;
HashCodeSample2(int id) {
this.id = id;
}
public boolean equals(Object obj) {
return id == ((HashCodeSample2) obj).id;
}
// Object.hashCodeをオーバーライドした。ごく単純に自分自身のintを戻す。
public int hashCode() {
return id;
}
public static void main(String[] args) {
HashCodeSample2 sample1 = new HashCodeSample2(1);
HashCodeSample2 sample2 = new HashCodeSample2(1);
System.out.println(sample1.equals(sample2)); // → true、sample1とsample2は意味的には同じ
System.out.println(sample1.hashCode()); // hashCodeの結果も同じになる(idを戻しているので)
System.out.println(sample2.hashCode());
HashMap<HashCodeSample2, String> hashMap = new HashMap<>(); // HashMapを作って…
hashMap.put(sample1, "猫"); // sample1をキーに値を設定して…
String value = hashMap.get(sample2); // 意味的に同じsample2で値を取り出すと…
System.out.println(value); // → "猫"、値がちゃんと取り出せた!!
}
}４．equalsとhashCodeを結びつける3つのルール
equalsとhashCodeはお互いに深く関係しています。両方とも「同じ」か調べるものですが、用途が違います。でも、きちんと連携していなければなりません。
以下の3つのルールの中で、重要なのは1と2です。hashCodeはこれを守るように作らなければなりません。equalsの動きをを変えたなら、hashCodeも必ずセットで変えましょう、ということでもあります。
- equalsでの判断で使うフィールドが変わらないなら、hashCodeの値も変わらない
- equalsの結果がtrueなら、違うインスタンスでもhashCodeの値は同じになる
- equalsの結果がfalseなら、hashCodeの値は違わなくてもいい
hashCodeの値は自分自身を特徴づける数字でしかなく、インスタンス同士の簡易的な分類・識別が主目的です。
intは全体で43億とおり「しか」表現できない32bitの数字なので、違うクラスのインスタンスが同じintを戻すこともありえます。これを考慮に入れる必要があります。
なお、equalsについては以下の記事も参照してください。
関連記事
５．hashCodeの具体的な計算方法
基本的には、equalsで同じかの判断に使うフィールドのhashCodeを寄せ集めたものを、hashCodeが戻す数字とします。こうすると、なかなかいい感じにインスタンスごとにハッシュ値が異なるからです。
hashCodeの計算方法には「これ一択!!」と言うものはありません。でも、Javaの標準APIにはハッシュコードを計算するユーティリティメソッドがあるので、それを使うとプログラム中で統一したやり方で計算できます。
基本的には、equalsでの判定に使うフィールド全てに対して個別にハッシュ値を計算し、全てを計算結果に混ぜ込んで最終的な値を作ります。
５-１．Javaの標準APIを使う方法
５-１-１．基本的な実装方法
equalsで使うフィールド全てに対して、以下のような感じで計算します。計算式と31はおまじないのようなものだと、今のところはとりあえず考えておいてください。
public int hashCode() {
int result = 0ではない何かの初期値;
result = 31 * result + フィールドごとのハッシュ値;
// ↑をequalsで使っているフィールドすべてに対して行う
return result;
}５-１-２．プリミティブ型のハッシュ値の計算方法
プリミティブ型のラッパークラス(Integer、Doubleなど)にあるhashCodeを使うといいでしょう。
引数があるhashCodeは、引数のプリミティブ型の値に対するhashCodeを返すstaticメソッドです。引数のないhashCodeは、プリミティブ型のインスタンス自身のhashCodeを返すインスタンスメソッドです。
Double d = Double.valueOf(65535); System.out.println(d.hashCode()); // → 1089470432 System.out.println(Double.hashCode(65535)); // → 1089470432
５-１-３．参照型のハッシュ値の計算方法
参照型の場合は、そのインスタンスが持つhashCodeが戻すハッシュ値を使うのが原則です。ただし、そのクラスがequalsと連動したhashCodeを実装しているかは確認しましょう。そうでないと、おかしな計算結果になってしまいます。
実際の計算には、java.util.ObjectsのstaticメソッドhashCodeを使うといいでしょう。nullの場合も処理してくれますので、自分でif文を書かなくてもいいため楽ができます。
String str1 = "ABCD"; String str2 = null; System.out.println(Objects.hashCode(str1)); // → 2001986 System.out.println(Objects.hashCode(str2)); // → 0
５-１-４．配列のハッシュ値の計算方法
java.util.ArraysのhashCodeは、配列の要素ごとにhashCodeを実行して、全体の結果を戻してくれます。配列の型ごとにオーバーライドされたメソッドがあります。
ちなみに、Objects.hashを呼び出すと、Java 11の実装ではこのメソッドが実行されます。
boolean[] blArray = {true, false, true};
double[] dblArray = {1.1, 2.2, 3.3};
String[] strArray = {"A", "B", "C"};
System.out.println(Arrays.hashCode(blArray)); // → 1252360
System.out.println(Arrays.hashCode(dblArray)); // → 742162431
System.out.println(Arrays.hashCode(strArray)); // → 94369java.util.ArraysのdeepHashCodeは、配列の要素の型を自動判定して、再帰的にhashCodeを計算してくれます。例えば、二次元以上の多次元配列を扱いたい場合でも大丈夫です。
double[][] dblArray = { { 1.1, 2.2, 3.3 }, { 4.4, 5.5, 6.6 } };
String[][] strArray = { { "A", "B", "C" }, { "D", "E", "F" } };
System.out.println(Arrays.deepHashCode(dblArray)); // → -603847868
System.out.println(Arrays.deepHashCode(strArray)); // → 3023748５-１-５．hashCodeの実装例
では試しに、前述の方法でhashCodeを実装してみます。
import java.util.Arrays;
import java.util.Objects;
class HashCodeSample3 {
boolean booleanField;
byte byteField;
char charField;
short shortField;
int intField;
long longField;
float floatField;
double doubleField;
String objectField;
String[] arrayField;
public int hashCode() {
int result = 17; // 計算結果、0ではない値で初期化する
final int prime = 31; // 計算で使う奇数の素数
result = prime * result + Boolean.hashCode(booleanField);
result = prime * result + Byte.hashCode(byteField);
result = prime * result + Character.hashCode(charField);
result = prime * result + Short.hashCode(shortField);
result = prime * result + Integer.hashCode(intField);
result = prime * result + Long.hashCode(longField);
result = prime * result + Float.hashCode(floatField);
result = prime * result + Double.hashCode(doubleField);
result = prime * result + Objects.hashCode(objectField);
result = prime * result + Arrays.hashCode(arrayField);
return result;
}
}５-２．【参考】Effective JavaでのhashCode計算方法
有名なJavaの本「Effective Java」で紹介されているhashCode計算の方法は以下のものです(これは第二版のもの)。
1.int resultを、0でない定数(例:17)で初期化する。
2.クラス内のフィールドf(equalsで使うものすべて)で以下の計算をする。
(a) fのハッシュ値「int c」を計算する。
i. booleanなら「(f ? 0 : 1)」の結果
ii. byte/char/short/intなら「(int)f」の結果
iii. longなら「(int)(f ^ (f >>> 32))」の結果
iv. floatなら「Float.floatToIntBits(f)」の結果
v. double なら「Double.doubelToLongBits(f)」のlongで、2 (a) iiiをした結果
vi. 配列ではない参照型変数なら「f.hashCode()」の結果(※きちんと実装されていそうなら)。fがnullなら0。
vii. 配列なら、各要素を別々のフィールドとしてi～vを行った結果
(b) cを「result = 31 * result + c」として結果に混ぜ込む
ちなみに、「31」という謎の数字がいきなり出ていますし、その数字を使ってなぜか掛け算をしています。前述したJava標準APIでの計算方法に出てきた数字31や計算式も、これが元ネタだったりします。
これらの数字や計算方法には、なかなか深遠な理由があるのです。興味があれば、ハッシュコードの計算方法について調べてみてもいいでしょう。
なお、Java標準APIでの実装も、概ねこれと同じです。ただし、細かいところは違っています。
６．【発展】hashCodeのあれこれ
６-１．hashCodeはオーバーライドするもの
Object.hashCodeは、サブクラスで適切にオーバーライド(override)しなければなりません。違う引数を持ったメソッドを作ってオーバーロード(overload)しても、期待したとおりの動きにはなりませんので、気を付けましょう。
６-２．hashCodeを自動生成して楽をする
hashCodeの計算で使うフィールドが増えてくると、それらのフィールドを計算途中にきちんと入れて、動作確認をするだけでも一苦労です。ですが、IDEやライブラリを上手に使うと、きちんとしたhashCodeを簡単に自動生成できたりするのです!! ここで学んで、ぜひどんどん活用しましょう。
６-２-１．IDEの機能を使う
Eclipse、IntelliJ IDEA、NetBeansなどのJava向けIDEでは、hashCodeを自動生成してくれる機能があります。ここではEclipseでの例を示します。
例えば、以下のようなクラスがあったとします。このクラスにEclipseでequalsを自動生成してみましょう。
class HashCodeSample4 {
int intField;
String objField;
}このクラスをパッケージエクスプローラなどから、「右クリック」→「ソース」→「hashCode()およびequals()の生成」を選びます。すると「hashCode()およびequals()の生成」ウィザードが表示されるので、equalsとhashCodeの対象としたいフィールドを選び、OKボタンを押します。
すると、以下のようにequalsとhashCodeが自動生成されました。少々ごちゃごちゃしたソースコードですが、きちんと動きます。それに、実装しづらいhashCodeもequalsと同期を取って生成してくれるのは、大変助かりますね。
class HashCodeSample4 {
int intField;
String objField;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + intField;
result = prime * result + ((objField == null) ? 0 : objField.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
HashCodeSample4 other = (HashCodeSample4) obj;
if (intField != other.intField)
return false;
if (objField == null) {
if (other.objField != null)
return false;
} else if (!objField.equals(other.objField))
return false;
return true;
}
}【参考】
IntelliJ IDEAの自動生成ウィザード
https://www.jetbrains.com/help/idea/generate-equals-and-hashcode-wizard.html
→[英語]IntelliJ IDEAの該当部分のマニュアルです。
NetBeansでの自動生成手順
https://blogs.oracle.com/java/ten-time-savers-in-netbeans-v2
→[英語]「Number 2: Auto-generate getters and setters, constructors and more!」のところに手順があります。
→[英語]equalsを自動する操作の簡単な手順が紹介されています。
６-２-２．ライブラリを使う(Lombokなど)
hashCodeはIDEに自動生成させる以外にも、外部ライブラリを使って自動生成する方法もあります。代表的なのは、Lombokというライブラリを使うことです。
Lombokの詳細や使えるようにする手順は省きますが、以下のようにクラスへアノテーション「@EqualsAndHashCode」を付けるだけで、クラスにあるフィールドを使ったequalsとhashCodeを自動的に作ってくれます!!(※) ものすごく楽ちんですね。
※Javaのソースコード上にはequalsとhashCodeは作成されず、コンパイルした結果のクラスファイル(.class)の中だけに、オーバーライドされたメソッドの実装が自動的に含まれます。
import lombok.EqualsAndHashCode;
@EqualsAndHashCode
public class HashCodeHashCodeSample5 {
int intField;
String objField;
}【参考】
Project Lombok
→[英語]プロジェクトのWEBページです
@EqualsAndHashCode
https://projectlombok.org/features/EqualsAndHashCode
→[英語]公式WEBページ内の、@EqualsAndHashCodeの説明ページです。
７．さいごに
この記事では、Object.hashCodeを説明してきました。hashCodeを使うと、インスタンスを表すハッシュ値が得られます。
あなたが作ったクラスでhashCodeをequalsと併せてオーバーライドしていないと、HashMapやHashSetが上手く動きません。equalsをオーバーライドした時は、忘れずにhashCodeもオーバーライドしましょうね。
equalsとhashCodeを正しく作れば、Javaの標準APIにある色々なクラスを、正しく便利に使えるようになります。少し難しい考え方が求められるところもありますが、しっかりとポイントを押さえて活用できるようになりましょう。
コメント