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

the key is new in the map, the new entry is created in the map (line 156). Before inserting the
new entry, the method checks whether the size exceeds the load-factor threshold (line 141). If
so, the program invokes rehash() (line 145) to increase the capacity and store entries into
the new larger hash table.
The rehash() method first copies all entries in a set (line 231), doubles the capacity (line
232), creates a new hash table (line 233), and resets the size to 0 (line 234). The method then cop-
ies the entries into the new hash table (lines 236-238). The rehash method takes O ( capacity )
time. If no rehash is performed, the put method takes O (1) time to add a new entry.
The remove(key) method removes the entry with the specified key in the map (lines
164-177). This method takes O (1) time.
The size() method simply returns the size of the map (lines 180-182). This method takes
O (1) time.
The values() method returns all values in the map. The method examines each entry
from all buckets and adds it to a set (lines 185-197). This method takes O ( capacity ) time.
The hash() method invokes the supplementalHash to ensure that the hashing is evenly
distributed to produce an index for the hash table (lines 200-208). This method takes O (1) time.
Table 27.1 summarizes the time complexities of the methods in MyHashMap .

rehash

remove

size

values

hash

T ABLE 27.1

Time Complexities for Methods in

MyHashMap

Methods Time

clear() O ( capacity )

O (1)

containsKey(key: Key)

O ( capacity )

containsValue(value: V)

entrySet() O ( capacity )

get(key: K) O (1)

isEmpty() O (1)

O ( capacity )

keySet()

put(key: K, value: V) O (1)

remove(key: K) O (1)

size() O (1)

O ( capacity )

values()

rehash() O ( capacity )

Since rehashing does not happen very often, the time complexity for the put method is
O (1). Note that the complexities of the clear , entrySet , keySet , values , and rehash
methods depend on capacity , so to avoid poor performance for these methods you should
choose an initial capacity carefully.
Listing 27.3 gives a test program that uses MyHashMap .

L ISTING 27.3

TestMyHashMap.java
1 public class TestMyHashMap {
2 public static void main(String[] args) {
3 // Create a map
4 MyMap<String, Integer> map = new MyHashMap<>();
5 map.put( "Smith" , 30 );
6 map.put( "Anderson" , 31 );
7 map.put( "Lewis" , 29 );
8 map.put( "Cook" , 29 );

create a map
put entries