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

(line 141). The variable current points to the element in the list. Initially, current is 0
(line 135), which points to the first element in the list. MyHashSetIterator implements
the methods hasNext() , next() , and remove() in java.util.Iterator . Invoking
hasNext() returns true if current < list.size() . Invoking next() returns the current
element and moves current to point to the next element (line 153). Invoking remove()
removes the current element in the iterator from the set.
The hash() method invokes the supplementalHash to ensure that the hashing is evenly
distributed to produce an index for the hash table (lines 166-174). This method takes O (1)
time.
Table 27.2 summarizes the time complexity of the methods in MyHashSet .

hash

T ABLE 27.2

Time Complexities for
Methods in MyHashSet

Methods Time

O ( capacity )

clear()

contains(e: E) O (1)

add(e: E) O (1)

remove(e: E) O (1)

O (1)

isEmpty()

size() O (1)

iterator() O ( capacity )

rehash() O ( capacity )

Listing 27.6 gives a test program that uses MyHashSet .

L ISTING 27.6

TestMyHashSet.java
1 public class TestMyHashSet {
2 public static void main(String[] args) {
3 // Create a MyHashSet
4 MySet<String> set = new MyHashSet<>();
5 set.add( "Smith" );
6 set.add( "Anderson" );
7 set.add( "Lewis" );
8 set.add( "Cook" );
9 set.add( "Smith" );
10
11 System.out.println( "Elements in set: " + set);
12 System.out.println( "Number of elements in set: " + set.size());
13 System.out.println( "Is Smith in set? " + set.contains( "Smith" ));
14
15 set.remove( "Smith" );
16 System.out.print( "Names in set in uppercase are " );
17 for (String s: set)
18 System.out.print(s.toUpperCase() + " " );
19
20 set.clear();
21 System.out.println( "\nElements in set: " + set);
22 }
23 }

create a set
add elements

display elements
set size

remove element

foreach loop

clear set