Sets in Java

What is an abstract data type (ADT)?

Every data structure can be described by answering two questions:

1. What can I do with it? Its operations, and what each one gives back. For a set: add a value, remove a value, ask "Is this value in it?", and count the values.
2. How is it stored inside the computer? For a set, it could be an array, a tree, or a hash table. Any of these can work.

An abstract data type (ADT) answers only the first question. "Abstract" means "the idea only, without the details". So the ADT says what you can do, not how it is done. The second question is answered by the code that builds it, called the implementation.

This table matches the store to a set:

Why split it this way? You can use a set without knowing how it is built, just as you can buy at any sari-sari store without seeing its shelves. And the way it is built can be changed later (to make it faster) without changing the code that uses it.

You already met this idea in the Stacks lesson: what made a stack a stack was the rule "push, pop, peek", not whether it was built with an array or a linked list. Now the idea has a name. A set is described the same way: "add, remove, contains".

Good to know: this course calls stacks and queues data structures and sets and maps abstract data types. Many books call stacks and queues ADTs too, because they can also be described only by what you can do with them. Both views are correct.

The two properties

Every set has these two properties:

1. Uniqueness. Each value appears at most once (like the second Ana in the list vs. set picture ). Adding a value that is already there does nothing.
2. Unordered. Items have no position (no place in line). In a list or an array, every item has an index: [0] is the first item, [1] is the second, and so on. A set has no index, so it has no "first" item. You can only ask "Is this value in the set?" That is why {1, 2, 3} and {3, 1, 2} are the same set.

Review: subsets (extra)

Extra topic. Subsets go a little beyond this course's required set topics (properties, union, intersection, difference, symmetric difference). Study it if you have time; your teacher will tell you if a quiz or exam uses it.

You may remember subsets from math class. Here is a quick review, because Java can check them too (Part 3).

Here are the words and symbols that go with subsets, using the sets in the picture:

Two facts are easy to forget:

• The empty set { } (the set with nothing in it) is a subset of every set. It has no value that could be missing from B.
• Every set is a subset of itself (B ⊆ B), but not a proper subset of itself.

Set operations in Java

Java does not have methods named "union" or "intersection". Instead, three methods do the work. Each one changes the set it is called on:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class SetOperations {
  public static void main(String[] args) {
    Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
    Set<Integer> b = new HashSet<>(Arrays.asList(4, 5, 6, 7));

    Set<Integer> union = new HashSet<>(a);   // copy of A
    union.addAll(b);                         // add all of B
    System.out.println("A u B = " + union);  // [1, 2, 3, 4, 5, 6, 7]

    Set<Integer> inter = new HashSet<>(a);
    inter.retainAll(b);                      // keep only what B has
    System.out.println("A n B = " + inter);  // [4, 5]

    Set<Integer> aMinusB = new HashSet<>(a);
    aMinusB.removeAll(b);                    // take out B's values
    System.out.println("A - B = " + aMinusB); // [1, 2, 3]

    Set<Integer> bMinusA = new HashSet<>(b);
    bMinusA.removeAll(a);
    System.out.println("B - A = " + bMinusA); // [6, 7]

    Set<Integer> sym = new HashSet<>(union); // A u B ...
    sym.removeAll(inter);                    // ... minus A n B
    System.out.println("A sym B = " + sym);  // [1, 2, 3, 6, 7]

    System.out.println("A is still " + a);   // [1, 2, 3, 4, 5]
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class SetOperations to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

The code prints u, n, and sym instead of ∪, ∩, and △, because some consoles cannot show those symbols. Small whole numbers like these usually come out in increasing order from a HashSet, but that is not guaranteed (the names in the attendance example did not). The values are what matter, not their order.

Subsets in Java (extra)

Extra topic, like the subsets review in Part 1.

Java has no method named "subset". You check A ⊆ B with containsAll. This table shows each subset question in Java:

Watch the direction: A ⊆ B is written b.containsAll(a), so the bigger set goes first. And unlike addAll, retainAll, and removeAll, containsAll changes nothing. It only answers true or false, so no copy is needed.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class Subsets {
  public static void main(String[] args) {
    Set<String> b = new HashSet<>(Arrays.asList("Ana", "Ben", "Carla", "Dan"));
    Set<String> a = new HashSet<>(Arrays.asList("Ana", "Ben"));
    Set<String> c = new HashSet<>(Arrays.asList("Ana", "Eve"));
    Set<String> empty = new HashSet<>();

    System.out.println(b.containsAll(a));     // true:  A is a subset of B
    System.out.println(b.containsAll(c));     // false: Eve is not in B
    System.out.println(b.containsAll(empty)); // true:  { } is a subset of every set
    System.out.println(a.containsAll(a));     // true:  every set is a subset of itself

    boolean proper = b.containsAll(a) && !a.equals(b);
    System.out.println(proper);               // true:  A is a proper subset of B

    Set<String> d = new TreeSet<>(Arrays.asList("Dan", "Carla", "Ben", "Ana"));
    System.out.println(b.equals(d));          // true:  same values (order and class don't matter)

    System.out.println(b.contains("Ana"));    // true:  one value, so contains
    System.out.println(a.size() + " " + b.size()); // 2 4: containsAll changed nothing
  }
}

▶ Try it in the Programiz online compiler: tap Copy, paste it there, change public class Subsets to public class Main (Programiz saves your code as Main.java, and Java needs the file name and the public class name to match), then press Run.

equals ignores order, and even the class: a HashSet and a TreeSet with the same values are equal.