• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Map behaviour with duplicate key

 
Ranch Hand
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?



 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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).
 
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Harshana Dias
Ranch Hand
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Harshana Dias wrote: . . . This Entry class creates per hash bucket right?

No. It is one per K‑V pair.
 
Harshana Dias
Ranch Hand
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 352
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Sheriff
Posts: 17644
300
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 am going to test your electrical conductivity with this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic