What is meant by number of buckets in the HashMap?

Question

I was reading about Hashmap.

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table.

If there are 10 key value pairs in the Hashmap. Assume there Hashcode is different.

Each will resides in one bucket right? Or one bucket can have bucket multiple key-value pairs?

Since bucket in english means a big thing where many objects can reside.

Solution 1

Yes, exactly, each bucket can have multiple key-value pairs.

The object's hashCode() determines which bucket it goes into, via this expression: object.hashCode() % n, where n = the total number of buckets and % is the modulus operator.

Most often the objects will be well distributed across buckets, but you have no guarantee where they go. This depends on the data and the hashCode function.

Obviously, when the hashCode implementation is poor, the performance of the hashmap will go down.

Also read up on the equals / hashcode contract, which is relevant.

Solution 2

In java if you store an object in HashMap first HashMap implementation calls the hashCode() method to find a bucket location. Then it stores both: the key and value as an Entry. NB! it stores the key also because it's crucial during retrieving the object. Two object can have the same hashcode so if this happens then HashMap will use the same bucket location and store the second object there too. Inside it uses a LinkedList for this. (not java.util.LinkedList, but a simpler implementation)

During retrieving: you have a key -> hashCode() -> bucket location -> search in LinkedList by key -> returning object.

EDIT: So you have one bucket on the same location but a bucket is a LinkedList so it can store multiple Entries. So the number of buckets is the capacity of Hashmap and describes how many Entries you can store without linking them in a list.

You can find a great article and more detailed explanation here: http://javahungry.blogspot.com/2013/08/hashing-how-hash-map-works-in-java-or.html http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html

Solution 3

Bucket with hashcode 1    Bucket with hashcode 2 and similar
  K and V                    K and V
  K and V                    K and V 

So the hashCode() of the key decides in which bucket the K V pair goes and the same hashCode is used to find the K V pair while lookup.

hashCode() should never return a constant value. As that would mean that all the objects will be in a single bucket. And that would be same as not using a Map in the first place. As all the key value pairs would be in same bucket, Java will have to iterate through all the objects to find the key.

Comments

[Thinker]

So you are saying, bucket can have multiple key-value pairs which has different hashcode.

[Prasad Kharkar]

@Thinker I would say a bucket is a hashcode. and all the objects with same hashcode fall into that bucket

[Prasad Kharkar]

@Thinker, This link will give you good information about hashcode. thejavageek.com/2013/06/27/what-are-hashcodes

[vikingsteve]

@PrasadKharkar hashCode() can be greater than the number of buckets. The modulus operator typically assigns the bucket from the hashCode.

[Prasad Kharkar]

@vikingsteve, thats new to learn. I told what I've learned from Kathie Sierra SCJP book. Can you please elaborate with a good link? It would be great.

[vikingsteve]

I see a good discussion here: stackoverflow.com/questions/10879302/…

[xploreraj]

Old comment but what concept you wrote is wrong other than first para.

[Sergey Shcherbakov]

"The object's hashCode() determines which bucket it goes into" -- that is a bit misleading. As you point out in the next sentence, the hashCode() returns the "hash code" not the bucket number/index. The modulo operator is what gives the bucket. The hashcode is not a bucket and the bucket is not a hashcode. The hash code is the hash code and some code outside of the object's hashCode() implementation (the %) determines the bucket (its index). The answer is correct. It's just slight inaccuracies in terminology what causes confusion.

[vikingsteve]

Hardly misleading, since when the hashCode is a single argument to the function determining the bucket, it does actually determine the bucket - given that the "outside" code you mention (modulus operator, or whatever the exact implementation) is consistent.