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

所以,我的问题是为什么在调整hashMap的大小之后(据我所知,直到重新调整键),我们仍然在keySet中有2个键而不是1个(因为现有的KV对的键对象是相同的)？

Answer 1

所以,我的问题是为什么在调整hashMap之后(到目前为止,据我所知,涉及重新调整键)

它实际上并没有,至少没有在-包括老调重弹键HashMap,除了在某些情况下(见下文)代码.它涉及在地图桶中重新定位它们.里面HashMap是一个Entry具有以下字段的类:

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

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

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

因此,即使您已更改单个对象的哈希值,它也会在地图中包含2个条目,其中包含不同的哈希字段.

总而言之,当调整HashMap的大小时,HashMap其中的代码可能会重新调整密钥 - 请参阅HashMap.transfer(...)jdk 7中的软件包保护方法(至少).这就是hash上面的字段不是的原因final.它仅在initHashSeedAsNeeded(...)返回true 时才使用"替代散列".以下设置启用alt-hashing的条目数阈值:

-Djdk.map.althashing.threshold=1

有了这个设置在VM上,我实际上能够hashcode()在调整大小时再次调用,但是我无法将第二个put(...)视为覆盖.问题的部分原因是,该HashMap.hash(...)方法是做与内部的XOR hashseed时调整大小会发生这变化,但之后的put(...)记录进入进入新的哈希码.

Answer 2

HashMap实际上为每个键缓存 hashCode(因为键的hashCode计算起来可能很昂贵).因此,虽然您更改了现有键的hashCode,但它在HashMap中链接到的Entry仍然具有旧代码(因此在调整大小后将其置于"错误"桶中).

你可以在HashMap.resize()的jvm代码中看到这个(或者在java 6代码HashMap.transfer()中更容易看到).

Answer 3

HashMap.tranfer当 java-8 中根本不存在该方法时，我无法说出为什么其中两个答案依赖于某些示例。因此，我将考虑 java-8 提供我的小输入。

aHashMap中的条目确实经过重新哈希处理，但不是您认为的那样。重新散列基本上是重新计算已经提供的（由您）Key#hashcode; 有一种方法：

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

所以基本上当你计算你的哈希码时，HashMap基本上会说 - “我对你不够信任”，它会重新哈希你的哈希码并可能更好地传播这些位（它实际上是XOR前 16 位和后 16 位的一个）。

在另一方面，当HashMap被重新定尺寸实际上意味着数箱/桶大小被加倍的; 并且因为 bin始终是 2 的幂 - 这意味着来自当前 bin 的条目将：可能留在同一个桶中或移动到位于当前 bin 数量的偏移处的桶。您可以在此问题中找到有关如何完成此操作的一些详细信息。

因此，一旦发生重新调整大小，就没有额外的重新散列；实际上还要考虑一位，因此条目可能会移动或停留在原处。从这个意义上说，格雷的答案是正确的，每个人Entry都有一个hash场，只计算一次 - 第一次把那个Entry.