ハッシュテーブル

2002年6月21日

Q:ハッシュテーブルでオブジェクトをキーとして使用する場合、Objectクラスの何をオーバーライドする必要がありますか?その理由は何ですか?

A:あなたが使用するために、独自のキーオブジェクトを作成するときにHashtable、あなたがオーバーライドする必要がありますObject.equals()し、Object.hashCode()以降のメソッドをHashtable使用のキーの組み合わせhashCode()equals()店に方法を、すぐにそのエントリを取得。をオーバーライドするときはequals()、常にをオーバーライドすることも一般的なルールですhashCode()

理由の詳細

もう少し詳細な説明はHashtable、保存と取得のメカニズムを理解するのに役立ちます。 Aは、Hashtable内部的には、キー/値のペアを格納するバケットが含まれています。Hashtableキー/値のペアをマップするべきバケットに決定するために、キーのハッシュコードを使用しています。

図1は、Hashtableとそのバケットを示しています。キー/値をに渡すとHashtable、キーのハッシュコードが照会されます。Hashtableコードはバケットを決定するという用途には、キー/値を配置します。したがって、たとえば、ハッシュコードがゼロに等しい場合、Hashtable値はバケット0に配置されます。同様に、ハッシュコードが2の場合Hashtable、値はバケット2に配置されます(これは単純な例です。Hashtable最初にハッシュコードをマッサージするため、Hashtableバケットの外に値を挿入しようとはしません。)

このようにハッシュコードを使用するHashtableことで、は、値を取得しようとしたときに、値を配置したバケットをすばやく判別することもできます。

ただし、ハッシュコードは全体像の半分にすぎません。ハッシュコードはHashtable、キー/値をドロップするバケットのみを指示します。ただし、複数のオブジェクトが同じバケットにマップされる場合があります。これは、衝突と呼ばれるイベントです。Javaでは、Hashtable同じバケットに複数の値を配置することで衝突に応答します(他の実装では衝突の処理が異なる場合があります)。図2はHashtable、数回の衝突後のがどのように見えるかを示しています。

ここget()で、バケット0にマップするキーを使用して呼び出すと想像してください。次に、バケット0のHashtableキーと値のペアを順次検索して、要求された値を見つける必要があります。このルックアップを実行するために、Hashtableは次の手順を実行します。

  1. キーのハッシュコードを照会する
  2. ハッシュコードで指定されたバケットにあるキー/値のリストを取得します
  3. 渡されたキーと等しいキーget()が見つかるまで、各エントリを順番にスキャンします

私が知っている短い質問に対する長い答えですが、それはさらに悪化します。適切にオーバーライドequals()hashCode()、重要な演習です。両方の方法の契約を保証するために細心の注意を払う必要があります。

equals()の実装について

equals()Javadocによると、メソッドは次のルールに準拠している必要があります。

「この equals()メソッドは、同値関係を実装します。
  • それは反射的です:任意の参照値xに対して、x.equals(x)trueを返す必要があります
  • 対称です。参照値xおよびyについてx.equals(y)は、trueを返す場合にのみy.equals(x)trueを返す必要があります。
  • これは推移的です。任意の参照値x、y、およびzについて、x.equals(y)trueをy.equals(z)返し、trueを返す場合、trueを返すx.equals(z)必要があります
  • 一貫性があります。参照値xおよびyx.equals(y)について、オブジェクトの同等の比較で使用される情報が変更されていない場合、一貫してtrueまたは一貫してfalseを返す複数の呼び出し。
  • null以外の参照値xの場合、x.equals(null)falseを返す必要があります」

効果的なJavaの、ジョシュア・ブロックは、効果的な書き込みを行うための5つのステップのレシピ提供equals()方法を。コード形式のレシピは次のとおりです。

