10

JavaのHashMapがどのように機能するかをよく理解していることを確認するための簡単な質問。

コードの例を次に示します。

//String key = new String("key");
//String val = new String("value");
String key = "key";
String val = "value";

HashMap map = new HashMap();
map.put(key, val);

System.out.println("hashmap object created. Its key hashcode = "+key.hashCode());
// the hashcode is 106079
System.out.println("hashmap object value for key = "+map.get(key));

// Let's store using a key with same hashcode
Integer intkey = new Integer(106079);
val = "value2";
map.put(intkey, val);
System.out.println("hashmap object created. Its intkey hashcode = "+intkey.hashCode());
// this returns 106079 once again. So both key and intkey have the same hashcode

// Let's get the values
System.out.println("hashmap object value for intkey = "+map.get(intkey));
System.out.println("hashmap object value for key = "+map.get(key));

返される値は期待どおりです。舞台裏では、HashMap は次のように機能することを読みました。

  1. キー/値を取得します。
  2. キーからハッシュコードを作成します。
  3. キーと値のオブジェクトをバケットに保存します (私の場合、バケット番号 106079)

2番目のものについても同じです。

  1. 同じバケット内に保存しますが、これはこの時点で LinkedList であるため、「次に利用可能な割り当て」に保存すると思います。

それを取得するには：

  1. キーを取得し、ハッシュコードを取得し、
  2. バケツを見て、
  3. 次に、LinkedList の最初の要素のキーを見て、
  4. 次に、渡されたキーと要素からのキーが一致するかどうかを確認し、一致しない場合は次のように値を取得できるまで続けます。

この概念を正しく理解していますか?

どうもありがとう！

編集：

- Java HashMap はエントリを内部的にどのように保存するのですか? - Java HashMap は同じハッシュ コードを持つ異なるオブジェクトをどのように処理しますか?

と：

  • それほど多くの「バケツ」があるべきではありません
  • バケットはエントリと同じではありません。バケットは、同じバケットを共有するすべてのエントリの論理的なコレクションです# (Java の場合は、キーの hashCode() の関数です)。他の回答で述べたように、バケット オーバーフローは、必ずしもリストではなく、いくつかの方法で実装できます。
  • 他の既存の衝突解決があります: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution
  • オブジェクトの equals メソッドを使用して、同じバケットからオブジェクトを比較および取得します。
4

3 に答える 3

3

また、あなたが言及したようにリンクリストを利用するだけでなく、 HashMapがハッシュコードの衝突解決を実装できる方法がいくつかあることに注意してください

LinkedListJava の HashMap 実装は、戦略を使用して同じ値を持つキー値を処理するだけではありませんkey.hashCode()。

また、この記事を読むことをお勧めします

于 2013-10-28T20:52:13.120 に答える
1

はい、あなたの理解は正しいです。1 つのバケットに多くのハッシュコードが割り当てられていることに注意してください。新しいHashMapバケットには全部で 16 個のバケットがあり、それぞれに合計 2 32 /16 = 2 28のハッシュコードが割り当てられています。

于 2013-10-28T20:42:15.177 に答える
0

あなたの理解は問題ありませんが、いくつかの実装があることを考慮してください。HashMap が値を格納するために使用する実際のハッシュコードは 106079 ではない可能性があります。1 つの実装 (java-6-openjdk) を次に示します。

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

hash以下で構成されるメソッドに注意してください。

/**
 * 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);
}

したがって、この JVM の例では、ハッシュとして 106079 を使用しません。これは、HashMap がハッシュを再作成して「強化」するためです。

それが役立つことを願っています

于 2013-10-28T20:50:47.437 に答える