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