Hashmap and how this works behind the scene

This question already has an answer here:

How does Java HashMap store entries internally 3 answers

---

Please also note, there are several ways HashMap can implement hash codes collision resolution, not only utilizing linked list as you mentioned

Java's HashMap implementation does not only use LinkedList strategy to handle key-values with same key.hashCode() values.

Also, you may want to read this article

---

Yes, your understanding is correct. Just note that a single bucket is assigned many hashcodes: in a fresh HashMap there are altogether 16 buckets, each assigned a total of 232/16 = 228 hashcodes.

---

Your understandings are OK, but take into account that there are several implementations. The actual hashcode HashMap uses to store the value may not be 106079. Here's one implementation (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;
}

Notice the hash method, which consists of the following:

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

So in this JVM's example, it does not use 106079 as a hash, since HashMap recreates a hash to 'harden' it.

I hope that helps

链接地址: http://www.djcxy.com/p/75136.html

上一篇: Conda和Python模块

下一篇: 散列图以及它如何在幕后工作