Menu
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.
652
The Initial Capacity is essentially the number of buckets in the HashMap which by default is 24 = 16. A good HashMap algorithm will distribute an equal number of elements to all the buckets.
Buckets: It bucket is one element of the HashMap array. It is used to store nodes. Two or more nodes can have the same bucket. In that case, a link list structure is used to connect the nodes. Buckets are different in capacity.
The initial capacity of the HashMap is the number of buckets in the hash table. It creates when we create the object of HashMap class. The initial capacity of the HashMap is 24, i.e., 16. The capacity of the HashMap is doubled each time it reaches the threshold.
HashMap works on the principle of Hashing. There are three terms used in hashing: Hash Function, Hash Value and Bucket. In Java, the default bucket size is 16 and the maximum bucket size is 2^30 and we can verify it with the following code found in HashMap class.
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.
115
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
44
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
