aspose file tools*
The moose likes Java in General and the fly likes Map behaviour with duplicate key Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of JavaScript Promises Essentials this week in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Map behaviour with duplicate key" Watch "Map behaviour with duplicate key" New topic
Author

Map behaviour with duplicate key

Harshana Dias
Ranch Hand

Joined: Jun 11, 2007
Posts: 327
I have read in a article which says HashMap maintain a linked list to maintain duplicates. But as i know it replace the latest value if so right?

article

See the below section which it says,


"What will happen if two different objects have same hashcode?”
Now from here onwards real confusion starts, Some time candidate will say that since hashcode is equal, both objects are equal and HashMap will throw exception or not store them again etc, Then you might want to remind them about equals() and hashCode() contract that two unequal object in Java can have same hashcode. Some will give up at this point and few will move ahead and say "Since hashcode is same, bucket location would be same and collision will occur in HashMap, Since HashMap use LinkedList to store object, this entry (object of Map.Entry comprise key and value ) will be stored in LinkedList. Great this answer make sense though there are many collision resolution methods available this is simplest and HashMap in Java does follow this. But story does not end here and interviewer asks


Above description is false right?

Also what collection maintain duplicates in a such list and if so how to identify the relevant object using get("key") method?



Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14338
    
  22

No, the description isn't wrong.

Note that when two objects have the same hash code, it does not mean the objects are equal (i.e. the objects are not necessarily duplicates).


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 8 API documentation
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4991
    
    8

You have to be clear on what you mean by "duplicates" -- a Map will not contain any duplicate keys. It's the hash codes of the keys that can be the same, so there needs to be some way to deal with these collisions. And per the JavaDocs for HashMap, if you put a new value for a key that already exists in the HashMap, the old value will be replaced by the new one and the old value will be returned by the put method.

Also note that there is nothing that prevents you from mapping the same value to multiple keys. Thus, a Map can contain duplicate values but these must be associated with different keys. You can even associate the same object to multiple keys. There are real-world applications to this.


Junilu - [How to Ask Questions] [How to Answer Questions]
Harshana Dias
Ranch Hand

Joined: Jun 11, 2007
Posts: 327
Does when map figure the hash code by key both key and value store as a Entry in that hash bucket as a LinkedList. In the case of more objects add to the same hash code, those will add to the LinkedList?
i mean like List<Entry> per hash bucket
Harshana Dias
Ranch Hand

Joined: Jun 11, 2007
Posts: 327
Also i found that its not a concrete linked list implementation but a Entry class implementation behaves as a linked list.



This Entry class creates per hash bucket right?
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39773
    
  28
What is not concrete about that? That is the usual way a linked list is implemented: a self‑referential class which has an instance of itself as the next field.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39773
    
  28
Harshana Dias wrote: . . . This Entry class creates per hash bucket right?
No. It is one per K‑V pair.
Harshana Dias
Ranch Hand

Joined: Jun 11, 2007
Posts: 327
Campbell Ritchie wrote:
Harshana Dias wrote: . . . This Entry class creates per hash bucket right?
No. It is one per K‑V pair.


ok multiple Entry objects in same buckets for duplicate hashcode key objects right
Harshana Dias
Ranch Hand

Joined: Jun 11, 2007
Posts: 327
Campbell Ritchie wrote:What is not concrete about that? That is the usual way a linked list is implemented: a self‑referential class which has an instance of itself as the next field.


No i thought it as a java.util.LinkedList<Entry> class per bucket and each new hash code similar elements going to add for it
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39773
    
  28
Harshana Dias wrote: . . . ok multiple Entry objects in same buckets for duplicate hashcode key objects right
Not quite.
The map implementations usually use abs(h % c) where h is the hashcode and c the capacity of the backing array. The simplest way to implement this is with the bitwise and operator.
You write something like myArray[h & myArray.size - 1].
The array must always have 1, 2, 4, 8, 16, 32, etc, elements.
Harshana Dias
Ranch Hand

Joined: Jun 11, 2007
Posts: 327
Campbell Ritchie wrote:
The map implementations usually use abs(h % c) where h is the hashcode and c the capacity of the backing array.


In here you mean by backing array is the linked list type of implementation of the Entry class right?
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4991
    
    8

What's curious to me is your keen interest in knowing the internals of this class. The whole point of creating the Collections API was to abstract away these details so that application developers did not have to worry about the implementation -- they just work as documented in the API Javadocs and that's all you really need to know.

Granted, as an academic exercise it may have some value in giving you ideas on how to solve such problems but other than that, there are more important concepts that apply to design and application development that you can spend your time and effort on for more benefit to you and others who will have to work with your code.

If this is related to an interview question that you missed, I wouldn't agonize over it if it were me. My reaction to a question like this would be to question the motivation of the question and say exactly what I said above about the intent of the API. If they don't like that, then they're probably not the kind of developers I'd like to work with anyway.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39773
    
  28
Harshana Dias wrote: . . . In here you mean by backing array is the linked list type of implementation of the Entry class right?
No.

A backing array is an array and a linked list is a linked list.
There is likely to be an Entry[] array, and each Entry’s location in the array depends on its hash code.
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14338
    
  22

If you really want to know how HashMap works, you can look at the source code, which you can find in the file src.zip in your JDK installation directory.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Map behaviour with duplicate key