Java - HashMap confusion about collision handling and the get() method
Solution 1
Are they overwritten so that only the last object placed in that key exists there anymore?
Yes, assuming you're putting multiple values with the same key (according to Object.equals
, not Object.hashCode
.) That's specified in the Map.put
javadoc:
If the map previously contained a mapping for the key, the old value is replaced by the specified value.
If you want to map a key to multiple values, you're probably better off using something like Guava's ListMultimap
, ArrayListMultimap
in specific, which maps keys to lists of values. (Disclosure: I contribute to Guava.) If you can't tolerate a third-party library, then really you have to have a Map<Key, List<Value>>
, though that can get a bit unwieldy.
Solution 2
The documentation for Hashmap.put() clearly states, "Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced"
If you would like to have a list of objects associated with a key, then store a list as the value.
Note that 'collision' generally refers to the internal working of the HashMap, where two keys have the same hash value, not the use of the same key for two different values.
Solution 3
Let's say n > 1 objects get placed in the same key. Are they stored in a linked list? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?
There could be single instance for the same key so the last one overrides the prior one
Map<String, Integer> map = new HashMap<String, Integer>();
map.put("a", 1);
map.put("a", 2);// it overrides 1 and puts 2 there
chaining comes where there turns the same hash for different keys
See
Slims
Updated on July 06, 2022Comments
-
Slims almost 2 years
I'm using a
HashMap
and I haven't been able to get a straight answer on how theget()
method works in the case of collisions.Let's say
n > 1
objects get placed in the same key. Are they stored in aLinkedList
? Are they overwritten so that only the last object placed in that key exists there anymore? Are they using some other collision method?If they are placed in a
LinkedList
, is there a way to retrieve that entire list? If not, is there some other built in map for Java in which I can do this?For my purposes, separate chaining would be ideal, as if there are collisions, I need to be able to look through the list and get information about all the objects in it. What would be the best way to do this in Java?
Thanks for all your help!
-
Chris Dargis over 11 yearsThe OP is referring to collisions resulting from multiple
hashCode()
invocations from two distinct objects producing the same value. Collisions -
Slims over 11 yearsThank you. I'm annoyed that I am going to have to use that latter strategy, but such is life.
-
GreyBeardedGeek over 11 yearsNo, clearly OP was asking about using the same key multiple times, "Let's say n > 1 objects get placed in the same key"...
-
Louis Wasserman over 11 yearsThe Java designers decided that the "overwriting" behavior was much more commonly useful, and could be used to simulate the "mapping to lists" (with, of course, a
Map<Key, List<Value>>
) -- and that mapping to lists wasn't common enough a use case to add to the JDK itself. -
Chris Dargis over 11 yearsGood point, this is clearly stated in the question. If you do a quick edit I will remove my down-vote. Although I still think the OP was referring to collisions, it isn't clear at all.
-
Chris Dargis over 11 yearsThere is nothing wrong with the answer. For me to be allowed to remove the down-vote, an edit needs to be applied to it.
-
GreyBeardedGeek over 11 years