9

Cormen et alのビデオによるアルゴリズムの紹介を行っており、いくつかのハッシュ関数について説明しています。Javaがデフォルトで使用するハッシュ関数を知りたいのですが、キーとして使用されるオブジェクトの種類によって、ハッシュ関数は実際に異なりますか？コレクションフレームワークに独自のハッシュアルゴリズムを記述できるAPIはありますか？

4

5 に答える 5

11

javaの各オブジェクトにpublic int hashCode()は、ハッシュを返すメソッドがあります。各オブジェクトは、そのメソッドをオーバーライドすることにより、独自の方法で自由に実装できます。メソッドがオーバーライドされていない場合は、デフォルトのObject#hashCodeメソッドが使用されます。

さまざまなオブジェクトのソースコードを見て、JDKでどのように実装されているかを確認できます。これは、たとえばStringのhashCodeです（1494行目）。

一部のコレクションでは、オブジェクトのhashCodeメソッドの上にハッシュのレイヤーを追加できます。たとえば、HashMapは、オブジェクトのhashCodeが適切に分散されていない場合に、パフォーマンスを向上させるためにこれを行います。

于 2012-08-16T16:28:57.333 に答える
2

どのクラスでもいつでもオーバーライドできます...

 @override
 public int hashCode()
 { 
 //new implementation 
 }

http://mindprod.com/jgloss/hashcode.html

デフォルトのhashCode（）メソッドは、オブジェクトの32ビット内部JVM（Java仮想マシン）アドレスをhashCodeとして使用します。

ただし、ガベージコレクション中にオブジェクトがメモリ内で移動された場合、hashCodeは一定のままです。このデフォルトのhashCodeはあまり役に立ちません。これは、HashMapでオブジェクトを検索するには、キーと値のペアが最初に提出されたのとまったく同じキーオブジェクトが必要だからです。

通常、検索に行くときは、元のキーオブジェクト自体はなく、キーのデータがいくつかあります。したがって、キーが文字列でない限り、ほとんどの場合、キークラスにhashCodeおよびequalsメソッドを実装する必要があります。

Object.hashCode（）はネイティブメソッドです。

于 2012-08-16T16:30:40.353 に答える
1

使用するオブジェクトの種類によって異なります。独自のクラスに実装するオブジェクトについては、デフォルトのhashCode（）メソッドをいつでもオーバーライドできます。

hashCode（）javadocに記載されているように、hashCode()との間のコントラクトに常に従う必要があることに注意してください。equals()

equals（Object）メソッドに従って2つのオブジェクトが等しい場合、2つのオブジェクトのそれぞれでhashCodeメソッドを呼び出すと、同じ整数の結果が生成される必要があります。

詳細については、このエントリをお読みください。

于 2012-08-16T16:28:35.330 に答える
0

Javaのすべてのクラスは、を継承します。そうすることで、を返すjava.lang.Objectメソッドを継承します。デフォルトのメソッドは、VMによって作成された（多かれ少なかれ）一意の値を返します（完全に正しくない場合でも、オブジェクトのメモリアドレスと考えてください）。独自のクラスを実装する場合、そのメソッドをオーバーライドして、必要なことを実行できます。ただし、メソッドとメソッドは一貫していることに注意する必要があります。また、一般にハッシュコードは一意ではないため、何をするにしても、異なるオブジェクトのハッシュコード間の衝突が予想されます。hashCode()inthashCodeequals

コレクションフレームワークは通常、このhashhCode()メソッドを使用してハッシュテーブルなどをハッシュします。他のライブラリの他のデータ構造が明示的なハッシュ関数を使用することも考えられますが、コレクションフレームワークでは発生しません。

于 2012-08-16T16:33:10.547 に答える
0

JavaのすべてのタイプにはhashCode()、のようにメソッドが定義されていObjectます。hashCode()を返しますint。そして、HashMap実装では、結果を再度ハッシュし、下位ビットのみを使用して0からsize-1の範囲にします。Sun JDKでは、サイズは常に2 xであり、xは整数であることに注意してください。

Javaライブラリはオープンソースであり、おそらく開発マシンにコピーがあります。

Sun JDK 6では、上記の2番目のハッシュは

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

hashCode()興味のあるクラスの関数を見ると、最初のハッシュを見つけることができます。

于 2012-08-16T16:30:50.453 に答える