yeppe - 5 months ago 35

Java Question

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.

http://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.

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

Answer

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:newCapacitythe 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`

.