Hashmap Capacity not increased even on reaching threshold

Question

Java doc says - When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed

In below program -

HashMap<Integer, String> map = new HashMap<Integer, String>();
int i = 1;
while(i<16) {
    map.put(i, new Integer(i).toString());
    i++;
}

Key is of type Integer, at insertion of 13th to 15th element HashMap capacity remains as 16 and threshold remains same as 12, why ?

Debug screenshot after adding 13th element in map -

args                 String[0] (id=16)
map HashMap<K,V> (id=19)
 entrySet   null
 hashSeed   0
 KeySet     null
 loadFactor 0.75
 modCount   13
 size       13
 table      HashMap$Entry<K,V>[16] (id=25)
 threshold  12
 values     null
i   14

[null, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10, 11=11, 12=12, 13=13, null, null] 

HashMap with key of type String - HashMap<String, String> or a custom class - Map<Employee,Integer> show expected behaviour at 13th insertion

Oscar

Read the code. That will explain it. It is possible that something has changed in the implementation that means that the javadoc is no longer exactly correct. But this is not interesting (IMO) because no sensible programmer would ever depend on the precise behaviour of hashmap resizing. – Reimpression

Just trying to find why implementation behaviour is different for having keys as Integer. If I try HashMap<String, String> it does resizes map at 13th insertion – Oscar

Which Java version (including update)? – Whitneywhitson

@m3th0dman java version - 1.7.0_67-b01 – Oscar

Answer 1

Looks like this behaviour is due to change in internal implementation of HashMap PUT method in recent version of Java 7. After going through source code of multiple versions, found an answer to my question

HashMap put method calls addEntry() to add a new entry -

public V put(K key, V value) {
    ...
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    ...
    addEntry(hash, key, value, i);
    ...
}

jdk7-b147 HashMap.addEntry method looks like -

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

Source code of version 1.7.0_67-b01 looks like -

void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}

So, in recent versions of Java, HashMap may not be resized based on threshold alone. If bucket is empty entry would still go in without resizing HashMap

Java 8 may have different behaviour, source code of version 8-b132 shows PUT is completely re implemented -

put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    ....
}

final Node<K,V>[] resize() {
     //many levels of checks before resizing   
}

Java doc may not be updated as frequently as Java versions ! Thanks Stephen

Oscar