When there is a collision during a put in a HashMap is the map resized or is the entry added to a list in that particular bucket?
+8
A:
When you say 'collision', do you mean the same hashcode? The hashcode is used to determine what bucket in a HashMap is to be used, and the bucket is made up of a linked list of all the entries with the same hashcode. The entries are then compared for equality (using .equals()) before being returned or booted (get/put).
Note that this is the HashMap specifically (since that's the one you asked about), and with other implementations, YMMV.
Kylar
2010-02-10 18:30:14
And as an added note: if you're curious about how an implementation works, why not just download the source code and look at it? It's available here: http://java.sun.com/javase/downloads/index.jsp under 'Additional Resources'.
Kylar
2010-02-10 18:39:16
+2
A:
Either could happen - it depends on the fill ratio of the HashMap.
Usually however, it will be added to the list for that bucket - the HashMap class is designed so that resizes are comparatively rare (because they are more expensive).
mikera
2010-02-10 18:38:05
A:
The documentation of java.util.HashMap explains exactly when the map is resized:
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, and the initial capacity is simply the capacity at the time the hash table is created.
The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
The default initial capacity is 16, the default load factor is 0.75. You can supply other values in the map's constructor.
Eli Acherkan
2010-02-11 09:12:34