Hashing as a Dictionary Implementation - Data Structures and Abstractions with Java - page 560

public void remove()
{

throw new UnsupportedOperationException();
} // end remove
} // end KeyIterator

Note: Hashing as an implementation of the ADT dictionary does not provide the ability to
sort its entries. Such an implementation is not suitable for any application that requires a
sorted iteration of the entries.

Java Class Library: The Class HashMap

22.18

The standard package java.util contains the class HashMap<K, V> . This class implements the
interface java.util.Map that we mentioned in Segment 19.22. Recall that this interface is similar
to our DictionaryInterface . HashMap assumes that the search-key objects belong to a class that
overrides the methods hashCode and equals .
The hash table is a collection of buckets, where each bucket can contain several entries. As you
know, a hash table's load factor is a measure of how full the table is. The constructors for HashMap

enable you to specify the initial number of buckets and the maximum load factor

λ

λ max . These con-

structors are as follows:

public HashMap()
Creates an empty hash table with a default initial size of 16 and a default maximum load factor of 0.75.

public HashMap( int initialSize)
Creates an empty hash table with a given initial size and a default maximum load factor of 0.75.

public HashMap( int initialSize, float maxLoadFactor)
Creates an empty hash table with a given initial size and a given maximum load factor.

public HashMap(Map<? extends K,? extends V> table)
Creates a hash table with the same entries as table .

The authors of HashMap chose a default maximum load factor of 0.75 to provide a balance
between time and memory requirements. Even though higher values of the load factor permit
smaller hash tables, they cause higher search times, which in turn reduce the efficiency of the get ,
put , and remove methods.
When the number of entries in the hash table exceeds

λ max times the number of buckets, the
size of the hash table is increased by using rehashing. But rehashing takes time. You can avoid
rehashing if you choose

Maximum number of entries in the dictionary
λ max

Number of buckets

-------------------------------------------------------------------------------------------------------------------------

>

Of course, too large a hash table wastes space.

Java Class Library: The Class HashSet

22.19

The package java.util of the Java Class Library also contains the class HashSet<T> . This class
implements the interface java.util.Set that we presented in Segment 1.21 of Chapter 1. Recall
that a set is a collection that does not contain duplicate entries, but otherwise is similar to a bag.
HashSet uses an instance of the class HashMap , as introduced in the previous segment, to contain the
entries in a set.