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

27.8 Implementing Set Using Hashing
A hash set can be implemented using a hash map.

Key
Point

A set (introduced in Chapter 21) is a data structure that stores distinct values. The Java Collections
Framework defines the java.util.Set interface for modeling sets. Three concrete implemen-
tations are java.util.HashSet , java.util.LinkedHashSet , and java.util.TreeSet .
java.util.HashSet is implemented using hashing, java.util.LinkedHashSet using
LinkedList , and java.util.TreeSet using red-black trees.
You can implement MyHashSet using the same approach as for implementing MyHashMap .
The only difference is that key/value pairs are stored in the map, while elements are stored in
the set.
We design our custom Set interface to mirror java.util.Set and name the interface
MySet and a concrete class MyHashSet , as shown in Figure 27.10.

hash set
hash map
set

MySet
MyHashSet

«interface»
java.lang.Iterable<E>

+ iterator(): java.util.Iterator<E>

«interface»
MySet<E>

+ clear(): void Removes all elements from this set.

Returns true if the element is in the set.
Adds the element to the set and returns true if the element is added
successfully.

+ contains(e: E): boolean

+ add(e: E): boolean

+ remove(e: E): boolean

+ isEmpty(): boolean Returns true if this set does not contain any elements.

Returns the number of elements in this set.

+ size(): int

MyHashSet<E>

+MyHashSet() Creates an empty set with default capacity 4 and default load

factor threshold 0.75f .

+MyHashMap(capacity: int)

Creates a set with a specified capacity and default load factor
threshold 0.75f .

+MyHashMap(capacity: int,
loadFactorThreshold: float)

Creates a set with a specified capacity and load factor threshold.

F IGURE 27.10 MyHashSet implements the MySet interface.

Listing 27.4 shows the MySet interface and Listing 27.5 implements MyHashSet using
separate chaining.

L ISTING 27.4

MySet.java
1 public interface MySet<E> extends java.lang.Iterable<E> {
2

/** Remove all elements from this set */

3 public void clear();

clear

4
5 /** Return true if the element is in the set */