Java HashMap 调整大小

问题描述

假设我们有一些代码

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

所以，我的问题是为什么在调整 hashMap 的大小后(据我所知，这涉及 重新散列键)，我们在 keySet 中仍然有 2 个键而不是 1 个(因为键对象对于两个现有的 KV 对)?

So, my question is why after resizing hashMap (that, as far, as I understand involves rehashing keys), we still have 2 keys in keySet instead of 1 (since key object is same for both existing KV pairs) ?

推荐答案

所以，我的问题是为什么在调整 hashMap 的大小之后(据我所知，这涉及重新散列键)

So, my question is why after resizing hashMap (that, as far, as I understand involves rehashing keys)

它实际上不涉及重新散列键 - 至少在 HashMap 代码中没有，除非在某些情况下(见下文).它涉及在地图桶中重新定位它们.HashMap 内部是一个 Entry 类，它具有以下字段:

It actually does not involve rehashing keys – at least not in the HashMap code except in certain circumstances (see below). It involves repositioning them in the map buckets. Inside of HashMap is a Entry class which has the following fields:

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

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

The hash field is the stored hashcode for the key that is calculated when the put(...) call is made. This means that if you change the hashcode in your object it will not affect the entry in the HashMap unless you re-put it into the map. Of course if you change the hashcode for a key you won't be even able to find it in the HashMap because it has a different hashcode as the stored hash entry.

我们在 keySet 中仍然有 2 个键而不是 1 个(因为两个现有 KV 对的键对象相同)?

we still have 2 keys in keySet instead of 1 (since key object is same for both existing KV pairs) ?

因此，即使您更改了单个对象的哈希值，它仍在映射中，其中包含 2 个条目，其中包含不同的哈希字段.

So even though you've changed the hash for the single object, it is in the map with 2 entries with different hash fields in it.

话虽如此，HashMap 中的代码可能在调整 HashMap 大小时重新散列键 - 请参阅包 protected HashMap.transfer(...) jdk 7 中的方法(至少).这就是为什么上面的 hash 字段不是 final 的原因.但是，它仅在 initHashSeedAsNeeded(...) 返回 true 以使用替代哈希"时使用.以下设置启用 alt-hashing 的条目数阈值:

All that said, there is code inside of HashMap which may rehash the keys when a HashMap is resized – see the package protected HashMap.transfer(...) method in jdk 7 (at least). This is why the hash field above is not final. It is only used however when initHashSeedAsNeeded(...) returns true to use "alternative hashing". The following sets the threshold of number of entries where the alt-hashing is enabled:

-Djdk.map.althashing.threshold=1

通过在 VM 上设置此设置，我实际上能够在调整大小时再次调用 hashcode()，但我无法获得第二个 put(...) 被视为覆盖.部分问题是 HashMap.hash(...) 方法正在与内部 hashseed 进行 XOR，当调整大小时会更改，但是 在之后，put(...) 记录传入条目的新哈希码.

With this set on the VM, I'm actually able to get the hashcode() to be called again when the resizing happens but I'm not able to get the 2nd put(...) to be seen as an overwrite. Part of the problem is that the HashMap.hash(...) method is doing an XOR with the internal hashseed which is changed when the resizing happens, but after the put(...) records the new hash code for the incoming entry.

这篇关于Java HashMap 调整大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！