4

私はを使用していますが、衝突の場合にメソッドHashMapがどのように機能するかについて直接的な答えを得ることができませんでした。get()

n > 1オブジェクトが同じキーに配置されるとしましょう。それらはに保存されていLinkedListますか?そのキーに配置された最後のオブジェクトのみが存在するように上書きされていますか?他の衝突方法を使用していますか?

それらがに配置されている場合、LinkedListそのリスト全体を取得する方法はありますか?そうでない場合、これを実行できるJava用の組み込みマップは他にありますか?

私の目的では、衝突があるかのように、個別のチェーンが理想的です。リストを調べて、リスト内のすべてのオブジェクトに関する情報を取得できる必要があります。Javaでこれを行うための最良の方法は何でしょうか?

ご協力ありがとうございます!

4

5 に答える 5

8

Hashmap.put()のドキュメントには、「指定された値をこのマップ内の指定されたキーに関連付けます。マップに以前にキーのマッピングが含まれていた場合、古い値が置き換えられます」と明記されています。

キーに関連付けられたオブジェクトのリストが必要な場合は、リストを値として保存します。

「衝突」は通常、HashMapの内部動作を指し、2つの異なる値に同じキーを使用するのではなく、2つのキーが同じハッシュ値を持つことに注意してください。

于 2012-10-18T01:43:20.597 に答える
7

そのキーに配置された最後のオブジェクトのみが存在するように上書きされていますか?

はい、同じキーで複数の値を入力していると仮定します(によるとObject.equals、ではありません)。これはjavadocObject.hashCodeで指定されています。Map.put

マップに以前にキーのマッピングが含まれていた場合、古い値は指定された値に置き換えられます。

ListMultimapキーを複数の値にマップする場合は、ArrayListMultimap特に、キーを値のリストにマップするGuavaのようなものを使用する方がよいでしょう。(開示:私はGuavaに貢献します。)サードパーティのライブラリを許容できない場合は、実際にはが必要ですがMap<Key, List<Value>>、少し扱いに​​くい場合があります。

于 2012-10-18T01:43:23.580 に答える
3

n>1個のオブジェクトが同じキーに配置されるとしましょう。それらはリンクリストに保存されていますか?そのキーに配置された最後のオブジェクトのみが存在するように上書きされていますか?他の衝突方法を使用していますか?

同じキーに単一のインスタンスが存在する可能性があるため、最後のインスタンスが前のインスタンスをオーバーライドします

Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there

連鎖は、異なるキーに対して同じハッシュが変わる場所で発生します


見る

于 2012-10-18T01:43:08.997 に答える
0

引用: 「n > 1 のオブジェクトが同じキーに配置されるとしましょう。それらはリンクされたリストに格納されていますか?そのキーに配置された最後のオブジェクトだけがそこに存在するように上書きされていますか?それらは他の衝突方法を使用していますか?」

はい、ハッシュマップがこのキーの下に何かを含んでいた場合、それは上書きされます。

それを処理する独自のクラスを実装するか、より簡単に HashMap> を使用できます。ここで、K はキー オブジェクトであり、V はオブジェクト値です。最後のソリューションでは、map.get(K) を実行すると、リストまたは選択した実装 (つまり、ArrayList) が取得されるため、この実装のすべてのメソッドを使用でき、おそらく要件を満たすことに注意してください。たとえば、Arraylist を使用した場合、サイズ、trimToSize、removeRange などがあります。

于 2012-10-18T02:02:14.667 に答える
-1

Java でのハッシュの衝突解決は、連鎖に基づいていません。私の理解では、JDK はオープン アドレス指定の最良の方法の 1 つであるダブル ハッシュを使用します。したがって、ハッシュ スロットに関連付けられるリストはありません。

ハッシュ関数が同じキーに解決されるオブジェクトをリストに入れることができ、このリストをテーブル/マップで更新できます。

package hashing;

import java.util.HashMap;
import java.util.Map;

public class MainAnimal {

    /**
     * @param args
     */
    public static void main(String[] args) {

        Animal a1 = new Animal(1);
        Animal a2 = new Animal(2);

        Map<Animal, String> animalsMap = new HashMap<Animal, String>();

        animalsMap.put(a1,"1");
        animalsMap.put(a2,"2");

        System.out.println(animalsMap.get(a1));

        Map<String, Integer> map = new HashMap<String, Integer>();
        map.put("a", 1);
        map.put("a", 2);// it overrides 1 and puts 2 there

        System.out.println(map.get("a"));       

    }

}


class Animal {

    private int index = 0;

    Animal(int index){
        this.index = index;
    }

    public boolean equals(Object obj){
        if(obj instanceof Animal) {
            Animal animal = (Animal) obj;
            if(animal.getIndex()==this.getIndex())
                return true;
            else
                return false;
        }
        return false;
    }

    public int hashCode() {
        return 0;
    }

    public int getIndex() {
        return index;
    }

    public void setIndex(int index) {
        this.index = index;
    }


}

上記のコードでは、2 つの異なるものを示しています。

ケース 1 - 同じハッシュキーに解決される 2 つの異なるインスタンス ケース 2 - 2 つの異なるエントリのキーとして機能する 2 つの同じインスタンス。

動物インスタンス、a1 と a2 は同じキーに解決されます。しかし、それらはオーバーライドされません。ハッシュ メカニズムは、ハッシュ スロットを調べて、エントリを別のスロットに配置します。

2 番目のケースでは、キーは同じハッシュ キーに解決され、equals メソッドも満たされます。したがって、オーバーライドが発生します。

動物クラスで equals メソッドをこのようにオーバーライドすると、

    public boolean equals(Object obj){
//      if(obj instanceof Animal) {
//          Animal animal = (Animal) obj;
//          if(animal.getIndex()==this.getIndex())
//              return true;
//          else
//              return false;
//      }
//      return false;
        return true;
    }

オーバーライドが発生します。動作は同じインスタンスを使用するようなものです。a1 と a2 は同じバケットにあり、equals も true を返すためです。

于 2012-10-18T02:05:29.783 に答える