Objectives

Students will be able to:

  • Understand the fundamental characteristics of sets, including their unordered nature and the uniqueness of elements
  • Operations: union, intersection and difference
  • Code to check if an element is in a set, to add an element to a set, to remove an element, and to check whether one set is a subset/superset of another set

Abstract Data Types

HashSets

In the last unit we looked at how a Hash Table is a nice alternative to other data structures that require fast access, especially when searching.

This is especially true when collisions can be avoided, which is almost impossible. However, a good hashing function can reduce the opportunity for collisions.

Collision resolution strategies such as Linear Polling and Separate Chaining can be used.

Also, when the Load Factor of a hash table passes a threshold, the table is resized with every item in the table being rehashed.

But which Abstract Data Types use Hash Tables in their implementation?

One ADT is the HashSet.

Worksheet

Use the following files to setup a new project, HashSetProject, in your IDE.

Union/Intersection/Difference

Now we know a little about subsets/supersets using the HashSet class's containsAll method.

We can also:

Union

Set set1 = {"Australia", "Canada", "USA"};

Set set2 = {"Australia", "UK", "France"};

set1.addAll(set2);

Will produce a HashSet containing {"Australia", "Canada", "USA", "UK", "France"}

Intersection

Set set1 = {"Australia", "Canada", "USA"};

Set set2 = {"Australia", "UK", "France"};

set1.retainAll(set2);

Will produce a HashSet containing {"Australia"}

Difference

Set set1 = {"Australia", "Canada", "USA"};

Set set2 = {"Australia", "UK", "France"};

set1.removeAll(set2);

Will produce a HashSet containing {"Canada","USA"}

Glossary

object

property

method

create an object/instance of a class

instantiate an object

encapsulate

access

mutate

abstraction

Exercises

Tags

idesyntax file class instantiate constructor type propertymethod