Java HashMap调整大小 [英] Java HashMap resizing

问题描述

假设我们有一些代码

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的大小时，可能会重新哈希密钥-至少请参见jdk 7中受程序包保护的HashMap.transfer(...)方法.这就是为什么上面的hash字段不是final的原因.但是，仅当initHashSeedAsNeeded(...)返回true时才使用替代哈希".以下设置了启用alt哈希的条目数阈值:

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(...)方法正在对内部进行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调整大小的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！