1

Recently, I attended an interview and the interviewer asked me this question.

How many times rehashing can occur in an HashMap once? twice? or N number of times? [when (threshold value +1) elements are added each time]

I know that when an map is full, then its likely that we are doing something wrong.

I admit that I could not give a satisfactory answer. Can anyone tell me the approach to answer such questions.

Or, what exactly was the interviewer looking for in an convincing answer?

Below are some of the SO questions I referred before asking this question.

https://stackoverflow.com/a/28811708 "Rehashing of a hash map is done when the number of elements in the map reaches the threshold values" Load factor of a HashMap is 0.75 and the default initial capacity value is 16. Once the number of elements reaches or crosses 12 element capacity rehashing of map happens.

Rehashing in Hashmap

When the number of entries in the hash map exceeds the product of the load factor and the current capacity, the hash map is rehashed (internal data structures are rebuilt), so that the hash map has approximately twice the number of buckets. When you rehash and move everything to a new location (bucket, etc.) then the older elements are also rehashed again and stored in the new bucket according to their new hash codes. The old space which was allocated to store the elements is garbage collected.

https://stackoverflow.com/a/27384645/5086633

Community
  • 1
  • 1
yeppe
  • 679
  • 1
  • 11
  • 43

1 Answers1

3

It depends from the kind of map.

For example for an HashMap exists a method resize that is defined as follow:

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. If current capacity is MAXIMUM_CAPACITY, this method does not resize the map, but sets threshold to Integer.MAX_VALUE. This has the effect of preventing future calls. Parameters: newCapacity the new capacity, MUST be a power of two; must be greater than current capacity unless current capacity is MAXIMUM_CAPACITY (in which case value is irrelevant).

So according this definition is possible to enlarge the Map at steps of power of two up to MAXIMUM_CAPACITY.

The value of MAXIMUM_CAPACITY is 

static final int MAXIMUM_CAPACITY = 1 << 30;

this value is 1.073.741.824.

Building a new HashMap expliciting an initial capacity of 1 you can have at maximum of 30 resizes, because 2^30 = MAXIMUM_CAPACITY = 1.073.741.824.

Davide Lorenzo MARINO
  • 26,420
  • 4
  • 39
  • 56
  • ok ...if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } – yeppe Jun 21 '16 at 17:02
  • 1
    The exact number may be slightly less, there are a lot of places to check with regards to *minimum* table size and the exact rules applied when growing. But this answer gives a good estimate and it should be more than sufficient to answer the interview question. – Durandal Jun 21 '16 at 17:05