Unsorted HashSet in Java

Question

Code.

Set<String> set = new HashSet<String>(3);
set.add("3 Lorem");
set.add("1 Lorem");
set.add("2 Lorem");
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    String type = (String) iterator.next();
    System.out.println(type);
}

Output.

2 Lorem
3 Lorem
1 Lorem

This order looks strange to me. I add 3 Lorem, 1 Lorem, and then 2 Lorem. Why are they in a different order in the output?

@LutzHorn, I thought it would in the order I used when adding. — Maksim Dmitriev, Nov 06 '13 at 12:42
@LutzHorn, I didn't know it; now I know. By the way, it may be an interview question — Maksim Dmitriev, Nov 06 '13 at 12:50
@HussainAkhtarWahid That's incorrect. The ordering of a set depends entirely on the implementation of a set. See for example the differences between `TreeSet`, `HashSet`, and `LinkedHashSet`. — Jason C, Nov 07 '13 at 08:18
It is scary to think that the OP may be interviewing for whatever job this is. — Jason C, Nov 07 '13 at 08:19
@JasonC : yeah , exactly , set is not ordered means , sets do not gaurantee the order you input the elements while iterating the sets , so sets do not maintain the order , thus are unordered — Hussain Akhtar Wahid 'Ghouri', Nov 07 '13 at 14:31

score 9 · Answer 1 · answered Nov 06 '13 at 12:41

Hash sets are not supposed to be sorted.

Technically they are sorted, but by the hash code (or a hash reduction thereof); and on hash collisions they may overflow into other buckets.

If you want an ordered set, use TreeSet instead. It usually is a bit slower, but sorted. If you want to retain the insertion order, use a List such as ArrayList or LinkedList.

There also is a hybrid, called LinkedHashSet, which allows fast contains operations, but maintains insertion order. Note that it won't have duplicates though.

He should use a `LinkedHashSet` to maintain the insertion order. — Petar Minchev, Nov 06 '13 at 12:43

score 5 · Accepted Answer · edited May 23 '17 at 12:14

5

From the JavaDocs:

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time. This class permits the null element.

if you intended to keep order better use TreeSet (but complexity will be log(n)

also check this post Hashset vs Treeset

EDIT as pointed out by @Petar in order to maintain insertion order better use LinkedHashSet

and this Dzone Article demonstrates comparison between all three with nice suit of example and performance

edited May 23 '17 at 12:14

Community

1
1

answered Nov 06 '13 at 12:41

exexzian

7,782
6
41
52

1

He should use a `LinkedHashSet` to maintain the insertion order, not a `TreeSet`. – Petar Minchev Nov 06 '13 at 12:45
@PetarMinchev yeah thanks for the pointer, now updated my answer – exexzian Nov 06 '13 at 12:51

score 3 · Answer 3 · answered Nov 06 '13 at 12:42

3

Use a LinkedHashSet to maintain the insertion order.

answered Nov 06 '13 at 12:42

Petar Minchev

46,889
11
103
119

Prabhakaran Ramaswamy · Answer 4 · 2013-11-06T12:48:31.570

1

Use TreeSet<String>(); or TreeSet<String>(String.CASE_INSENSITIVE_ORDER); if you want to Sort the elements. Use List instead of Set If you need to maintain the insertion order.

edited Nov 06 '13 at 12:48

answered Nov 06 '13 at 12:41

Prabhakaran Ramaswamy

25,706
10
57
64

He should use a `LinkedHashSet` to maintain the insertion order, not a `List`. – Petar Minchev Nov 06 '13 at 12:45
I think he wants to maintain the insertion order, not to sort. – Petar Minchev Nov 06 '13 at 12:47
`List` allows duplicates which is not desired as implied by the OP's original use of `Set` – Poniros Mar 18 '21 at 10:27

Unsorted HashSet in Java

4 Answers4