Internal implementation of LinkedHashSet

public class LinkedHashSetExample

{    public static void main(String[] args)

    {

        //Creating LinkedHashSet

         LinkedHashSet set = new LinkedHashSet();

         //Adding elements to LinkedHashSet

         set.add("BLUE");

         set.add("RED");

         set.add("GREEN");   

         set.add("BLACK");

    }

}

Pictorial representation of how it works




New obj of LinkedHashset calls a super (ie HashSet constructor) 

which inturn create LinkedHashMap

How LinkedHashSet Maintains Insertion Order?

How LinkedHashSet Maintains Insertion Order?

LinkedHashSet uses LinkedHashMap object to store it’s elements. The elements you insert in the LinkedHashSet are stored as keys of this LinkedHashMap object. Each key, value pair in the LinkedHashMap are instances of it’s static inner class called Entry. This Entry class extends HashMap.Entry class. The insertion order of elements into LinkedHashMap are maintained by adding two new fields to this class. They are before and after. These two fields hold the references to previous and next elements. These two fields make LinkedHashMap to function as a doubly linked list.

private static class Entry extends HashMap.Entry

{

        // These fields comprise the doubly linked list used for iteration.

        Entry before, after;

        Entry(int hash, K key, V value, HashMap.Entry next) {

            super(hash, key, value, next);

        }

}

The first two fields of above inner class of LinkedHashMap – before and after are responsible for maintaining the insertion order of the LinkedHashSet. The header field of LinkedHashMap stores the head of this doubly linked list. It is declared like below,

private transient Entry header; //Stores the head of the doubly linked list

In LinkedHashMap, the same set of Entry objects (rather references to Entry objects) are arranged in two different manner. One is the HashMap and another one is Doubly linked list. The Entry objects just sit on heap memory, unaware of that they are part of two different data structures.