9. Java Collections Framework

Programming Project 2021/22

9.4. Sets

Interface: `Set<E>`

Set is an abstract data structure that

stores a collection of values in no particular order and
prohibits repeated values.

It is an implementation of the mathematical concept of a finite set, which is typically used to test a value for membership.

Set, as a Java interface,

inherits methods from Collection and
prohibits duplicate elements.

`Set<E>`: Main methods

void clear(): Removes all of the elements from the set.
boolean contains(Object o): Returns true if the set contains the specified element.
boolean add(Object o): Adds the specified element to the set if it is not already present.
boolean isEmpty(): Returns true if the set contains no elements.
boolean remove(Object o) Removes the specified element from the set if it is present.
Iterator iterator() Returns an iterator over the elements in the set.
int size() Returns the number of elements in the set.

Classes: `HashSet`, `LinkedHashSet`, `TreeSet`

HashSet:

Implements Set
No order guaranteed

LinkedHashSet:

Implements Set
Extends HashSet
Insertion order maintained

TreeSet:

Implements OrderedSet
(Lexical) order maintained

Here is an example of how these three classes behave:

public static void main(String[] args) {
  Set<String> hashSet = new HashSet<>();
  hashSet.add("Joey");
  hashSet.add("Joey");
  hashSet.add("Rachel");
  hashSet.add("Monica");
  hashSet.add("Chandler");
  System.out.println("HashSet (no order guaranteed): " + hashSet);

  Set<String> linkedHashSet = new LinkedHashSet<>();
  linkedHashSet.add("Joey");
  linkedHashSet.add("Joey");
  linkedHashSet.add("Rachel");
  linkedHashSet.add("Monica");
  linkedHashSet.add("Chandler");
  System.out.println("LinkedHashSet (insertion order maintained): " + linkedHashSet);

  Set<String> treeSet = new TreeSet<>();
  treeSet.add("Joey");
  treeSet.add("Joey");
  treeSet.add("Rachel");
  treeSet.add("Monica");
  treeSet.add("Chandler");
  System.out.println("TreeSet (lexical order maintained): " + treeSet);
}

HashSet (no order guaranteed): [Rachel, Joey, Chandler, Monica]
LinkedHashSet (insertion order maintained): [Joey, Rachel, Monica, Chandler]
TreeSet (lexical order maintained): [Chandler, Joey, Monica, Rachel]

Class: `HashSet<E>`

A HashMap-based implementation of the Set interface.

Characteristics:

No repeated elements (from Set).
Stores elements using a HashMap.
Does not guarantee element order.
Allows null.
Implements all optional Set operations.

HashSet uses HashMap internally to store it’s objects.

The elements you add into a HashSet are stored as keys of this HashMap object and the values associated with those keys are a constant.

Class: `LinkedHashSet<E>`

A LinkedHashMap-based implementation of the Set interface.

Characteristics:

No repeated elements (from Set).
Its HashMap makeup guarantees unique elements.
Its LinkedList makeup guarantees insertion order.
Allows null.
Implements all optional Set operations.

When we invoke add() on a LinkedHashSet:

set.add(x);

It internally calls the put() method of its LinkedHashMap:

public boolean add(E e) {
  return m.put(e, PRESENT)==null;
}

Here is a demo of LinkedHashSet:

public static void main(String args[]) {
  // create a Hash set
  LinkedHashSet hs = new LinkedHashSet();
  
  // add elements to the LinkedHashSett
  hs.add("B");
  hs.add("A");
  hs.add("D");
  hs.add("E");
  hs.add("C");
  hs.add("F");
  hs.add("A");
  System.out.println(hs);
}

[B, A, D, E, C, F]

Interface: `SortedSet`

An extension of Set in which the elements are always sorted.

The elements are ordered using

their lexical ordering, or
a Comparator typically provided at sorted set creation time.

The set's iterator will traverse the set in ascending element order.

Class: `TreeSet<E>`

A TreeMap-based implementation of the OrderedSet interface.

Characteristics:

No repeated elements (from Set).
Its TreeMap component guarantees
- unique elements and
- ascending element order.
Does not allow null.
Implements all optional Set operations.

When we invoke add() on a TreeSet:

set.add(x);

It internally calls the put() method of its TreeMap:

public boolean add(E e) {
  return m.put(e, PRESENT)==null;
}

Here is a demo of TreeSet:

public static void main(String[] args) {
  TreeSet<String> treeSet = new TreeSet<>();
  treeSet.add("Red");
  treeSet.add("Blue");
  treeSet.add("Black");
  treeSet.add("Green");
  treeSet.add("Yellow");

  System.out.println("TreeSet: " + treeSet);

  String lowest = treeSet.first();
  System.out.println("Lowest element in the set: " + lowest);

  String highest = treeSet.last();
  System.out.println("Highest element in the set: " + highest);

  SortedSet<String> headSet = treeSet.headSet("Green");
  System.out.println("Subset with elements lower than \"Green\": " + headSet);

  SortedSet<String> tailSet = treeSet.tailSet("Green");
  System.out.println("Subset with elements higher or equal than \"Green\": " + tailSet);
}

TreeSet: [Black, Blue, Green, Red, Yellow]
Lowest element in the set: Black
Highest element in the set: Yellow
Subset with elements lower than "Green": [Black, Blue]
Subset with elements higher or equal than "Green": [Green, Red, Yellow]

You can find the solution to this exercise here.

Exercise 3

Revisit exercise 2 and remove all duplicates from a List dogs using a Set:

public class Dog {
  private String name;
  private int age;

  public Dog(String name, int age) {
    setName(name);
    setAge(age);
  }

  public String getName() {
    return name;
  }

  public void setName(String name) {
    this.name = name;
  }

  public int getAge() {
    return age;
  }

  public void setAge(int age) {
    if (age < 0 || age > 15)
      throw new IllegalArgumentException("Invalid age: " + age + ". Must be 0 <= age <= 15");
    this.age = age;
  }

  @Override
  public String toString() {
    return "(" + name + ", " + age + ')';
  }
}

public class Main {
  public static void main(String[] args) {
    Dog d1 = new Dog("King", 5);
    Dog d2 = new Dog("Rex", 7);
    Dog d3 = new Dog("Boss", 2);
    Dog d4 = new Dog("Duke", 11);

    
    List<Dog> dogs = new ArrayList<>();
    dogs.add(d1);
    dogs.add(d1);
    dogs.add(d2);
    dogs.add(d2);
    dogs.add(d3);
    dogs.add(d3);
    dogs.add(d4);
    dogs.add(d4);

    System.out.println(dogs);
    // => [(King, 5), (King, 5), (Rex, 7), (Rex, 7), (Boss, 2), (Boss, 2), (Duke, 11), (Duke, 11)]

    //FIX ME
    
    System.out.println(dogs);
    // => [(King, 5), (Rex, 7), (Boss, 2), (Duke, 11)]
  }
}

You can find the solution to this exercise here.

9.4. Sets

Interface: Set<E>

Set<E>: Main methods

Classes: HashSet, LinkedHashSet, TreeSet

Class: HashSet<E>

Class: LinkedHashSet<E>

Interface: SortedSet

Class: TreeSet<E>

Exercise 3

Interface: `Set<E>`

`Set<E>`: Main methods

Classes: `HashSet`, `LinkedHashSet`, `TreeSet`

Class: `HashSet<E>`

Class: `LinkedHashSet<E>`

Interface: `SortedSet`

Class: `TreeSet<E>`