HashSet vs LinkedHashSet
Solution 1
The difference between the two are, as you've stated:
A
LinkedHashSet
is an ordered version ofHashSet
that maintains a doubly-linked List across all elements. Use this class instead ofHashSet
when you care about the iteration order. When you iterate through aHashSet
the order is unpredictable, while aLinkedHashSet
lets you iterate through the elements in the order in which they were inserted.
As for your question:
But in sourcecode of LinkedHashSet there are only calling constructors of HashSet.
The answer lies in which constructors the LinkedHashSet
uses to construct the base class:
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true); // <-- boolean dummy argument
}
...
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true); // <-- boolean dummy argument
}
...
public LinkedHashSet() {
super(16, .75f, true); // <-- boolean dummy argument
}
...
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true); // <-- boolean dummy argument
addAll(c);
}
And (one example of) a HashSet
constructor that takes a boolean argument is described, and looks like this:
/**
* Constructs a new, empty linked hash set. (This package private
* constructor is only used by LinkedHashSet.) The backing
* HashMap instance is a LinkedHashMap with the specified initial
* capacity and the specified load factor.
*
* @param initialCapacity the initial capacity of the hash map
* @param loadFactor the load factor of the hash map
* @param dummy ignored (distinguishes this
* constructor from other int, float constructor.)
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
Solution 2
HashSet is unordered and unsorted Set.
LinkedHashSet is the ordered version of HashSet.
The only difference between HashSet and LinkedHashSet is that:
LinkedHashSet maintains the insertion order.
When we iterate through a HashSet, the order is unpredictable while it is predictable in case of LinkedHashSet.
The reason for how LinkedHashSet maintains insertion order is that:
The underlying used data structure is Doubly-Linked-List.
Solution 3
LinkedHashSet
's constructors invoke the following base class constructor:
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}
As you can see, the internal map is a LinkedHashMap
. If you look inside LinkedHashMap
, you'll discover the following field:
private transient Entry<K, V> header;
This is the linked list in question.
Solution 4
I suggest you to use LinkedHashSet
most of the time, because it has better performance overall):
- Predictable iteration order LinkedHashSet (Oracle)
- LinkedHashSet is more expensive for insertions than HashSet;
- In general slightly better performance than
HashMap
, because the most of the time we use Set structures for iterating.
Performance tests:
------------- TreeSet -------------
size add contains iterate
10 746 173 89
100 501 264 68
1000 714 410 69
10000 1975 552 69
------------- HashSet -------------
size add contains iterate
10 308 91 94
100 178 75 73
1000 216 110 72
10000 711 215 100
---------- LinkedHashSet ----------
size add contains iterate
10 350 65 83
100 270 74 55
1000 303 111 54
10000 1615 256 58
You can see source test page here: The Final Performance Testing Example
Solution 5
You should look at the source of the HashSet
constructor it calls... it's a special constructor that makes the backing Map
a LinkedHashMap
instead of just a HashMap
.
Related videos on Youtube
Shikarn-O
Updated on April 05, 2022Comments
-
Shikarn-O about 2 years
What is the difference between them? I know that
A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.
But in sourcecode of LinkedHashSet there are only calling constructors of HashSet. So where is double-linked List and insertion order?
-
Delta over 12 yearsuse Intellij(Ctrl + B) option to track down the answer. :)
-
Delta over 12 yearsof course you need source code attached. :)
-
-
Shikarn-O over 13 yearsThanks, in HashSet there is constructor for creating LinkedHashMap, which is called in LinkedHashSet and all logic is in LinkedHashMap
-
ASA about 9 yearsA parent class having functionality explicitly for a child class, an ignored argument to distinguish
-
Eric J. over 8 yearsNot exactly a clean design using a dummy parameter for constructor disambiguation.
-
lbalazscs over 8 yearsIt is reasonably clean design, because the API is clean (this HashSet constructor is package private). The implementation details do not matter for the users of the class. Maintaining this code could be harder, but in the case of java.util classes, even very small performance improvements can justify that.
-
Felix S almost 7 yearsI don't see any warming up of the JVM before those "benchmarks", so I wouldn't take any of that data seriously. Read more