JCH
Java Community | Help. Code. Learn.•2w ago
JavaBot

Week 120 — What are the differences between `HashSet` and `TreeSet`?

Question of the Week #120
What are the differences between HashSet and TreeSet?
5 Replies
KineticMate
KineticMate•2w ago
Sets are collections of objects that are not allowed to contain duplicates with operations for adding and removing element as well as checking whether or not a set contains an element. HashSet is an unordered Set that can do these operations (adding, removing, checking for containment) in constant (O(1)) time assuming the element classes implement equals() and hashCode() properly. This means that having more elements in a HashSet doesn't make adding. removing or checking for existence take longer. TreeSet is a sorted Set where elements are sorted using a custom Comparator or using their compareTo method (if the element class implements compareTo). Keeping the elements sorted comes at the cost of the aforementioned set operations (add, remove, contains) need to be done with a time complexity of O(log(n)). Another Set implementation is LinkedHashSet which extends HashSet but keeps track of the insertion order meaning that it is possible to iterate over its elements in the order they have been added to the set. When executing the following code with someSet being a HashSet, the elements are not ordered (e.g. [here, some, Hello, text, World]). With TreeSet, the Strings are sorted lexicographically with uppercase letters before lowercase letters resulting in it printing [Hello, World, here, some, text]. With LinkedHashSet, the insertion order is kept and it prints [Hello, World, here, some, text]. 
Set<String> someSet = new HashSet<>();
//Set<String> someSet = new TreeSet<>();
//Set<String> someSet = new LinkedHashSet<>();
someSet.add("Hello");
someSet.add("World");
someSet.add("some");
someSet.add("text");
someSet.add("here");
System.out.println(someSet);
Set<String> someSet = new HashSet<>();
//Set<String> someSet = new TreeSet<>();
//Set<String> someSet = new LinkedHashSet<>();
someSet.add("Hello");
someSet.add("World");
someSet.add("some");
someSet.add("text");
someSet.add("here");
System.out.println(someSet);
📖 Sample answer from dan1st
KineticMate
KineticMate•2w ago
i may be writing nonsense and approaching the matter wrongly, but I have found that in the hash set the elements are arranged in a random order, while in the tree set they are in a fixed, ascending order
Submission from capitainfox.dev
KineticMate
KineticMate•2w ago
HashSet is a set which takes the elements in random order in O(1) time complexity while TreeSet is a set which maintains the sorted order of elements in O(log n) time complexity
Submission from santamurderer2
KineticMate
KineticMate•2w ago
HashSet & TreeSet are both implementations of the java.util.Set interface. Like all implementations of Set, only unique elements are allowed. However, a TreeSet also provides predictable iteration order and other navigation primitives.
KineticMate
KineticMate•2w ago
In addition to Set, the TreeSet implements both SortedSet and NavigableSet. SortedSet guarantees the sort and iteration order of its elements. The order is determined by the elements' natural order, or by a Comparator provided at construction time. NavigableSet defines additional methods to navigate through the elements in the Set. Because the elements are in a predictable order, the navigation methods also behave predictably.
⭐ Submission from dangerously_casual

Did you find this page helpful?