2012-03-19 13 views
6

Hashtableには、ペアごとに同じキーと値を持つエントリのみが含まれていると、JavaのHashtable#hashCode()のデフォルト実装が壊れているのだろうかと思います。Javaハッシュテーブル#hashCode()の実装が壊れていますか?

例えば次のアプリケーションを参照してください。

public class HashtableHash { 
    public static void main(final String[] args) { 
     final Hashtable<String, String> ht = new Hashtable<String, String>(); 

     final int h1 = ht.hashCode(); 
     System.out.println(h1); // output is 0 

     ht.put("Test", "Test"); 

     final int h2 = ht.hashCode(); 
     System.out.println(h2); // output is 0 ?!? 

     // Hashtable#hashCode() uses this algorithm to calculate hash code 
     // of every element: 
     // 
     // h += e.key.hashCode()^e.value.hashCode() 
     // 
     // The result of XOR on identical hash codes is always 0 
     // (because all bits are equal) 

     ht.put("Test2", "Hello world"); 

     final int h3 = ht.hashCode(); 
     System.out.println(h3); // output is some hash code 
    } 
} 

空のハッシュテーブルのハッシュコードがキー​​持つエントリ後0であり、値​​ハッシュコード依然として Hastableに追加されています0

問題が

を以下のようにハッシュテーブルの hashCode()方法のすべてのエントリのハッシュコードが計算され、ハッシュコードに追加されたことです
h += e.key.hashCode()^e.value.hashCode() 

ただし、同一のハッシュコード(同じ文字列の場合)の場合はXORは常に0です。したがって、同一のキーと値を持つエントリは、ハッシュテーブルのハッシュコードの一部ではありません。

この実装は、実際にHashtableが変更されたため、imhoが壊れています。キーと値が同一であるかどうかは関係ありません。

+2

正当な質問であり、誰かに何か問題を救うことができるので、なぜこれが下落したのだろうと思います。私はこの行動によって引き起こされたバグを見つけるために何時間も探してきました。 –

+2

オブジェクトが異なるため、別のハッシュコードに頼ることはできません。 2つの全く異なるオブジェクトを追加し、hashCodeも同じままにすると、hashCodeも壊れていると思いますか?その場合、可能なオブジェクトのユニバースが2^32より大きい場合、すべての可能なハッシュコードの実装が壊れます。 – Voo

+0

これは疑問よりも観察の方が多いです。 (私のdownvoteではありませんが) –

答えて

6

hashCodeのマニュアルから。

それはない 2つのオブジェクトが 等しい(java.lang.Object上位)の方法に従って等しくない場合には、別個の整数結果を生成しなければならない 二つのオブジェクトのそれぞれにhashCodeメソッドを呼び出すことが必要。 ただし、等しくないオブジェクトに対して別の 整数結果を生成すると、 ハッシュテーブルのパフォーマンスが向上する可能性があります。

つまり、おそらく実装不良です。壊れた - 仕様通りではありません。

5

これは壊れていない、それは設計されて広告として動作しています。 2つのMapが等しいハッシュコードは、2つのハッシュコードが等しいことを必要としません。

1

hashCodeの唯一の要件は、2つのオブジェクトが等しい場合、それらのハッシュコードが等しくなければならないということです。したがって、

public int hashCode() { 
    return 123; 
} 

は、最適ではありませんが、完全に有効です。

関連する問題