Java HashMap resizing

Question

Let's assume we have some code

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

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) ?

@ACV, when we add second KV hashMap chunks size became 4 instead of 2 (initial). Or I miss something? — Vladyslav Nikolaiev, Sep 05 '17 at 13:28
hashMap.keySet() returns you number of actual keys in hash map. So, as you put two keys, you always get 2. — Natalia, Sep 05 '17 at 13:30
have you confirmed via debugging that the HashMap is _actually_ resizing? — jtahlborn, Sep 05 '17 at 13:31
Your code isn't valid. You aren't allowed to modify a key entry after inserting it. — user207421, Sep 06 '17 at 10:48
It doesn't matter why you did it. The code isn't valis, so no conclusions can be drawn from how it behaves. — user207421, Sep 06 '17 at 11:48
@EJP, but I still can do what I have done. Yes, may be it's not recommended, but the code is valid, at least because it's executable — Vladyslav Nikolaiev, Sep 06 '17 at 12:47
The code is *invalid* because it conflicts with the requirements specified in the documentation for `HashMap`. The compiler isn't obliged to enforce every last piece of Javadoc, and neither is the JVM. — user207421, Sep 07 '17 at 09:58

Gray · Accepted Answer · 2017-09-07T13:19:32.327

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

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;

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.

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

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.

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

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.

I see. So, the hash is cached and then it is reused only to find the position of the entry in the new (expanded or contracted depending upon the load factor) hashmap instead of actually rehashing the keys, as taught to most of us in Algorithms etc. classes. Learned something new and important. — displayName, Sep 05 '17 at 13:53
This of course, depends on the implementation of `HashMap`. I've not looked at (for example) `LinkedHashMap` or other implementations of `Map`. There's nothing that says that the `Map` implementation can't call `obj.hashcode()` multiple times although, as @jthlborn mentions, it can be expensive to do so. — Gray, Sep 05 '17 at 14:08
That is why it is recommended to use keys that are immutable (or atleast the equals/hashcode part). For the example above, the behavior is implementation defined and can vary for JVM to JVM. It was probably a thought exercise. — rents, Sep 05 '17 at 14:17

jtahlborn · Answer 2 · 2017-09-06T13:19:20.213

7

The HashMap actually caches the hashCode for each key (as a key's hashCode may be expensive to compute). So, although you changed the hashCode for an existing key, the Entry to which it is linked in the HashMap still has the old code (and hence gets put in the "wrong" bucket after resize).

You can see this for yourself in the jvm code for HashMap.resize() (or a little easier to see in the java 6 code HashMap.transfer()).

edited Sep 06 '17 at 13:19

answered Sep 05 '17 at 13:33

jtahlborn

52,909
5
76
118

1

I can't tell why you've linked the jdk-6 sources, and why not 8 for example? where there is no such method at all – Eugene Sep 06 '17 at 07:40
@Eugene happened to be the first hit on google when i search for the source for HashMap. looking at java 8, the answer is still correct, although it's a little harder to decipher from the source. – jtahlborn Sep 06 '17 at 13:17
@Eugene add java 8 link. – jtahlborn Sep 06 '17 at 13:19

score 5 · Answer 3 · answered Sep 06 '17 at 08:01

I can't tell why two of the answers rely on HashMap.tranfer for some example, when that method is not present in java-8 at all. As such I will provide my small input taking java-8 in consideration.

Entries in a HashMap are indeed re-hashed, but not in the sense you might think they do. A re-hash is basically re-computing the already provided (by you) of the Key#hashcode; there is a method for that:

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

So basically when you compute your hashcode, HashMap will basically say - "i don't trust you enough" and it will re-hash your hashcode and potentially spread the bits better (it's actually a XOR of the first 16 bits and last 16 bits).

On the other hand when HashMap is re-sized it actually means that number of bins/buckets is doubled in size; and because bins are always a power of two - that means that an entry from a current bin will: potential stay in the same bucket OR move to a bucket that is at the offset at the current number of bins. You can find a bit of details how this is done in this question.

So once a re-size happens, there is no extra re-hashing; actually one more bit is taken into consideration and thus an entry might move or stay where it is. And Gray's answer is correct in this sense, that each Entry has the hash field, that is computed only once - the first time you put that Entry.

Persixty · Answer 4 · 2017-09-06T10:56:44.500

I can't find it clearly documented, but changing a key value in a way that changes its hashCode() typically breaks a HashMap.

HashMap divides entries amongst b buckets. You can imagine key with hash h is assigned to bucket h%b. When it receives a new entry it works out which bucket it belongs to then if an equal key already exists in that bucket. It finally adds it to the bucket removing any matched key.

By changing the hash-code the object wrongHashCode will be (typically and here actually) directed to another bucket second time around and its first entry won't be found or removed.

In short, changing the hash of an already inserted key breaks the HashMap and what you get after that is unpredictable but may result in (a) not finding a key or (b) find two or more equal keys.

score 0 · Answer 5 · answered Sep 06 '17 at 10:35

Because HashMap stores the elements in an internal table and incrementing the code does not affect that table:

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

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

As you can see table[bucketIndex] = new Entry (hash, ...) so although you increment the code, it won't be reflected here.

Try making the field code to be Integer and see what happens?

@VladyslavNikolaiev. No it's not. Where does it say it's reconstructed? I can't see that in the code. — ACV, Sep 06 '17 at 10:59
@ACV4, it's resized when elements count is reached to specific value. After that inner table size is doubled (reconstructed) — Vladyslav Nikolaiev, Sep 06 '17 at 11:04

Java HashMap resizing

5 Answers5

Linked