What happens to the index of the values in a HashMap when it increases its size?

Question

I understand that when we declare a map like the following:

Map <String, Integer> map = new HashMap ();

The default load factor is 0.75 and its size is 16, when the buckets of the map exceed the number of 12 elements, the size changes to 32.

However, the way in which the map chooses the index of the bucket where the object will be placed when using the put function, is defined by hascode % n but what happens when the map size exceeds the load factor? n no longer has the same value, therefore, how can you find the previously set entries if, when applying hascode % n, the resulting index will not be the same as before?

My final question is :

how can the index of the bucket be the same after we've increased the size?

Answer 1

The simple answer is that the index of the bucket can't necessarily be the same. HashMap has to perform a rehashing of all of the elements at the point when it expands.

See the following method:

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {

which is called by resize. The JavaDoc for which says

Rehashes the contents of this map into a new array with a larger capacity. This method is called automatically when the number of keys in this map reaches its threshold.

_{Emphasis mine}

See also:

• Rehashing process in hashmap or hashtable
• how and when Rehashing is done in HashMap
• Rehashing in HashMap in Java

Answer 2

Default initial capacity of the HashMap takes is 16 and load factor is 0.75f (i.e 75% of current map size). The load factor represents at what level the HashMap capacity should be doubled.

For example product of capacity and load factor as 16 * 0.75 = 12. This represents that after storing the 12th key – value pair into the HashMap , its capacity becomes 32.

For Further Exposure

Further Process Explanation

Rehashing of a hash map is done when the number of elements in the map reaches the maximum threshold value.

Usually the load factor value is 0.75 and the default initial capacity value is 16. Once the number of elements reaches or crosses 0.75 times the capacity, then rehashing of map takes place. In this case when the number of elements are 12, then rehashing occurs. (0.75 * 16 = 12)

When rehashing occurs a new hash function or even the same hash function could be used but the buckets at which the values are present could change. Basically when rehashing occurs the number of buckets are approximately doubled and hence the new index at which the value has to be put changes.

While rehashing, the linked list for each bucket gets reversed in order. This happens because HashMap doesn't append the new element at the tail instead it appends the new element at the head. So when rehashing occurs, it reads each element and inserts it in the new bucket at the head and then keeps on adding next elements from the old map at the head of the new map resulting in reversal of linked list.

If there are multiple threads handling the same hash map it could result in infinite loop.

Detailed explanation stating how infinite loop occurs in the above case can be found here :

Read this Article for more understanding

If the elements inserted in the map has to be sorted wrt the keys then TreeMap can be used. But HashMap would be more efficient if order of keys doesn't matter.

Answer 3

Internal data structures are rebuilt. From the docs: https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html :

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 (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

Answer 4

Hashmaps do not preserve ordering. Look at using LinkedHashMaps instead.