aspose file tools*
The moose likes Java in General and the fly likes How insertion order is maintained in LinkedHashSet? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "How insertion order is maintained in LinkedHashSet?" Watch "How insertion order is maintained in LinkedHashSet?" New topic
Author

How insertion order is maintained in LinkedHashSet?

Ankush Kanungo
Greenhorn

Joined: Apr 20, 2008
Posts: 10

Hi,

I am looking at the API's of Java 6.

LinkedHashSet maintains insertion order as opposed to HashSet.

I have read that LinkedHashSet uses doubly linked list for maintaining the insertion order between the elements. But, its extending
HashSet class and that uses a map and not doubly linked list.

Any explaining would be helpful.

Thank you,
Ankush

Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
It uses a hash map and a doubly-linked list. The hash map is inherited from HashMap, while the doubly-linked list is implemented internally by adding new fields to the new class. The source code is freely available - your JDK probably has a src.jar file somewhere near the top directory, containing source for all the standard Java libraries (except the stuff implemented as native methods). Studying this source can be very informative for questions like this.
Ankush Kanungo
Greenhorn

Joined: Apr 20, 2008
Posts: 10

Hello Mike,

Thanks for your reply and pointing me to the right direction.

I installed decompiler, and can see the source code. I can see that Entry class is used for maintaining doubly linked list.

An Entry array is declared in HashMap, which contains a variable to itself, for implementing doubly linked list.

Please let me know what i have inferred from the code is correct.

Thank you,
Ankush
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Well, I don't think you should need a decompiler for this. Decompilers are very cool but may give errors, and they may not include the original local variable names or comments. Since Sun and now Oracle make the actual source code easily available, it's generally preferable to view that source directly. Are you using an IDE? (Which one?) They usually make it very easy to find the source. If not, can you find a file called src.jar or src.zip in your JDK installation? If not, what operating system are you using, and what JDK? We can probably provide pointers.

Your understanding so far seems accurate, except here:
An Entry array is declared in HashMap, which contains a variable to itself, for implementing doubly linked list.

The one declared in HashMap doesn't know anything about linked lists. Did you mean to say "for implementing hash map"?

The extended version, LinkedHashMap.Entry, has the necessary information to be part of both a HashMap and a doubly linked list. There are really two data structures that are sharing the same set of Entry objects, arranging them differently. Or rather, arranging the references differently. The Entry objects themselves just sit on the heap, unaware that they are part of two different data structures. Kind of cool, I think.

Ankush Kanungo
Greenhorn

Joined: Apr 20, 2008
Posts: 10

Hi Mike,

I am using Eclipse Galileo on Ubuntu, i was able to attach the source code.

I think, the entry has nothing to do with the doubly linked list as i interpreted is wrong.

You mean the transient Entry field declared in the LinkedHashSet class acts as a header to Entry<K,V> doubly linked list, where these entries referenced by header are also used as elements in HashMap, right?

Thank you



Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 3018
    
  10
Yes.
 
Don't get me started about those stupid light bulbs.
 
subject: How insertion order is maintained in LinkedHashSet?