6

私はHashMapキーとを格納するためにJavaで使用していますObject <Key,Object>。そして、ハッシュマップの衝突について読みましたが、リンクリストを使用して回避しようとしています。

オンラインで検索しましたが、これを行う方法の例が見つかりませんでした。

リンクされたリストでハッシュマップを実装するオンラインリソースを教えてもらえますか?

4

2 に答える 2

8

Java HashMap はすでにこの方法で衝突を処理しています。hashCode()キーのandequals()メソッドをオーバーライドして実装していることを確認するだけです。

それぞれhash codeが特定の「バケット」にマップされます。各バケットには、衝突の場合のリンクされたリストが含まれています。

衝突を回避 (または最小限に抑える) 唯一の方法は、HashMap 全体で可能な限り最適な値の分布を作成するハッシュ関数を作成することです。HashMap の密度と の品質によってはhash code、衝突はほとんど避けられないため、2 つのメソッドをオーバーライドする必要があります。

編集：OPは例を求めました

2 つのメソッドをオーバーライドするには、次のようにします。

public class MyObject {
  String var1;
  int var2;

  //...
  public boolean equals(Object obj) {
    if(obj == null) return false;
    if(this == obj) return true;      // Reference equality
    if(!(obj instanceof MyObject)) return false;
    MyObject myObj = MyObject(obj);
    return (var1.equals(myObj.var1)) && (var2 == myObj.var2); 
  }
  public int hashCode {
     return var1.hashCode() ^ var2;
  }
}
于 2012-07-30T18:58:58.910 に答える
5

衝突は、キーと同じものを使用した場合、または同じハッシュ コードとequalsobjectを持つキーとして異なるものを使用した場合にのみ発生します。object

HashMap を正しく使用するには、キー クラスに hashCode と equals メソッドを正しく実装する必要があります。オブジェクトのドキュメントとこの記事を読んでください。

キーごとに複数のオブジェクトを格納する場合は、リストの HashMap を作成する必要があります。

これは簡単な例です:

HashMap<Object, List<Object>> map = new HashMap<Object, List<Object>>();
map.put(key, new LinkedList<Object>);
map.get(key).add(object);
于 2012-07-30T19:02:29.537 に答える