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
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.
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.