HashMap 内部是如何工作的

Question

HashMap objHashMap = new HashMap();

objHashMap.put("key1", "Value1");
objHashMap.put("key1", "Value2");

System.out.println(objHashMap.get("key1"));

上面的代码显示了“Value2”的方式和原因

Answer 1

检查 这个

\n\n

/**\n* Associates the specified value with the specified key in this map. If the\n* map previously contained a mapping for the key, the old value is\n* replaced.\n*\n* @param key\n*            key with which the specified value is to be associated\n* @param value\n*            value to be associated with the specified key\n* @return the previous value associated with <tt>key</tt>, or <tt>null</tt>\n*         if there was no mapping for <tt>key</tt>. (A <tt>null</tt> return\n*         can also indicate that the map previously associated\n*         <tt>null</tt> with <tt>key</tt>.)\n*/\npublic V put(K key, V value) {\n    if (key == null)\n    return putForNullKey(value);\n    int hash = hash(key.hashCode());\n    int i = indexFor(hash, table.length);\n    for (Entry<K , V> e = table[i]; e != null; e = e.next) {\n        Object k;\n        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {\n            V oldValue = e.value;\n            e.value = value;\n            e.recordAccess(this);\n            return oldValue;\n        }\n    }\n\n    modCount++;\n    addEntry(hash, key, value, i);\n    return null;\n}\n

\n\n

让我们一一记下步骤：

\n\n

1）首先，检查key对象是否为null。如果 key 为 null，则 value 存储在 table[0] 位置。因为 null 的哈希码始终为 0。

\n\n

2) 然后下一步，通过调用 key\xe2\x80\x99s 的哈希码，调用其 hashCode() 方法计算哈希值。该哈希值用于计算存储 Entry 对象的数组中的索引。JDK 设计者很好地假设可能存在一些写得不好的 hashCode() 函数，它们可能返回非常高或非常低的哈希码值。为了解决这个问题，他们引入了另一个 hash() 函数，并将 object\xe2\x80\x99s 哈希码传递给这个 hash() 函数，以使哈希值在数组索引大小的范围内。

\n\n

3）现在调用indexFor(hash, table.length)函数来计算存储Entry对象的确切索引位置。

\n\n

4）主要部分来了。现在，我们知道两个不相等的对象可以具有相同的哈希码值，那么两个不同的对象将如何存储在同一数组位置[称为存储桶]。\n答案是 LinkedList。如果您还记得的话，Entry 类有一个属性 \xe2\x80\x9cnext\xe2\x80\x9d。该属性始终指向链中的下一个对象。这正是 LinkedList 的行为。

\n\n

因此，为了防止发生碰撞，Entry 对象以 LinkedList 形式存储。当一个Entry对象需要存储在特定的索引中时，HashMap会检查是否已经存在一个Entry？如果不存在条目，则 Entry 对象存储在此位置。

\n\n

如果计算索引上已经有一个对象，则检查其下一个属性。如果为null，则当前Entry对象成为LinkedList中的下一个节点。如果 next 变量不为 null，则继续执行该过程，直到 next 被评估为 null。

\n\n

如果我们添加另一个具有与之前输入的键相同的值对象会怎样？从逻辑上讲，它应该替换旧值。它是如何完成的？好吧，在确定 Entry 对象的索引位置后，在计算出的索引上迭代 LinkedList 时，HashMap 对每个 Entry 对象的键对象调用 equals 方法。LinkedList 中的所有这些 Entry 对象都将具有相似的哈希码，但 equals() 方法将测试真正的相等性。如果 key.equals(k) 为 true，则两个键都被视为相同的键对象。这将导致仅替换 Entry 对象内的值对象。

\n\n

通过这种方式，HashMap保证了键的唯一性。

\n