Java Reference
In-Depth Information
233 table = new LinkedList[capacity]; // Create a new hash table
234 size = 0 ; // Reset size to 0
235
236 for (Entry<K, V> entry: set) {
237 put(entry.getKey(), entry.getValue()); // Store to new table
238 }
239 }
240
241 @Override /** Return a string representation for this map */
242 public String toString() {
243 StringBuilder builder = new StringBuilder( "[" );
244
245 for ( int i = 0 ; i < capacity; i++) {
246 if (table[i] != null && table[i].size() > 0 )
247 for (Entry<K, V> entry: table[i])
248 builder.append(entry);
249 }
250
251 builder.append( "]" );
252
toString
return builder.toString();
253 }
254 }
The MyHashMap class implements the MyMap interface using separate chaining. The param-
eters that determine the hash-table size and load factors are defined in the class. The default
initial capacity is 4 (line 5) and the maximum capacity is 2 30 (line 8). The current hash-table
capacity is designed as a value of the power of 2 (line 11). The default load-factor threshold
is 0.75f (line 14). You can specify a custom load-factor threshold when constructing a map.
The custom load-factor threshold is stored in loadFactorThreshold (line 17). The data
field size denotes the number of entries in the map (line 20). The hash table is an array. Each
cell in the array is a linked list (line 23).
Three constructors are provided to construct a map. You can construct a default map with
the default capacity and load-factor threshold using the no-arg constructor (lines 26-28), a
map with the specified capacity and a default load-factor threshold (lines 32-34), and a map
with the specified capacity and load-factor threshold (lines 38-46).
The clear method removes all entries from the map (lines 49-52). It invokes
removeEntries() , which deletes all entries in the buckets (lines 221-227). The
removeEntries() method takes O ( capacity ) time to clear all entries in the table.
The containsKey(key) method checks whether the specified key is in the map
by invoking the get method (lines 55-60). Since the get method takes O (1) time, the
containsKey(key) method takes O (1) time.
The containsValue(value) method checks whether the value is in the map (lines
63-74). This method takes O ( capacity
hash-table parameters
three constructors
clear
containsKey
containsValue
+
size ) time. It is actually O ( capacity ), since
size .
The entrySet() method returns a set that contains all entries in the map (lines 77-90).
This method takes O ( capacity ) time.
The get(key) method returns the value of the first entry with the specified key (lines
93-103). This method takes O (1) time.
The isEmpty() method simply returns true if the map is empty (lines 106-108). This
method takes O (1) time.
The keySet() method returns all keys in the map as a set. The method finds the keys from
each bucket and adds them to a set (lines 111-123). This method takes O ( capacity ) time.
The put(key, value) method adds a new entry into the map. The method first tests if
the key is already in the map (line 127), if so, it locates the entry and replaces the old value
with the new value in the entry for the key (line 134) and the old value is returned (line 136). If
capacity
7
entrySet
get
isEmpty
keySet
put
 
 
Search WWH ::




Custom Search