Questions

• Reading?
• Quiz?
• Homework?

Concept - Sets

• A set organizes its elements for efficiency
• Elements may not be in the order in which they were added
• Can not contain duplicates
  • An added duplicate is ignored

Concept - Set interface

• Set interface extends the Collection interface
• So it has the same methods we saw earlier, including
  • size()
  • add()
  • remove()
  • contains()
  • iterator()

Activity - Set implementations

Record your participation in Piazza clicker question Lesson24 Q1

There are two classes in the Java library that implement the Set interface. What are they? Click all that apply. (section 15.3)

1. HashSet
2. MapSet
3. LinkedSet
4. TreeSet
5. ArraySet
6. ListSet

Concept - HashSet

• HashSet implements the Set interface using a hash table
• What is a hash table?
• Objects of classes that override the Object's hashCode method can be put into a HashSet
• HashSet has a type parameter like other Collection classes

  Set<String> names = new HashSet<String>();
  Set<Rectangle> boxes = new HashSet<>();   
      

• Notice that the HashSet object is assigned to a Set reference
  • Good programming practice

 

Concept - TreeSet

• TreeSet implements the Set interface using a binary search tree.
• Elements are stored in sorted order
• Linked nodes are used
• Not arranged in a linear sequence but in a tree shape
• Use a TreeSet when you need to visit the nodes in order.
• Otherwise use a HashSet

 

Activity - Use a set?

Record your participation in Piazza clicker question Lesson24 Q2

I want to keep a collection of all my grades for a course I am taking. Since we just learned about sets, I want to try to use a HashSet. Will that work? Think about why or why not.

• yes
• no

Activity - Spell check

Record your participation in Piazza clicker question Lesson24 Q3

In your text in section 15.3.2, Dr Horstmann implements a spell check application (opens in a new window) using sets. Could the implementation use an ArrayList for documentWords instead? Think about why or why not.

• yes
• no

Activity - Which Set implementation?

Record your participation in Piazza clicker question Lesson24 Q4

I want to print all the unique words in a text in alphabetical order. Can I use a set? If so, which implementation should I use?

1. no
2. yes, HashSet
3. yes, TreeSet
4. yes, LinkedSet

Activity - SpellCheck

Record your participation in Piazza clicker question Lesson24 Q5

Suppose you wanted the misspelled words in aphabetical order. You would need to change line 40 of the SpellCheck program to use a TreeSet instead of a HashSet.

Set<String> words = new HashSet<>(); // current line 40

Set<String> words = new TreeSet<>(); // new line 40

What else would need to change?

1. everything
2. nothing except add an import for TreeSet
3. the return type of the readWords method
4. it won't compile

 

How would the output change?

Activity - Sets

Record your participation in Piazza clicker question Lesson24 Q6

What is wrong with the following test to check whether the Set<String> names contains the elements "Thomas", "Diana", and "Harry" and only those elements?

if (words.toString().equals("[Thomas, Diana, Harry]")) . . .

1. There is no equals method for Sets
2. A set might contain the elements in a different order
3. All elements in a set are unique
4. "Thomas" will be printed last because it is longest

Concept - Binary Search Tree

Tree

• is a non-linear data structure consisting of linked nodes
• each node can have child nodes.
• each tree has one root which is the ancestor of all the nodes.

Binary Tree

• A tree where each node has at most 2 children
• Each node has left and right child

Binary Search Tree

• all the descendants ( the child node and all its children) to the left of a node have smaller data values than the node itself.
• And the descendants to the right have larger data values.