HASHING - Introduction to Java Programming: Comprehensive Version - page 1009

223 public String toString() {
224 java.util.ArrayList<E> list = setToList();
225 StringBuilder builder = new StringBuilder( "[" );
226
227 // Add the elements except the last one to the string builder
228 for ( int i = 0 ; i < list.size() - 1 ; i++) {
229 builder.append(list.get(i) + ", " );
230 }
231
232 // Add the last element in the list to the string builder
233 if (list.size() == 0 )
234 builder.append( "]" );
235 else
236 builder.append(list.get(list.size() - 1 ) + "]" );
237
238

toString

return builder.toString();

239 }
240 }

The MyHashSet class implements the MySet interface using separate chaining. Imple-
menting MyHashSet is very similar to implementing MyHashMap except for the following
differences:

MyHashSet vs. MyHashMap

1. The elements are stored in the hash table for MyHashSet , but the entries (key/value
pairs) are stored in the hash table for MyHashMap .

2. MySet extends java.lang.Iterable and MyHashSet implements MySet and over-
rides iterator() . So the elements in MyHashSet are iterable.

Three constructors are provided to construct a set. You can construct a default set with the
default capacity and load factor using the no-arg constructor (lines 26-28), a set with the
specified capacity and a default load factor (lines 32-34), and a set with the specified capacity
and load factor (lines 38-46).
The clear method removes all elements from the set (lines 49-52). It invokes
removeElements() , which clears all table cells (line 190). Each table cell is a linked list
that stores the elements with the same hash code. The removeElements() method takes
O ( capacity ) time.
The contains(element) method checks whether the specified element is in the set by
examining whether the designated bucket contains the element (lines 55-65). This method
takes O (1) time.
The add(element) method adds a new element into the set. The method first checks if
the element is already in the set (line 69). If so, the method returns false. The method then
checks whether the size exceeds the load-factor threshold (line 72). If so, the program invokes
rehash() (line 76) to increase the capacity and store elements into the new larger hash table.
The rehash() method first copies all elements in a list (line 197), doubles the capacity
(line 198), creates a new hash table (line 199), and resets the size to 0 (line 200). The method
then copies the elements into the new larger hash table (lines 202-204). The rehash method
takes O ( capacity ) time. If no rehash is performed, the add method takes O (1) time to add a
new element.
The remove(element) method removes the specified element in the set (lines 95-114).
This method takes O (1) time.
The size() method simply returns the number of elements in the set (lines 122-124). This
method takes O (1) time.
The iterator() method returns an instance of java.util.Iterator . The
MyHashSetIterator class implements java.util.Iterator to create a forward iterator.
When a MyHashSetIterator is constructed, it copies all the elements in the set to a list

three constructors

clear

contains

add

rehash

remove

size

iterator