Java Map :: HashCode()衝突 - なぜですか?
質問
次のコードでは、2つのマップに対して同じハッシュコードが生成されます。アイデアはありますか?
import java.util.HashMap;
import java.util.Map;
public class Foo
{
@SuppressWarnings("unchecked")
public static void main (String[] args)
{
Map map;
map = new HashMap();
map.put("campaignId", 4770L);
map.put("location", "MINI_PROFILE");
map.put("active", "true");
map.put("lazy", true);
System.out.println(map.hashCode());
map = new HashMap();
map.put("campaignId", 4936L);
map.put("location", "MINI_PROFILE");
map.put("active", "true");
map.put("lazy", false);
System.out.println(map.hashCode());
}
}
結果は次のとおりです。
-1376467648
-1376467648
単にキー名を変更するだけで、コードが2つの異なるハッシュコードを生成するのに十分です。
解決
単に偶然の一致、私は疑う...ある バウンド 衝突であり、この場合、最初の値の関連する異なるビットが効果的に失われているように見えます。
ただし、違いはありません - ハッシュコードを使用するものは何でも しなければならない 衝突に対処します。
編集:ハッシュがたまたま計算される方法です。このコードは何が起こっているのかを示しています:
import java.util.*;
public class Test
{
@SuppressWarnings("unchecked")
public static void main (String[] args)
{
AbstractMap.SimpleEntry[] entries = {
new AbstractMap.SimpleEntry("campaignId", 4770L),
new AbstractMap.SimpleEntry("campaignId", 4936L),
new AbstractMap.SimpleEntry("lazy", true),
new AbstractMap.SimpleEntry("lazy", false)
};
for (AbstractMap.SimpleEntry entry : entries) {
System.out.println(entry + ": " + entry.hashCode());
}
}
}
結果:
campaignId=4770: -1318251287
campaignId=4936: -1318251261
lazy=true: 3315643
lazy=false: 3315617
したがって、1つのペアでは、最初のマップにはハッシュ26があります 以下 2番目のマップよりも、別のペアでは、最初のマップにはハッシュ26があります もっと 2番目のマップよりも。
AbstractMap
ハッシュ値(順序付けが無関係であることを確認する1つの方法)を合計するだけで、2つは同じハッシュコードになります。
それは本当にダウンしています Boolean.hashCode()
これは次のようになります:
return value ? 1231 : 1237;
... と Long.hashCode()
これは次のようになります:
return (int)(value ^ (value >>> 32));
彼らがたまたま選んだ価値を考えると Boolean.hashCode()
, 、 もしあなたの long
値はわずか26(または26 * 2^32離れています)で、同じことに遭遇します。
他のヒント
これは単なる偶然だと思います。 abstractMap#hashcode()のJavadocから:
マップのハッシュコードは、マップのエントリセット()ビューの各エントリのハッシュコードの合計であると定義されています。
エントリ#hashcode()の場合:
このマップエントリのハッシュコード値を返します。マップエントリEのハッシュコードは、次のように定義されています。
(e.getKey()==null ? 0 : e.getKey().hashCode()) ^
(e.getValue()==null ? 0 : e.getValue().hashCode())
したがって、マップのハッシュコードは、マップに含まれるキーと値の両方に基づいています。 2つのマップが同じハッシュコードを持っているという奇妙な状況を経験しているだけで、その理由はありません。
衝突が起こります。実際、HashCode()をオーバーライドして、常に0を返すことができます HashMap
そしてそれは正しいでしょう(それは多くの構造を作るでしょう スロー).
それは偶然ではありません。
文字列オブジェクトは両方で同じです。同じオブジェクトは同じハッシュコードを与えます。