JavaHashMapのキーとしてカスタムクラスを使用する
1. 概要
この記事では、 HashMap がキーと値のペアを内部的に管理する方法と、カスタムキーの実装を作成する方法を学習します。
2. キー管理
2.1. 内部構造
マップは、キーに割り当てられた値を格納するために使用されます。 このキーは、マップの値を識別し、重複を検出するために使用されます。
TreeMapはComparable#compareTo(Object)メソッドを使用してキーを並べ替えます(また、同等性を識別します)が、HashMapはハッシュベースの構造を使用します。簡単なスケッチを使用してより簡単に説明します。
Map は重複キーを許可しないため、 Object#equals(Object)メソッドを使用してキーを相互に比較します。 この方法はパフォーマンスが低いため、呼び出しはできるだけ避ける必要があります。 これは、 Object#hashCode()メソッドを介して実現されます。 このメソッドでは、オブジェクトをハッシュ値で並べ替えることができます。 Object#equals メソッドは、オブジェクトが同じハッシュ値を共有している場合にのみ呼び出す必要があります。
この種の鍵管理は、 HashSet クラスにも適用されます。このクラスの実装では、HashMapが内部で使用されます。
2.2. キーと値のペアの挿入と検索
記事ID( String )で在庫アイテム( Integer )の数を管理する単純なショップのHashMapの例を作成してみましょう。 そこで、サンプル値を入力します。
Map<String, Integer> items = new HashMap<>();
// insert
items.put("158-865-A", 56);
// find
Integer count = items.get("158-865-A");
キーと値のペアを挿入するアルゴリズム:
- “ 158-865-A” .hashCode()を呼び出して、ハッシュ値を取得します
- 同じハッシュ値を共有する既存のキーのリストを探します
- リストの任意のキーを「158-865-A」と比較します。equals(key)
- 最初の等式は既存のものとして識別され、新しいものが割り当てられた値を置き換えます。
- 等式が発生しない場合、キーと値のペアが新しいエントリとして挿入されます。
値を見つけるためのアルゴリズムは同じですが、値が置き換えられたり挿入されたりすることはありません。
3. カスタムキークラス
キーにカスタムクラスを使用するには、 hashCode()とequals()が正しく実装されている必要があると結論付けることができます。 簡単に言うと、 hashCode()メソッドが次を返すことを確認する必要があります。
- 状態が変化しない限り、オブジェクトの値は同じです( Internal Consistency )
- 等しいオブジェクトの同じ値( Equals Consistency )
- 等しくないオブジェクトに対して可能な限り多くの異なる値。
hashCode()と equals()は計算で同じフィールドを考慮する必要があり、両方をオーバーライドするか、どちらもオーバーライドしない必要があると一般的に言えます。 これは、LombokまたはIDEのジェネレーターを使用して簡単に実現できます。
もう1つの重要なポイントは次のとおりです。オブジェクトがキーとして使用されている間はオブジェクトのハッシュコードを変更しないでください。簡単な解決策は、キークラスを不変になるように設計することです。キーで操作が行われないようにすることができる限り、これは必要ありません。
ここで不変性には利点があります。ハッシュ値はオブジェクトのインスタンス化時に一度計算できるため、特に複雑なオブジェクトのパフォーマンスが向上する可能性があります。
3.1. 良い例え
例として、xとyの値で構成されるCoordinateクラスを設計し、それをHashMapのキーとして使用します。 :
Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2);
pixels.put(coord, Color.CYAN);
// read the color
Color color = pixels.get(new Coordinate(1, 2));
Coordinateクラスを実装しましょう。
public class Coordinate {
private final int x;
private final int y;
private int hashCode;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
this.hashCode = Objects.hash(x, y);
}
public int getX() {
return x;
}
public int getY() {
return y;
}
@Override
public boolean equals(Object o) {
if (this == o)
return true;
if (o == null || getClass() != o.getClass())
return false;
Coordinate that = (Coordinate) o;
return x == that.x && y == that.y;
}
@Override
public int hashCode() {
return this.hashCode;
}
}
別の方法として、Lombokを使用してクラスをさらに短くすることもできます。
@RequiredArgsConstructor
@Getter
// no calculation in the constructor, but
// since Lombok 1.18.16, we can cache the hash code
@EqualsAndHashCode(cacheStrategy = CacheStrategy.LAZY)
public class Coordinate {
private final int x;
private final int y;
}
最適な内部構造は次のとおりです。
3.2. 悪い例:静的ハッシュ値
すべてのインスタンスに静的ハッシュ値を使用してCoordinateクラスを実装すると、 HashMap は正しく機能しますが、パフォーマンスは大幅に低下します。
public class Coordinate {
...
@Override
public int hashCode() {
return 1; // return same hash value for all instances
}
}
ハッシュ構造は次のようになります。
これは、ハッシュ値の利点を完全に打ち消します。
3.3. 悪い例:変更可能なハッシュ値
キークラスを可変にする場合は、インスタンスがキーとして使用されている間、インスタンスの状態が変更されないようにする必要があります。
Map<Coordinate, Color> pixels = new HashMap<>();
Coordinate coord = new Coordinate(1, 2); // x=1, y=2
pixels.put(coord, Color.CYAN);
coord.setX(3); // x=3, y=2
Coordinate は古いハッシュ値で保存されているため、新しいハッシュ値では見つかりません。 したがって、以下の行はnull値になります。
Color color = pixels.get(coord);
そして、次の行は、オブジェクトがMap内に2回格納される結果になります。
pixels.put(coord, Color.CYAN);
4. 結論
この記事では、 HashMap のカスタムキークラスを実装することは、 equals()と hashCode()を正しく実装することの問題であることを明確にしました。 ハッシュ値が内部でどのように使用され、これが良い方法と悪い方法の両方でどのように影響を受けるかを見てきました。
いつものように、サンプルコードはGitHubでから入手できます。