深くhashcode方法
3643 ワード
なぜHashCodeはオブジェクトにとってこんなに重要なのですか?
オブジェクトのHashCodeは単純なHashアルゴリズムの実装であるが,それは実際の複雑なHashアルゴリズムに比べて真のアルゴリズムとは呼べないが,それがどのように実現されるかは,プロセスだけではない.
シーケンサのプログラミングレベルの問題は、あなたのオブジェクトがアクセスしていることに関係する非常に重要な関係です.可能性があります.HashCodeによってオブジェクトへのアクセスが低下し、何百倍ものパフォーマンスが低下する可能性があります.
いいえ.
まず、JAVAにおける2つの重要なデータ構造:HashMapとHashtableは、継承関係の違い、valueの制約条件(nullを許可するかどうか)の違い、スレッドの安全性など、大きな違いがあるが、実現原理的には一致している.したがって、Hashtableのみで説明します.
Javaでは、データへのアクセスの性能は、一般的には頭打ち配列であるが、データ量がやや大きいコンテナ選択では、Hashtableが配列よりも性能の高いクエリー速度を持つことになる.具体的な原因は以下の内容を見てください.
Hashtableは、データを格納際に、keyのオブジェクトであるHashCodeと0 x 7 FFFFFFFとを先に操作するのが一般的である、1つのオブジェクトのHashCodeは負数であることができるため、操作後に正の整数であることを保証することができる.次に、Hashtableの長さで型を取り、値オブジェクトのHashtable内のインデックスを得る. 、
この値オブジェクトはHashtableのindex番目の位置に直接配置する、書き込みについては配列と同様に、1つのオブジェクトをその中のindex番目の位置に配置するが、クエリであれば、同じアルゴリズムを経て、Hashtableはkeyで直接indexを得ることができ、indexからこの値オブジェクトを取得するが、配列はループ比較を行う.したがって、データ量が少し大きい場合、Hashtableのクエリはデータよりもパフォーマンスが向上します.
異なるオブジェクトには異なるhashcodeがあるが,異なるhashCodeは長さとの取り残しを経て,同じindexを生成する可能性が高い.
極端な場合、同じインデックスを生成するオブジェクトが大量に存在する.これがHashtableのパフォーマンスに関する最も重要な問題です.
Hash衝突.
一般的なHash衝突は、異なるkeyオブジェクトが最終的に同じインデックスを生成することであるが、非常にまれなHash衝突は、1組のオブジェクトの個数がint範囲を大きく超え、HashCodeの長さがint範囲内にしかない場合、同じグループの要素が同じHashCodeであることに違いない.このように、いずれにしても同じインデックスがある.もちろん
このような極端なケースは極めて珍しく、しばらく考慮しなくてもよいが、同じHashCodeが型取りされると、同じインデックスが生成されるか、異なるオブジェクトが同じHashCodeを有し、もちろん同じインデックスが生成される.
実際に設計する良いHashTableは、一般的に各要素を比較的平均的に分布するが、Hashtableの長さは常に実際の要素の個数より一定の割合で自己増加する(充填因子は一般的に0.75)程度であるため、多くのインデックス位置は1つのオブジェクトしかなく、少ない位置にはいくつかの要素がある.したがって、Hashtableの各位置には1つのチェーンテーブルが格納、1つのオブジェクトのみが位置である場合、チェーンテーブルには1つのヘッダノード(Entry)しかなく、Entryのnextはnullとなる.次にhashCode,key,value属性はその位置のオブジェクトのHashCode,key,value(オブジェクト自体)を保存する、同じインデックスのオブジェクトが入ってくるとチェーンテーブルの次のノードに入る.同じインデックスに複数のオブジェクトがある場合、HashCodeとkeyに基づいてチェーンテーブルにクエリーのkeyと一致するオブジェクトを見つけることができます.
以上から分かるように、HashMapとHashtableのアクセス性能に重大な影響を及ぼすのは、まず、このデータ構造中の要素ができるだけ大きく異なるHashCodeを有する可能性があることである.これは、異なるHashCodeが異なるindexを生じることを保証するものではないが、同じHashCodeが必ず同じindexを生じ、それによって影響を及ぼす
Hash衝突.
1つの象に対して、多くの属性を持つ場合、すべての属性をハッシュに参加するのは明らかに不器用な設計である.オブジェクトのHashCode()メソッドは、equals比較のように、多くのオブジェクトがハッシュに関与する場合、ほとんどどこにでも自動的に呼び出されるためである.操作定数が大きくなる.したがって、ハッシュに参加するプロパティを選択することは、プログラミングレベルの問題です.
実現から言えば、一般的なHashCodeの方法はこうなります.
このメソッドを呼び出すたびに、メソッド内のハッシュに参加するオブジェクトに対してHashCodeの演算を再計算し、オブジェクトの属性が変更されていない場合でも毎回計算するので、現在のハッシュコードをキャッシュするタグを設定すると、ハッシュに参加するオブジェクトが変更された場合に再計算されます.そうしないと、キャッシュのhashCodeが呼び出されます.これにより、パフォーマンスが大幅に向上します.もちろんjavaオブジェクトのこのような状態特性については,前後の2つのオブジェクトのどちらの属性が変化したかを直接知ることは難しい.
デフォルトの実装では、オブジェクトの内部アドレスを整数に変換してHashCodeとして使用します.これにより、オブジェクトごとに異なるHasCodeが保証されます.オブジェクトの内部アドレスが異なるに違いありません(くだらない話).
しかしjava言語ではプログラマにオブジェクトの内部アドレスを取得させることはできないため,オブジェクトごとに異なるHashCodeを生成させるには多くの研究可能な技術がある.
複数の属性から平均分布を持つhashCodeの属性をサンプリングすると、これは性能と多様性が矛盾するところであり、すべての属性がハッシュに参加すれば、もちろんhashCodeの多様性は大幅に向上するが、性能を犠牲にし、少量の属性のみがハッシュをサンプリングすると、極端な状況では大量のハッシュ衝突が発生する.人"のプロパティでは、名前や生年月日ではなく性別を使用すると、オプションのhashcode値が2つ以上しかなく、ハッシュ競合が半分以上発生します.したがって、可能な場合、HashCodeを生成するためにシーケンスを特定することは良い選択です(もちろん、シーケンスを生成するパフォーマンスは、すべての属性がハッシュに関与するパフォーマンスよりも高い場合になります.そうでなければ、すべての属性で直接ハッシュするほうがいいです).
どのようにHashCodeの性能と多様性に対して1つの平衡を求めて、関連するアルゴリズムの設計の本を参考にすることができて、実は必ずしも非常に優秀であることを要求しないで、できるだけハッシュ値の集積を減らすことができる限り.重要なのはHashCodeが私たちのプログラム性能に重要な影響を及ぼしていることを覚えておくべきで、プログラム設計の時に常に注意しなければならない.
オブジェクトのHashCodeは単純なHashアルゴリズムの実装であるが,それは実際の複雑なHashアルゴリズムに比べて真のアルゴリズムとは呼べないが,それがどのように実現されるかは,プロセスだけではない.
シーケンサのプログラミングレベルの問題は、あなたのオブジェクトがアクセスしていることに関係する非常に重要な関係です.可能性があります.HashCodeによってオブジェクトへのアクセスが低下し、何百倍ものパフォーマンスが低下する可能性があります.
いいえ.
まず、JAVAにおける2つの重要なデータ構造:HashMapとHashtableは、継承関係の違い、valueの制約条件(nullを許可するかどうか)の違い、スレッドの安全性など、大きな違いがあるが、実現原理的には一致している.したがって、Hashtableのみで説明します.
Javaでは、データへのアクセスの性能は、一般的には頭打ち配列であるが、データ量がやや大きいコンテナ選択では、Hashtableが配列よりも性能の高いクエリー速度を持つことになる.具体的な原因は以下の内容を見てください.
Hashtableは、データを格納際に、keyのオブジェクトであるHashCodeと0 x 7 FFFFFFFとを先に操作するのが一般的である、1つのオブジェクトのHashCodeは負数であることができるため、操作後に正の整数であることを保証することができる.次に、Hashtableの長さで型を取り、値オブジェクトのHashtable内のインデックスを得る. 、
index = (o.hashCode() &0x7FFFFFFF)%hs.length;この値オブジェクトはHashtableのindex番目の位置に直接配置する、書き込みについては配列と同様に、1つのオブジェクトをその中のindex番目の位置に配置するが、クエリであれば、同じアルゴリズムを経て、Hashtableはkeyで直接indexを得ることができ、indexからこの値オブジェクトを取得するが、配列はループ比較を行う.したがって、データ量が少し大きい場合、Hashtableのクエリはデータよりもパフォーマンスが向上します.
異なるオブジェクトには異なるhashcodeがあるが,異なるhashCodeは長さとの取り残しを経て,同じindexを生成する可能性が高い.
極端な場合、同じインデックスを生成するオブジェクトが大量に存在する.これがHashtableのパフォーマンスに関する最も重要な問題です.
Hash衝突.
一般的なHash衝突は、異なるkeyオブジェクトが最終的に同じインデックスを生成することであるが、非常にまれなHash衝突は、1組のオブジェクトの個数がint範囲を大きく超え、HashCodeの長さがint範囲内にしかない場合、同じグループの要素が同じHashCodeであることに違いない.このように、いずれにしても同じインデックスがある.もちろん
このような極端なケースは極めて珍しく、しばらく考慮しなくてもよいが、同じHashCodeが型取りされると、同じインデックスが生成されるか、異なるオブジェクトが同じHashCodeを有し、もちろん同じインデックスが生成される.
実際に設計する良いHashTableは、一般的に各要素を比較的平均的に分布するが、Hashtableの長さは常に実際の要素の個数より一定の割合で自己増加する(充填因子は一般的に0.75)程度であるため、多くのインデックス位置は1つのオブジェクトしかなく、少ない位置にはいくつかの要素がある.したがって、Hashtableの各位置には1つのチェーンテーブルが格納、1つのオブジェクトのみが位置である場合、チェーンテーブルには1つのヘッダノード(Entry)しかなく、Entryのnextはnullとなる.次にhashCode,key,value属性はその位置のオブジェクトのHashCode,key,value(オブジェクト自体)を保存する、同じインデックスのオブジェクトが入ってくるとチェーンテーブルの次のノードに入る.同じインデックスに複数のオブジェクトがある場合、HashCodeとkeyに基づいてチェーンテーブルにクエリーのkeyと一致するオブジェクトを見つけることができます.
以上から分かるように、HashMapとHashtableのアクセス性能に重大な影響を及ぼすのは、まず、このデータ構造中の要素ができるだけ大きく異なるHashCodeを有する可能性があることである.これは、異なるHashCodeが異なるindexを生じることを保証するものではないが、同じHashCodeが必ず同じindexを生じ、それによって影響を及ぼす
Hash衝突.
1つの象に対して、多くの属性を持つ場合、すべての属性をハッシュに参加するのは明らかに不器用な設計である.オブジェクトのHashCode()メソッドは、equals比較のように、多くのオブジェクトがハッシュに関与する場合、ほとんどどこにでも自動的に呼び出されるためである.操作定数が大きくなる.したがって、ハッシュに参加するプロパティを選択することは、プログラミングレベルの問題です.
実現から言えば、一般的なHashCodeの方法はこうなります.
return Attribute1.HashCode() + Attribute1.HashCode()..[+super.HashCode()]。
このメソッドを呼び出すたびに、メソッド内のハッシュに参加するオブジェクトに対してHashCodeの演算を再計算し、オブジェクトの属性が変更されていない場合でも毎回計算するので、現在のハッシュコードをキャッシュするタグを設定すると、ハッシュに参加するオブジェクトが変更された場合に再計算されます.そうしないと、キャッシュのhashCodeが呼び出されます.これにより、パフォーマンスが大幅に向上します.もちろんjavaオブジェクトのこのような状態特性については,前後の2つのオブジェクトのどちらの属性が変化したかを直接知ることは難しい.
デフォルトの実装では、オブジェクトの内部アドレスを整数に変換してHashCodeとして使用します.これにより、オブジェクトごとに異なるHasCodeが保証されます.オブジェクトの内部アドレスが異なるに違いありません(くだらない話).
しかしjava言語ではプログラマにオブジェクトの内部アドレスを取得させることはできないため,オブジェクトごとに異なるHashCodeを生成させるには多くの研究可能な技術がある.
複数の属性から平均分布を持つhashCodeの属性をサンプリングすると、これは性能と多様性が矛盾するところであり、すべての属性がハッシュに参加すれば、もちろんhashCodeの多様性は大幅に向上するが、性能を犠牲にし、少量の属性のみがハッシュをサンプリングすると、極端な状況では大量のハッシュ衝突が発生する.人"のプロパティでは、名前や生年月日ではなく性別を使用すると、オプションのhashcode値が2つ以上しかなく、ハッシュ競合が半分以上発生します.したがって、可能な場合、HashCodeを生成するためにシーケンスを特定することは良い選択です(もちろん、シーケンスを生成するパフォーマンスは、すべての属性がハッシュに関与するパフォーマンスよりも高い場合になります.そうでなければ、すべての属性で直接ハッシュするほうがいいです).
どのようにHashCodeの性能と多様性に対して1つの平衡を求めて、関連するアルゴリズムの設計の本を参考にすることができて、実は必ずしも非常に優秀であることを要求しないで、できるだけハッシュ値の集積を減らすことができる限り.重要なのはHashCodeが私たちのプログラム性能に重要な影響を及ぼしていることを覚えておくべきで、プログラム設計の時に常に注意しなければならない.