HashSet Introduction — Collections and Generics

Prof: Can you think of any situation where you wouldn’t want duplicates in a collection? Where you only care whether an element is present at least once?

Student: Maybe a list of all the CSE courses at UC San Diego? A course can’t be in the catalog twice.

Prof: Good example. Let’s use that to introduce another type of collection in Java, the HashSet.

import java.util.HashSet;

HashSet<String> courses = new HashSet<String>();
int count;
String all;
void main() {
  courses.add("CSE 11");
  courses.add("CSE 12");
  courses.add("CSE 11");
  count = courses.size();
  all = courses.toString();
}

Prof: What do you notice about the count and output from toString?

Student: Even though we added CSE 11 twice, it only shows up in the HashSet once.

Prof: Exactly. Unlike an ArrayList, HashSet can’t contain duplicate elements. Also, the add() method for HashSet returns whether or not the element could be added.

import java.util.HashSet;

HashSet<String> courses = new HashSet<String>();
boolean first = courses.add("CSE 11");
boolean second = courses.add("CSE 11");

Student: So, when courses was empty, the first add() appended “CSE 11”, but the second time nothing changed and it returned false.

Prof: Almost, but I notice you said appended, but that isn’t really the right word. HashSet is unordered, so when an element is added it doesn’t necessarily get appended to the end.

Student: Am I able to use contains() like we did with ArrayList?

Prof: Yep. And contains() is usually why programmers choose to use a HashSet, since determining whether or not a HashSet contains a given value can be much faster than checking an array or ArrayList. We won’t go over the specifics in this class, but it is good to remember that the advantage of a HashSet is faster contains() and remove().

Student: For ArrayList, remove() took an index as the argument. But you said that HashSet doesn’t have indexes?

Prof: Right, so for remove() the argument is instead the element you would like to remove.

import java.util.HashSet;

HashSet<String> courses = new HashSet<String>();
boolean hasCse11;
boolean removed;
boolean removedAgain;
boolean stillHasCse11;
int count;
void main() {
  courses.add("CSE 11");
  courses.add("CSE 12");

  hasCse11 = courses.contains("CSE 11");
  removed = courses.remove("CSE 11");
  removedAgain = courses.remove("CSE 11");
  stillHasCse11 = courses.contains("CSE 11");
  count = courses.size();
}

Prof: How about you try creating a set of Integer, and then writing a for-each loop to sum all of the values in the HashSet. For-each loops work on ArrayList as well.

import java.util.HashSet;

HashSet<Integer> scores = new HashSet<Integer>();
int total;
void main() {
  scores.add(90);
  scores.add(75);
  scores.add(90);
  scores.add(60);

  total = 0;
  for (int score : scores) {
    total += score;
  }
}

Prof: Now here’s a question: What order did you sum the scores in?

Student: Well I assume it did 90 + 75 + 60, since that was the order I put them into the HashSet, and second time I tried to add 90 it was already in the set.

Prof: Not necessarily, because the set is unordered, we don’t know what order it did the summation. But in this case, addition doesn’t result in a different value when you change the order.

Prof: Here, look at this example. Now we are going to create a set of Point, what do you think the size() for points will return?

import java.util.HashSet;

record Point(int x, int y) { }

HashSet<Point> points = new HashSet<Point>();
int count;
void main() {
  points.add(new Point(1, 2));
  points.add(new Point(1, 2));
  points.add(new Point(2, 1));
  count = points.size();
}

Student: So count is 2. The two new Point(1, 2) are different objects, but the set only kept one of them.

Prof: Right. Two records with the same fields count as the same element, and so do two Strings with the same text. That works for String and for records. For a class you write yourself, it takes more work to make a set treat two objects as the same, and we won’t get into that here.

Prof: Now that we have learned about both ArrayList and HashSet, here is a nice trick that uses both of them. If we create an ArrayList, we can add duplicate elements to it. Normally with an array, if I asked you to give me a new array with all the duplicates removed what would you have to do?

Student: I would probably create an empty array, then loop through the old one and add any that aren’t already in the new array. But then I would have to write another for-loop that checks if the new array already has that element…

Prof: Well, here’s the helpful trick: You can create a HashSet from an ArrayList like this.

import java.util.ArrayList;
import java.util.HashSet;

ArrayList<String> requests = new ArrayList<String>();
HashSet<String> distinct;
int total;
int offered;
void main() {
  requests.add("CSE 11");
  requests.add("CSE 12");
  requests.add("CSE 11");
  requests.add("MATH 18");
  requests.add("CSE 12");

  distinct = new HashSet<String>(requests);
  total = requests.size();
  offered = distinct.size();
}

Student: Ok I see.

Prof: HashSet is an important tool to keep in your Java toolbox. Remember that while ArrayList is needed when the position in your list matters, HashSet is better for questions about whether or not an element is present.

Practice

The list below has repeats. Fill in the code that builds a HashSet from it, and then sets offered to the number of distinct names.

import java.util.ArrayList;
import java.util.HashSet;

ArrayList<String> names = new ArrayList<String>(
List.of("Ada", "Grace", "Ada", "Alan", "Grace", "Ada"));

HashSet<String> distinct = new HashSet<String>();
int total = names.size();
int offered = ;

Once that program has run, what are the values of total and offered?

total =
offered =