COMP 210: Data Structures

Set Abstract Data Type

Mathematics:

In mathematics, a Set is a collection of distinct, well-defined elements. The order of elements is not important. Thus the set {1, 2, 3} is equivalent to the set {3, 2, 1}. The set {1, 2, 2, 3} is also equivalent to set {1, 2, 3}, since both have the same 3 distinct (different) elements. The repeated element is ignored. The basic Set operations in mathematics are: union, intersection, and difference.

Computing:

In computing, a Set is an abstract data type that stores a collection of unique elements. The key, defining characteristic of a Set is that it contains no duplicates. In general, sets are unordered, so there is no index-based access. Operations include adding to the set, removing from the set, and checking for membership. Since Set data structures do not have duplicates, the add operation must either ignore duplicates or raise an exception.

The Java Set Interface

Java has a Set interface that models the mathematical set abstraction. The java.util.Set interface extends the java.util.Collection interface, imposing the crucial restriction that it cannot contain duplicate elements.

The mathematical operations of union, intersection, and difference are implemented using the operations addAll(), retainAll(), and removeAll, It is important to note, though, that these operations modify the set on which they are called, unlike the mathematical functions.

Provided Set Classes in Java

The Java Collections Framework includes several classes that implement the Set interface.

• HashSet: Uses a hash table for storage, offering fast performance for basic operations like add(), remove(), and contains(). It does not maintain any element order.

• LinkedHashSet: Extends HashSet but maintains the insertion order of elements. This means elements are iterated in the order they were added.

• TreeSet: Implements the SortedSet interface (which extends Set). It stores elements in a sorted order, either naturally (if elements are Comparable) or according to a custom Comparator.

More Information

For more information, see the Java documentation for the Set interface and its classes. Many other resources are available online, including GeeksForGeeks and W3Schools, for example.