How does the HashMap make sure the index calculated using the hashcode key is within the available range?

Question

I looked at the source code of the HashMap and asked a few questions. The PUT method takes a key and a value and does

• a hash function of the key hash code.

• calculate the bucket location for this pair using the hash obtained in the previous step

  public V put(K key, V value) { int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); ..... } static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); } 

Example:

• Create a HashMap with size 10.
• calling put (k, v) three times and suppose these 3 occupy the bucket loc 7, 8 and 9
• call put 4th K, V pair and subsequent occurs
  • hash () is called with key.hashcode () and the hash is calculated
  • indexFor is calculated based on a hash

Question:

• What if the calculated bucket location for 4th k, v goes beyond the existing boundaries? say location 11?

Thanks in advance Ah

Answer 1

For your first question: the card always uses a power of two for size (if you give it a capacity of 10, it will actually use 16), which means that index & (length - 1) will always be in the range [0, length) so it always in range.

It is not clear what your second and third question relates to. I do not think that HashMap redistributes everything, except when necessary.

Answer 2

HashMaps typically uses a hash code to modify the number of buckets. What happens in a collision is implementation dependent (not sure about Java HashMap). There are two main strategies: keeping a list of items falling into the bucket, or moving to other buckets if your bucket is full. My guess would be that HashMap uses a list approach.

Answer 3

Let's move on to more detailed information. How will hashmap initialize bucket size?

following code from HashMap.java

while (i <paramInt) i <= 1;

If you pass the initial 10, then the code above is used to create power 2. Therefore, using the HashMap code above, initialize the bucket size 16;

And below code is used to calculate bucket index,

 static int indexFor(int h, int length) { return h & (length - 1); }