A set is simply a collection of unique objects. Unique means that no two objects can have the same value(s). Depending on the implementation of the set, it may or may not be ordered. The Java set, as an Abstract Data Type (ADT), has a few key operations (where T represents any data type e.g. int, String, or any class object):
boolean add(T item): returns true if the item is successfully added to the set, and false if the item was already in the set.
boolean remove(T item): returns true if the item was successfully removed from the set and false otherwise (if the item was not in the set).
boolean contains(T item): returns true if the item is in the set and false otherwise.
boolean isEmpty(): returns true if the set is empty and false otherwise.
The sets in Java have pretty self-explanatory function signatures (as they should). If you add two identical items to a set, then only the first added item will be in the set. All subsequent attempts to add the same item would be ignored unless the item is first removed. One of the most commonly used set operations is checking if an item is within a given set. The contains() function gives a great runtime for this: O(1) or O(log n) time complexity depending on if the implementation used is a HashSet or a TreeSet, respectively.
So what might a set be used for? Well, if you ever need to keep track of many distinct objects--such as IDs, names, or other unique identifiers--and frequently check if an item exists in such a collection, then a set is likely a good choice.
Here’s an example use case of a set:
Imagine that you have a list of Student objects representing all the students in a given class. Each Student might have a unique name (string) and grade (int) for this class. If you wanted to reference a list of all A students (grade >=90) frequently, then it would be tedious to loop through this list and check every student’s grade every time. Instead, you might use a HashSet of strings which keeps track of all A students in the class, as such:
Every time the students’ grades are updated, you can simply check if the Student’s new grade is greater than or equal to 90 or not.
If so, add them to the set of A students using add()
If they were already an A student, then this operation is simply ignored.
If not, then remove them from the set of A students using remove()
If they were not an A student at this point, then this operation is simply ignored.
With such a system, you would always have an up-to-date set of all ‘A’ students in your class. If you wanted to check if Johnny Appleseed was doing well in your class, you could easily do so by calling contains(“Johnny Appleseed”) on the set.
Of course, this is just one example of a use case for a set, and this specific problem of keeping track of A students could be solved in other ways.
Implementations: HashSet in Java and Java TreeSet Examples
Both the HashSet in Java and the TreeSet in Java come in the java.utils package. You can import them as such:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
or
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
The key difference between the Java HashSet and Java TreeSet is that the TreeSet is sorted, whereas the HashSet is not. This is why the TreeSet has O(log n) time complexity for key operations, whereas HashSet has O(1) or constant time complexity; the TreeSet must maintain order at all times.
In addition to the key set operations mentioned earlier, both the HashSet and TreeSet in Java have a few other helpful functions:
void clear(): clears the set of all objects.
int size(): returns the number of objects in the set.
Object clone(): returns a shallow copy of the set.
Iterator iterator(): returns an iterator to the set, starting at the first object.
You can imagine finding uses for these functions in the “list of A students” example: you could call size() if you wanted to see how many ‘A’ students you had, or clear() if you wanted to clear the list at the end of the semester. You might use clone() to create and keep a clone of the list of A students at a specific point in time, such as during midterm reports (this way the clone doesn’t stay up-to-date along with the original).
Java HashSet Example
Here’s a short example of a HashSet of Strings being used in Java:
import java.util.HashSet;
class HashSetDemo {
public static void main(String[] args)
{
// create a HashSet of Strings
HashSet<String> hs = new HashSet<String>();
// Add elements using the add() method
hs.add("Collin");
hs.add("Bob");
hs.add("Abigail");
// Duplicates will ignored; this statement is useless
hs.add("Collin");
System.out.println(hs);
System.out.println("Bob is in the set (T/F): " + hs.contains("Bob"));
System.out.println("Max is in the set (T/F): " + hs.contains("Max"));
}
}
Output:
--------
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Java TreeSet example
Java set example could help you to understand the theory. Here is the short example of a TreeSet of Strings being used in Java:
import java.util.TreeSet;
class TreeSetDemo {
public static void main(String[] args)
{
// create a TreeSet of Strings
TreeSet<String> ts = new TreeSet<String>();
// Add elements using the add() method.
ts.add("Collin");
ts.add("Bob");
ts.add("Abigail");
// Duplicates will ignored; this statement is useless
ts.add("Collin");
// printing the set prints the names in alphabetical order!
System.out.println(ts);
System.out.println("Bob is in the set (T/F): " + ts.contains("Bob"));
System.out.println("Max is in the set (T/F): " + ts.contains("Max"));
System.out.println("Size of the set: " + ts.size());
ts.clear();
System.out.println("Size of the set after clear(): " + ts.size());
}
}
Output:
-------
[Abigail, Bob, Collin]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Size of the set: 3
Size of the set after clear(): 0
GO TO FULL VERSION