パブリッククラスEffectiveEquals {プライベートint値A; private int valueB; 。。。public boolean equals(Object o){if(this == o){//ステップ1:==テストを実行return true; } if(!(o instanceof EffectiveEquals)){//ステップ2:チェックのインスタンスがfalseを返す; } EffectiveEquals ee =(EffectiveEquals)o; //ステップ3:引数をキャストします//ステップ4:重要なフィールドごとに、それらが等しいかどうかを確認します//プリミティブの場合は==を使用します//オブジェクトの場合はequals()を使用しますが、// nullの場合も処理するようにしてください最初にee.valueA == valueA && ee.valueB == valueB;を返します。}。。。}

注:null instanceof EffectiveEquals falseと評価されるため、nullチェックを実行する必要はありません。

最後に、ステップ5では、equals()のコントラクトに戻り、equals()メソッドが反射的、対称的、推移的であるかどうかを自問してください。そうでない場合は、修正してください。

hashCode()の実装について

以下のためhashCode()の一般的な契約、Javadocは言います:

  • 「Javaアプリケーションの実行中に同じオブジェクトで複数回呼び出される場合は常にhashCode()、オブジェクトの等しい比較で使用される情報が変更されていない限り、メソッドは一貫して同じ整数を返す必要があります。この整数は、1から一貫性を保つ必要はありません。同じアプリケーションの別の実行へのアプリケーションの実行。
  • equals(Object)メソッドに従って2つのオブジェクトが等しい場合、2つのオブジェクトのhashCode()それぞれでメソッドを呼び出すと、同じ整数の結果が生成される必要があります。
  • 2つのオブジェクトがequals(java.lang.Objectメソッドに従って等しくない場合、2つのオブジェクトのhashCode()それぞれでメソッドを呼び出すと、異なる整数の結果が生成される必要はありません。ただし、プログラマーは、等しくないオブジェクトに対して個別の整数結果を生成すると、ハッシュテーブルのパフォーマンスが向上する可能性があることに注意する必要があります。」

適切に機能するhashCode()メソッドを作成することは困難です。問題のオブジェクトが不変でない場合、さらに困難になります。特定のオブジェクトのハッシュコードは、さまざまな方法で計算できます。最も効果的な方法は、オブジェクトのフィールドに基づいて数値を計算します。さらに、これらの値をさまざまな方法で組み合わせることができます。2つの一般的なアプローチは次のとおりです。

  • オブジェクトのフィールドを文字列に変換し、文字列を連結して、結果のハッシュコードを返すことができます
  • 各フィールドのハッシュコードを追加して、結果を返すことができます

他のより徹底的なアプローチが存在しますが、前述の2つのアプローチは、最も理解しやすく、実装しやすいものです。

Tony Sintesは、独立したコンサルタントであり、異種のエンタープライズシステムとトレーニングの橋渡しを専門とするコンサルティング会社であるFirst ClassConsultingの創設者です。ファーストクラスコンサルティング以外では、トニーはアクティブなフリーランスライターであり、Sams Teach Yourself Object-Oriented Programming in 21 Days(Sams、2001; ISBN:0672321092)の著者でもあります。

このトピックの詳細

  • ハッシュテーブルJavadocについては、

    //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

  • Vipan Singlaの「equals()およびhashCode()の実装」では、equals()メソッドとhashCode()メソッドのオーバーライドに関する詳細な説明を提供しています。

    //www.vipan.com/htdocs/hashcode_help.html

  • The Object.equals() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

  • The Object.hashCode() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

  • For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

    //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

  • For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

    //www.javaworld.com/channel_content/jw-apis-index.shtml

  • Want more? See the Java Q&A index page for the full Q&A catalog

    //www.javaworld.com/columns/jw-qna-index.shtml

  • ビジネスの最高の頭脳からの100以上の洞察に満ちたJavaのヒントについては、JavaWorldJavaのヒントのインデックスページにアクセスしてください。

    //www.javaworld.com/columns/jw-tips-index.shtml

  • JavaビギナーディスカッションでJavaの基本を学ぶ

    //forums.idg.net/[email protected]@.ee6b804

  • 以下のためにサインアップJavaWorldの無料の週刊コアのJavaメールマガジン

    //www.javaworld.com/subscribe

  • .netの姉妹出版物からIT関連の記事が豊富にあります。

このストーリー「Hashtables」は、もともとJavaWorldによって公開されました。