哈希图及其在幕后的工作方式

Question

快速问题，以确保我很好地理解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）

第二个也一样。

4. 将其存储在同一个存储桶中，但由于此时这是一个 LinkedList，我想将其存储在"下一个可用分配"中。

要获得它：

1. 拿起钥匙，获取哈希码，
2. 看看水桶，
3. 然后查看链接列表中第一个元素的键，
4. 然后检查键是否传递和元素中的键匹配，如果没有，则继续下一个，依此类推，直到可以检索值。

我是否正确理解了这个概念？

非常感谢！

编辑：

非常感谢，所以要完成： - Java HashMap 如何在内部存储条目 - Java HashMap 如何处理具有相同哈希代码的不同对象？

和：

• 不应该有那么多"桶"
• 存储桶与条目不同。存储桶是共享同一存储桶#的所有条目的逻辑集合（在 Java 案例中是键的 hashCode（） 的函数）。如其他答案中所述，存储桶溢出可以通过多种方式实现，不一定在列表中实现。
• 还有其他现有的冲突解决方案：http://en.wikipedia.org/wiki/Hash_table#Collision_resolution
• 它使用 Object 的 equals 方法来比较和检索同一存储桶中的对象。

Answer 1

另请注意，HashMap 可以通过多种方式实现哈希码冲突解决，而不仅仅是您提到的利用链表

Java的HashMap实现不仅使用LinkedList策略来处理具有相同key.hashCode()值的键值。

另外，您可能想阅读这篇文章

Answer 2

是的，你的理解是正确的。请注意，单个存储桶被分配了许多哈希代码：在一个新的HashMap中总共有 16 个存储桶，每个存储桶总共分配了 2³²/16 = 2²⁸ 个哈希代码。

Answer 3

您的理解还可以，但要考虑到有多种实现。哈希映射用于存储值的实际哈希码可能未106079。下面是一个实现（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重新创建了一个哈希来"强化"它。

我希望这有所帮助