コレクションの hashCode メソッドの最適な実装
質問
最適な実装をどのように決定するか hashCode()
コレクションのメソッド (equals メソッドが正しくオーバーライドされていると仮定します) ?
解決
最良の実装?それは使用パターンによって異なるため、難しい質問です。
ほぼすべてのケースにおいて、適切な実装が提案されています。 ジョシュ・ブロックさんの 効果的なJava 項目 8 (第 2 版)。一番良いのは、そのアプローチが良い理由を著者がそこで説明しているので、そこで調べることです。
ショートバージョン
を作成します
int result
そして割り当てます ゼロ以外の 価値。のために あらゆる分野
f
でテストされましたequals()
メソッド、ハッシュ コードを計算するc
による:- フィールド f が a の場合、
boolean
:計算する(f ? 0 : 1)
; - フィールド f が a の場合、
byte
,char
,short
またはint
:計算する(int)f
; - フィールド f が a の場合、
long
:計算する(int)(f ^ (f >>> 32))
; - フィールド f が a の場合、
float
:計算するFloat.floatToIntBits(f)
; - フィールド f が a の場合、
double
:計算するDouble.doubleToLongBits(f)
そして戻り値を他の長い値と同様に処理します。 - フィールド f が 物体:の結果を使用します。
hashCode()
メソッドまたは 0 の場合f == null
; - フィールド f が 配列:すべてのフィールドを個別の要素として参照し、ハッシュ値を計算します。 再帰的なファッション 次に説明するように値を組み合わせます。
- フィールド f が a の場合、
ハッシュ値を結合する
c
とresult
:result = 37 * result + c
戻る
result
これにより、ほとんどの使用状況でハッシュ値が適切に分散されるはずです。
他のヒント
dmeister が推奨する効果的な Java 実装に満足している場合は、独自のローリングの代わりにライブラリ呼び出しを使用できます。
@Override
public int hashCode() {
return Objects.hashCode(this.firstName, this.lastName);
}
これにはグアバ (com.google.common.base.Objects.hashCode
) または Java 7 の標準ライブラリ (java.util.Objects.hash
) ただし、同じように機能します。
Eclipse が提供する非常に優れた機能を使用することをお勧めします。これにより、ビジネス ロジックの開発に労力とエネルギーを注ぐことができます。
これとリンクしているのですが、 Android
ドキュメント (ウェイバックマシン) そして Github にある自分のコード, 、Java 全般で動作します。私の答えは次の拡張です dマイスターの答え コードだけで、非常に読みやすく、理解しやすくなります。
@Override
public int hashCode() {
// Start with a non-zero constant. Prime is preferred
int result = 17;
// Include a hash for each field.
// Primatives
result = 31 * result + (booleanField ? 1 : 0); // 1 bit » 32-bit
result = 31 * result + byteField; // 8 bits » 32-bit
result = 31 * result + charField; // 16 bits » 32-bit
result = 31 * result + shortField; // 16 bits » 32-bit
result = 31 * result + intField; // 32 bits » 32-bit
result = 31 * result + (int)(longField ^ (longField >>> 32)); // 64 bits » 32-bit
result = 31 * result + Float.floatToIntBits(floatField); // 32 bits » 32-bit
long doubleFieldBits = Double.doubleToLongBits(doubleField); // 64 bits (double) » 64-bit (long) » 32-bit (int)
result = 31 * result + (int)(doubleFieldBits ^ (doubleFieldBits >>> 32));
// Objects
result = 31 * result + Arrays.hashCode(arrayField); // var bits » 32-bit
result = 31 * result + referenceField.hashCode(); // var bits » 32-bit (non-nullable)
result = 31 * result + // var bits » 32-bit (nullable)
(nullableReferenceField == null
? 0
: nullableReferenceField.hashCode());
return result;
}
編集
通常、オーバーライドするときは、 hashcode(...)
, 、オーバーライドすることもできます equals(...)
. 。これから実装する人、またはすでに実装している人のために equals
, 、ここが良い参考資料です 私のGithubから...
@Override
public boolean equals(Object o) {
// Optimization (not required).
if (this == o) {
return true;
}
// Return false if the other object has the wrong type, interface, or is null.
if (!(o instanceof MyType)) {
return false;
}
MyType lhs = (MyType) o; // lhs means "left hand side"
// Primitive fields
return booleanField == lhs.booleanField
&& byteField == lhs.byteField
&& charField == lhs.charField
&& shortField == lhs.shortField
&& intField == lhs.intField
&& longField == lhs.longField
&& floatField == lhs.floatField
&& doubleField == lhs.doubleField
// Arrays
&& Arrays.equals(arrayField, lhs.arrayField)
// Objects
&& referenceField.equals(lhs.referenceField)
&& (nullableReferenceField == null
? lhs.nullableReferenceField == null
: nullableReferenceField.equals(lhs.nullableReferenceField));
}
まず、equals が正しく実装されていることを確認してください。から IBM DeveloperWorks の記事:
- 対称:2 つの参照 a と b の場合、b.equals(a) の場合に限り、a.equals(b)
- 反射性:すべての非 null 参照の場合、a.equals(a)
- 推移性:a.equals(b) と b.equals(c) の場合、a.equals(c)
次に、hashCode との関係が連絡先を尊重していることを確認します (同じ記事から)。
- hashCode() との一貫性:2 つの等しいオブジェクトは同じ hashCode() 値を持つ必要があります
最後に、優れたハッシュ関数は、 理想的なハッシュ関数.
about8.blogspot.com、あなたは言いました
equals() が 2 つのオブジェクトに対して true を返す場合、hashCode() は同じ値を返す必要があります。equals() が false を返した場合、hashCode() は異なる値を返す必要があります
私はあなたに同意できません。2 つのオブジェクトが同じハッシュコードを持っている場合、それらが等しいことを意味する必要はありません。
A が B と等しい場合、A.hashcode は B.hascode と等しくなければなりません
しかし
A.hashcode が B.hascode に等しい場合、A が B に等しい必要があるという意味ではありません
Eclipseを使用する場合は、次のように生成できます。 equals()
そして hashCode()
使用:
ソース -> hashCode()とequals()を生成します。
この機能を使用すると、次のように決定できます。 どのフィールド 等価性とハッシュ コードの計算に使用すると、Eclipse が対応するメソッドを生成します。
の良い実装があります 効果的なJavaさんの hashcode()
そして equals()
ロジックイン Apache Commons Lang. 。チェックアウト ハッシュコードビルダー そして イコールビルダー.
他のより詳細な回答(コードの観点から)を完了するための簡単なメモ:
という疑問を考えてみると Javaでハッシュテーブルを作成する方法 そして特に jGuru FAQ エントリー, ハッシュコードが判断される他の基準は次のとおりだと思います。
- 同期 (アルゴは同時アクセスをサポートしていますか)?
- フェールセーフ反復 (反復中に変更されるコレクションをアルゴが検出しますか)
- null 値 (ハッシュ コードはコレクション内の null 値をサポートしますか)
あなたの質問を正しく理解できれば、カスタムコレクションクラス(つまり、Collection インターフェイスから拡張された新しいクラス)、hashCode() メソッドを実装したいとします。
コレクション クラスが AbstractList を拡張している場合は、それについて心配する必要はありません。すべてのオブジェクトを反復処理し、それらの hashCodes() を一緒に追加することで動作する、equals() と hashCode() の実装がすでに存在します。
public int hashCode() {
int hashCode = 1;
Iterator i = iterator();
while (i.hasNext()) {
Object obj = i.next();
hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
}
return hashCode;
}
ここで、特定のクラスのハッシュ コードを計算する最良の方法が必要な場合、通常は ^ (ビットごとの排他的論理和) 演算子を使用して、equals メソッドで使用するすべてのフィールドを処理します。
public int hashCode(){
return intMember ^ (stringField != null ? stringField.hashCode() : 0);
}
@about8 :そこにはかなり深刻なバグがあります。
Zam obj1 = new Zam("foo", "bar", "baz");
Zam obj2 = new Zam("fo", "obar", "baz");
同じハッシュコード
あなたはおそらく次のようなものを望んでいます
public int hashCode() {
return (getFoo().hashCode() + getBar().hashCode()).toString().hashCode();
(最近では Java で int から直接 hashCode を取得できますか?自動キャストを行っていると思います。その場合は、見苦しいので toString をスキップしてください。)
特にコレクションを求められたので、他の回答でまだ言及されていない側面を追加したいと思います。HashMap は、キーがコレクションに追加された後にそのキーのハッシュコードが変更されることを期待しません。目的全体が無効になってしまうでしょう...
Apache Commons のリフレクション メソッドを使用する イコールビルダー そして ハッシュコードビルダー.
可能な範囲にわたってハッシュ値を均等に分散するハッシュ方法は、適切な実装です。効果的な Java ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=Effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=ja&sa=X&oi=book_result&resnum=1&ct=result )、そこにはハッシュコードの実装に関する良いヒントがあります (項目 9 だと思います...)。
私はユーティリティメソッドを使用することを好みます クラス Objects からの Google Collections ライブラリ それはコードをきれいに保つのに役立ちます。よく equals
そして hashcode
メソッドは IDE のテンプレートから作成されているため、読みやすいものではありません。
小さなラッパーを使用しています Arrays.deepHashCode(...)
パラメータとして指定された配列を正しく処理するため
public static int hash(final Object... objects) {
return Arrays.deepHashCode(objects);
}
ここでは、スーパークラス ロジックを考慮した別の JDK 1.7 以降のアプローチのデモンストレーションを示します。オブジェクト クラス hashCode() が考慮されており、純粋な JDK 依存関係があり、余分な手動作業がないため、非常に便利だと思います。ご注意ください Objects.hash()
null トレラントです。
何も入ってないよ equals()
実装ですが、実際にはもちろん必要になります。
import java.util.Objects;
public class Demo {
public static class A {
private final String param1;
public A(final String param1) {
this.param1 = param1;
}
@Override
public int hashCode() {
return Objects.hash(
super.hashCode(),
this.param1);
}
}
public static class B extends A {
private final String param2;
private final String param3;
public B(
final String param1,
final String param2,
final String param3) {
super(param1);
this.param2 = param2;
this.param3 = param3;
}
@Override
public final int hashCode() {
return Objects.hash(
super.hashCode(),
this.param2,
this.param3);
}
}
public static void main(String [] args) {
A a = new A("A");
B b = new B("A", "B", "C");
System.out.println("A: " + a.hashCode());
System.out.println("B: " + b.hashCode());
}
}
標準の実装は弱いため、これを使用すると不要な衝突が発生します。想像してみてください
class ListPair {
List<Integer> first;
List<Integer> second;
ListPair(List<Integer> first, List<Integer> second) {
this.first = first;
this.second = second;
}
public int hashCode() {
return Objects.hashCode(first, second);
}
...
}
今、
new ListPair(List.of(a), List.of(b, c))
そして
new ListPair(List.of(b), List.of(a, c))
同じものを持っています hashCode
, 、つまり 31*(a+b) + c
に使用される乗数として List.hashCode
ここで再利用されます。もちろん、衝突は避けられませんが、不必要な衝突を引き起こすのは単なる...不必要です。
実質的に賢い使い方は何もありません 31
. 。情報の損失を避けるために、乗数は奇数でなければなりません (偶数の乗数は少なくとも最上位ビットを失い、4 の倍数は 2 を失います)。任意の奇数の乗数を使用できます。乗算器が小さいと計算が高速になる可能性がありますが (JIT はシフトと加算を使用できます)、最新の Intel/AMD では乗算のレイテンシが 3 サイクルしかないことを考えると、これはほとんど問題になりません。また、乗算器が小さいと、小さい入力に対して衝突が多くなり、問題になる場合があります。
環 Z/(2**32) では素数は意味を持たないため、素数を使用することは無意味です。
したがって、ランダムに選択された大きな奇数を使用することをお勧めします (素数を自由に取ってください)。i86/amd64 CPU は、単一の符号付きバイトに収まるオペランドに短い命令を使用できるため、109 のような乗算器では速度がわずかに向上します。衝突を最小限に抑えるには、0x58a54cf5 などを使用します。
異なる場所で異なる乗算器を使用することは役に立ちますが、おそらく追加の作業を正当化するには十分ではありません。
ハッシュ値を結合するときは、通常、boost C++ ライブラリで使用される結合メソッドを使用します。
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
これは、均一な分布を確保する上でかなりうまく機能します。この式がどのように機能するかについては、StackOverflow の投稿を参照してください。 boost::hash_combine のマジックナンバー
さまざまなハッシュ関数についての詳しい説明は次の場所にあります。 http://burtleburtle.net/bob/hash/doobs.html
単純なクラスの場合、多くの場合、equals() 実装によってチェックされるクラス フィールドに基づいて hashCode() を実装するのが最も簡単です。
public class Zam {
private String foo;
private String bar;
private String somethingElse;
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
Zam otherObj = (Zam)obj;
if ((getFoo() == null && otherObj.getFoo() == null) || (getFoo() != null && getFoo().equals(otherObj.getFoo()))) {
if ((getBar() == null && otherObj. getBar() == null) || (getBar() != null && getBar().equals(otherObj. getBar()))) {
return true;
}
}
return false;
}
public int hashCode() {
return (getFoo() + getBar()).hashCode();
}
public String getFoo() {
return foo;
}
public String getBar() {
return bar;
}
}
最も重要なことは、 hashCode() とquals() の一貫性を保つことです。equals() が 2 つのオブジェクトに対して true を返す場合、hashCode() は同じ値を返す必要があります。equals() が false を返した場合、hashCode() は異なる値を返す必要があります。