Java HashMap调整大小

Question

假设我们有一些代码。

class WrongHashCode{
    public int code=0;

    @Override
    public int hashCode(){
        return code;
    }
}
public class Rehashing {
    public static void main(String[] args) {

        //Initial capacity is 2 and load factor 75%
        HashMap<WrongHashCode,String> hashMap=new HashMap<>(2,0.75f);

        WrongHashCode wrongHashCode=new WrongHashCode();
        //put object to be lost
        hashMap.put(wrongHashCode,"Test1");

        //Change hashcode of same Key object
        wrongHashCode.code++;

        //Resizing hashMap involved 'cause load factor barrier
        hashMap.put(wrongHashCode,"Test2");

        //Always 2
        System.out.println("Keys count " + hashMap.keySet().size());
    }
}

所以，我的问题是：为什么在调整哈希映射大小后（据我所知，这涉及到重新哈希键），我们仍然有2个键在keySet中，而不是1个（因为现有的KV对的键对象相同）？

- Vladyslav Nikolaiev

---

实际的调整大小在哪里？ - ACV

hashMap.keySet() 返回哈希映射中实际键的数量。因此，如果您放置了两个键，则始终会返回2。 - Natalia

你的代码无效。在插入键条目后，不允许修改它。 - user207421

@EJP，这是有意为之的。 - Vladyslav Nikolaiev

代码是无效的，因为它与HashMap文档中指定的要求冲突。编译器不必强制执行每一个Javadoc，JVM也不必如此。 - user207421

Answer 1

所以，我的问题是，为什么调整hashMap大小（据我理解涉及重新散列键）之后实际上并没有涉及重新散列键 - 至少在HashMap代码中除非特定情况下（见下文）。它涉及将它们重新定位到地图桶中。HashMap内部有一个Entry类，它具有以下字段：

final K key;
V value;
Entry<K,V> next;
int hash;

hash 字段是当调用 put(...) 方法时计算键的哈希码并存储下来的。这意味着，如果更改对象中的哈希码，则不会影响 HashMap 中的条目，除非您重新将其放入映射中。当然，如果更改了密钥的哈希码，则甚至无法在 HashMap 中找到该密钥，因为它具有与存储的哈希条目不同的哈希码。

即使我们已经为单个对象更改了哈希值，它仍然在地图中具有2个具有不同哈希字段的条目（由于现有KV对的关键对象相同），这是否正确？

因此，即使您已更改单个对象的哈希值，它也在具有2个条目的映射中，并且每个条目具有不同的哈希字段。

---

尽管如此，在 HashMap 内部存在代码，可能会在调整 HashMap 大小时重新对键进行哈希 - 可以参见 jdk 7（至少）中的包保护的 HashMap.transfer(...) 方法。 这就是为什么上面的 hash 字段不是 final 的原因。只有当 initHashSeedAsNeeded(...) 返回 true 以使用“替代哈希”时，才会使用它。以下设置启用备用哈希的条目数量阈值：

-Djdk.map.althashing.threshold=1

使用这个设置在虚拟机上，我可以在调整大小时再次调用hashcode()，但我无法将第二个put(...)视为覆盖。问题的一部分是HashMap.hash(...)方法正在对内部的hashseed进行异或运算，而当调整大小发生时，hashseed会被更改，但是在put(...)记录传入条目的新哈希码之后发生。

- Gray

---

我明白了。所以哈希值被缓存，然后仅在新的（根据负载因子扩展或收缩）哈希映射中重复使用，以查找条目的位置，而不是像我们在算法等课程中学到的那样重新计算哈希键。学到了新的重要知识。 - displayName

当然，这取决于HashMap的实现。我没有查看（例如）LinkedHashMap或其他Map的实现。虽然可以像@jthlborn提到的那样多次调用obj.hashcode()，但并没有什么规定Map实现不能这样做，尽管这样做可能很昂贵。 - Gray

这就是为什么建议使用不可变的键（或至少是equals/hashcode部分）。对于上面的示例，行为是实现定义的，并且在JVM之间可能会有所不同。这可能只是一个思考练习。 - rents

@Gray HashMap.tranfer？那是哪个版本的Java？ - Eugene

这是JDK 7中HashMap中的一个包方法，@Eugene。 - Gray

Answer 2

HashMap实际上缓存每个键的hashCode(因为计算一个键的hashCode可能很耗费时间)。所以，即使您更改了现有键的hashCode，与其链接的Entry在HashMap中仍然具有旧代码(因此在调整大小后放入“错误”的桶中)。

您可以在HashMap.resize()的jvm代码中看到这一点(或者在Java 6代码HashMap.transfer()中更容易看到)。

- jtahlborn

---

我无法确定为什么您链接了jdk-6源代码，而不是例如8？在那里根本没有这样的方法。 - Eugene

当我搜索HashMap的源代码时，@Eugene恰好是谷歌上的第一个结果。查看Java 8，答案仍然正确，尽管从源代码中解密有点困难。 - jtahlborn

@Eugene 添加Java 8链接。 - jtahlborn

Answer 3

我不知道为什么两个答案依赖于HashMap.tranfer的例子，因为在Java-8中根本不存在这个方法。因此，我将提供我的小输入，考虑到Java-8。

HashMap中的条目确实会被重新哈希，但不是你认为的那种方式。重新哈希基本上是重新计算已经由你提供的Key#hashcode；有一个方法可以做到这一点：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

基本上，当您计算哈希码时，HashMap会说 - “我不信任你足够”，它将重新哈希您的哈希码，并潜在地更好地传播位（实际上是前16位和后16位的XOR）。另一方面，当HashMap进行调整大小时，实际上意味着桶/存储空间的数量加倍;因为存储空间始终是2的指数 - 这意味着当前存储空间中的条目：可以保持在相同的存储桶中 或者 移动到一个偏移量为当前存储空间数量的存储桶。您可以在这个问题中找到一些详细信息。

因此，一旦发生重新调整大小，就没有额外的重新哈希;实际上，还考虑了一个更多的位，因此条目可能会移动或停留在原处。Gray的答案在这个意义上是正确的，每个Entry都有一个hash字段，只有在第一次放置该Entry时才会计算。

- Eugene

Answer 4

我无法找到明确记录，但是以一种改变其hashCode()的方式来更改键值通常会破坏HashMap。 HashMap将条目分配到b个桶中。您可以想象哈希h的键被分配给桶h％b。 当它接收到一个新条目时，它会计算出它属于哪个桶，然后如果该桶中已经存在相等的键，则添加它到桶中并删除任何匹配的键。

通过更改哈希码，对象wrongHashCode第二次被定向到另一个桶，并且不会找到或删除其第一个条目（通常情况下）。

简而言之，更改已插入键的哈希会破坏HashMap，此后得到的结果是不可预测的，但可能会导致(a)找不到键或(b)找到两个或多个相等的键。

- Persixty

Answer 5

因为HashMap将元素存储在内部表中，增加代码不会影响该表：

  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;
    }

和 addEntry

  void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

正如您所看到的table[bucketIndex] = new Entry (hash, ...)，因此即使您增加了代码，这里也不会反映出来。

尝试将字段代码更改为Integer，看看会发生什么？

- ACV

---

是的，但是在哈希表调整大小后，该表会被重建。 - Vladyslav Nikolaiev

@VladyslavNikolaiev。不是的。哪里写了它是重建的？我在代码中看不到这个。 - ACV

@ACV4，当元素数量达到特定值时，它会被调整大小。此后，内部表格的大小将加倍（重建）。 - Vladyslav Nikolaiev