• Post Reply Bookmark Topic Watch Topic
  • New Topic

LinkedHashMap  RSS feed

 
Marcus Halberstram
Greenhorn
Posts: 19
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, in my data structures class we learned that a linked hashmap was a hashmap where a key led to a linked list of values, so one key could have many values. Reading the oracle javadoc on Java's LinkedHashMap class, it doesn't look like the same thing; where is the method to get the size of the associated linked list? Is there a data structure in java that has keys which may map to multiple values? I need to get the size of that associated list as well as index or traverse it. Thank you
 
Jesper de Jong
Java Cowboy
Sheriff
Posts: 16057
88
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Vulloff hatread wrote:Hi, in my data structures class we learned that a linked hashmap was a hashmap where a key led to a linked list of values, so one key could have many values.

Well, that's not true.

HashMap and LinkedHashMap both are implementations of interface Map, which is for collections that contain key-value pairs. The key and value can be of whatever type you like. The value is not necessarily a list, although it can be, if you use it like that.
 
Bin Smith
Ranch Hand
Posts: 514
1
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You didn't get it right.

LinkedHashMap(as well as HashMap) store its key-value pairs inside array. This array is array of special Entry objects that store your key and value.
One Entry instance stores only one key-value pair you provided.
However array can store multiple Entry instances at same bucket. Why?
Because index at which Entry is stored in array is calculated by using hashCode() method of key you provided. And that calculation can result in index which is occupied by previous Entry. To resolve this problem they decided to store multiple Entry objects at single index of array. As you know this is done due to linked list - one Entry references another Entry.

BUT LinkedHashMap additionally keeps Entry instances in way of linked list. Why? By storing Entry objects as linked list LinkedHashMap can guarantee order.
So LinkedHashMap stores Entry objects in array and additionally as linked list.
By storing Entry objects as linked list LinkedHashMap can store you key-value pairs(Entry objects) in insertion or access order.
You choose insertion or access order when creating LinkedHashMap in constructor. Note default order is insertion order.

Please review my LinkedHashMap tutorial to know it better as well as other java collections.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!