Set and its implementations in Java
Set that we studied in our math classes in high school, contains no duplicates. Unlike list, a set doesn’t remember where you inserted the elements means it does not remember the insertion order.
- Set cares about uniqueness
- Does not allow duplicates
-
equal()
method determines whether two object are equal or not.
A set is an interface in java that contains no duplicates elements. More formally, sets contain no pair of elements e1
and e2
such that e1.equals(e2)
and at most one null
element.
Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.
Concrete classes for Set
- HashSet
- LinkedHashSet
- TreeSet
HashSet
Class HashSet<E>
E – the type of elements maintained by this set
- Unsorted (no guarantees as to the iteration order of the set) and Unordered (not guarantee that the order will remain constant over time) set.
-
Permit
null
element -
This class offers constant time performance for the basic operations (
add
,remove
,contains
andsize
), assuming the hash function disperses the elements properly among the buckets. -
It uses the hashcode of the object being inserted, so the more efficient your
hashCode()
implementation the better access performance you’ll get.
This implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator
throws a ConcurrentModificationException
. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. (We’ll see this with example)
Examples:
HashSetOfNames.java
– demonstrate the basic use of HashSet
package com.javalatte.itcuties.setinterface; import java.util.HashSet; import java.util.Set; public class HashSetOfNames { public static void main(String[] JavaLatte) { //Constructs a new, empty set; the backing HashMap instance has default //initial capacity (16) and load factor (0.75). Set<String> names = new HashSet<String>(); System.out.println("Is Charlie added " + names.add("Charlie")); System.out.println("Is Kumar added " + names.add("Kumar")); System.out.println("Is Cuties added " + names.add("Cuties")); System.out.println("Is Robert added " + names.add("Robert")); System.out.println("Is Bill added " + names.add("Bill")); System.out.println("Is William added " + names.add("William")); // Notice the output of this Hashset and in what order element are added System.out.println();//space System.out.println(names); //we'll try to add null element System.out.println();//space System.out.println("Is null added " + names.add(null)); //We'll try to add duplicate System.out.println();//space System.out.println("Is Kumar added again " + names.add("Kumar")); //remove, contains and size method System.out.println();//space System.out.println("Is Java element present: " + names.contains("Java")); System.out.println("Size of HashSet : " + names.size()); if (names.remove("Kumar")) { System.out.println("Kumar is removed, Size : " + names.size()); } else { System.out.println("Kumar is not removed, Size : " + names.size()); } } }
HashSetIteratorDemo.java
– demonstrate the use of Iterator
and ConcurrentModificationException
package com.javalatte.itcuties.setinterface; import java.util.HashSet; import java.util.Iterator; import java.util.Set; public class HashSetIteratorDemo { public static void main(String[] JavaLatte) { //Constructs a new, empty set; the backing HashMap instance has the //specified initial capacity and default load factor (0.75). Set<String> sites = new HashSet<String>(10); sites.add("Facebook"); sites.add("Twitter"); sites.add("Instagram"); sites.add("500px"); sites.add("PinInterest"); sites.add("Tumbler"); sites.add("Google+"); Iterator iter = sites.iterator(); //This will throw ConcurrentModificationException exception as iterator //is alread created. sites.add("Test"); // comment it to excute sites.remove("500px"); // comment it to excute while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println(); } }
LinkedHashSet
Class LinkedHashSet<E>
E – the type of elements maintained by this set
-
A
LinkedHashSet
is an ordered version ofHashSet
that maintains a doubly-linked List across all elements. -
Use this class instead of
HashSet
when you care about the iteration order. - This linked list defines the iteration ordering, which is the order in which elements were inserted into the set.
-
Permit
null
element.
Note that insertion order is not affected if an element is re-inserted into the set.
This implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator
throws a ConcurrentModificationException
. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. (We’ll see this with example)
Examples:
LinkedHashSetDemo.java
– demonstrate the basic use of LinkedHashSet
package com.javalatte.itcuties.setinterface; import java.util.LinkedHashSet; import java.util.Set; public class LinkedHashSetDemo { public static void main(String[] JavaLatte) { //Constructs a new, empty linked hash set with the default initial //capacity (16) and load factor (0.75). Set<String> tech = new LinkedHashSet<String>(); tech.add("Java"); tech.add("Oracle"); tech.add("PHP"); tech.add("C++"); tech.add(".Net"); tech.add("JavaScript"); //Notice the output of this LinkedHashset and in what order element //are added. Insertion order is maintained System.out.println(tech); //we'll try to add null element System.out.println();//space System.out.println("Is null added " + tech.add(null)); //We'll try to add duplicate System.out.println();//space System.out.println("Is Java added again " + tech.add("Java")); //remove, contains and size method System.out.println();//space System.out.println("Is Java element present: " + tech.contains("Java")); System.out.println("Size of HashSet : " + tech.size()); if (tech.remove("PHP")) { System.out.println("PHP is removed, Size : " + tech.size()); } else { System.out.println("PHP is not removed, Size : " + tech.size()); } } }
LinkedHashSetIterator.java
– demonstrate the use of Iterator
and ConcurrentModificationException
package com.javalatte.itcuties.setinterface; import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; public class LinkedHashSetIterator { public static void main(String[] JavaLatte) { List<String> compNames = new ArrayList<String>(); compNames.add("Dell"); compNames.add("HP"); compNames.add("Sony"); compNames.add("Lenovo"); compNames.add("Lenovo"); //LinkedHashSet(Collection<? extends E> c) //Constructs a new linked hash set with the same elements as the specified collection. Set<String> tech = new LinkedHashSet<String>(compNames); System.out.println(tech); System.out.println("Size : " + tech.size()); Iterator iter = tech.iterator(); //This will throw ConcurrentModificationException exception as iterator //is alread created. tech.add("Test"); // comment it to excute while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println(); } }
TreeSet
Class TreeSet<E>
E – the type of elements maintained by this set
The TreeSet
is one of two sorted collections (the other being TreeMap
). It uses a Red-Black tree structure, and guarantees that the elements will be in ascending order, according to natural order.
-
The elements are ordered using their natural ordering, or by a
Comparator
provided at set creation time, depending on which constructor is used. -
This implementation provides guaranteed log(n) time cost for the basic operations (
add
,remove
andcontains
). -
TreeSet
will not allownull
object. If you try to add null value i will be throwNullPointerException
.
This implementation is not synchronized. If multiple threads access a hash set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
The iterators returned by this class’s iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the Iterator
throws a ConcurrentModificationException
. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. (We’ll see this with example)
Examples:
TreeSetOrderDemo.java
– demonstrate the ordering of TreeSet
.
package com.javalatte.itcuties.setinterface; import java.util.Set; import java.util.TreeSet; public class TreeSetOrderDemo { public static void main(String[] JavaLatte) { //Constructs a new, empty tree set, sorted according to the //natural ordering of its elements. Set<String> names = new TreeSet<String>(); names.add("Charlie"); names.add("Kumar"); names.add("Cuties"); names.add("Robert"); names.add("Bill"); names.add("William"); //Notice the output of TreeSet would be in natural order System.out.println(names); Set<Integer> numbers = new TreeSet<Integer>(); numbers.add(13); numbers.add(1); numbers.add(124); numbers.add(-10); //Notice the output of TreeSet would be in natural order i.e, numeric System.out.println(numbers); } }
TreeSetComparator.java
, TreeSetLengthComparator.java
– demonstrate how to use comparator with TreeSet
.
package com.javalatte.itcuties.setinterface; import java.util.Set; import java.util.TreeSet; public class TreeSetComparator { public static void main(String[] JavaLatte) { Set<String> str = new TreeSet<String>(new TreeSetLengthComparator()); str.add("ABCDE"); str.add("ABC"); str.add("BC"); str.add("G"); str.add("GHIJKLK"); str.add("ABD"); //Output will be sorted according to the Comparator i.e, according to // length of the String System.out.println(str); } }
package com.javalatte.itcuties.setinterface; import java.util.Comparator; public class TreeSetLengthComparator implements Comparator<String> { public int compare(String o1, String o2) { return o1.length() - o2.length(); } }
TreeSetBasicOperationDemo.java
– demonstrate the basic methods of TreeSet
.
package com.javalatte.itcuties.setinterface; import java.util.TreeSet; public class TreeSetBasicOperationDemo { public static void main(String[] JavaLatte) { TreeSet<Integer> integerSet = new TreeSet<Integer>(); integerSet.add(100); integerSet.add(45); integerSet.add(454); integerSet.add(1); integerSet.add(5); integerSet.add(4); integerSet.add(453); integerSet.add(-5); integerSet.add(11); //output of TreeSet would be in natural order i.e, numeric System.out.println(integerSet); System.out.println(); //Returns the first (lowest) element currently in this set. System.out.println("first (lowest) element : " + integerSet.first()); System.out.println(); //Returns the last (highest) element currently in this set. System.out.println("last (highest) element : " + integerSet.last()); System.out.println(); //Returns the greatest element in this set less than or equal to the //given element, or null if there is no such element. System.out.println("greatest element <= 5 : " + integerSet.floor(5)); System.out.println(); //Returns the greatest element in this set strictly less than the //given element, or null if there is no such element. System.out.println("greatest element < 5 : " + integerSet.lower(5)); System.out.println(); //Retrieves and removes the first (lowest) element, //or returns null if this set is empty. System.out.println(integerSet); integerSet.pollFirst(); System.out.println("After pollFirst : " + integerSet); System.out.println(); //Retrieves and removes the last (highest) element, //or returns null if this set is empty. System.out.println(integerSet); integerSet.pollLast(); System.out.println("After pollLast : " + integerSet); } }
Download this sample code here.
you have done a great work but i think these codes can be a little simple.