CODEWITHSUNDEEP
javaalgorithmdata-structureshashhashmap
Akh
Akh

Reputation: 6043

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

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:

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

Upvotes: 5

Views: 5447

Answers (3)

Rakesh Chaudhari
Rakesh Chaudhari

Reputation: 3510

Let's go into more detail, How hashmap will initialize bucket size?

following code is from HashMap.java

while (i < paramInt) i <<= 1;

If you pass initial 10 then above code is used to make a size of power 2. So using above code HashMap initialize bucket size 16;

And below code is used to calculate bucket index,

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

Upvotes: 0

Eric Andres
Eric Andres

Reputation: 3417

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.

Upvotes: 1

Jon Skeet
Jon Skeet

Reputation: 1501163

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.

Upvotes: 2

Related Questions