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

Question

I went through source code of HashMap and have a few questions. The PUT method takes the Key and Value and does

1. the hashing function of the hashcode of the key.

2. calculate bucket location for this pair using the hash obtained from 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:

• Creating a HashMap with size 10.
• call put(k,v) three times and assume these 3 occupies bucket loc 7 ,8 and 9
• call put 4th K,V pair and following happens
  • hash() is called with key.hashcode() and hash calculated
  • indexFor is calculated based on hash

Question:

1. What if the calculated bucket location for the 4th k,v is out of the existing bounds? say location 11 ?

Thanks in advance Akh

Answer 1

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

It's not clear what your second and third question relate to. I don't think HashMap reallocates everything unless it needs to.

Answer 2

HashMaps will generally use the hash code mod the number of buckets. What happens when there is a collision depends on the implementation (not sure for Java's HashMap). There are two basic strategies: keeping a list of items that fall in the bucket, or skipping forward to other buckets if your bucket is full. My guess would be that HashMap uses the list bucket approach.