Java Reference
In-Depth Information
27.19
Assume the hash table has the initial size 4 and its load factor is 0.5; show the hash
table after inserting entries with the keys 34, 29, 53, 44, 120, 39, 45, and 40, using
separate chaining.
27.7 Implementing a Map Using Hashing
A map can be implemented using hashing.
Key
Point
Now you understand the concept of hashing. You know how to design a good hash function
to map a key to an index in a hash table, how to measure performance using the load factor,
and how to increase the table size and rehash to maintain the performance. This section dem-
onstrates how to implement a map using separate chaining.
We design our custom Map interface to mirror java.util.Map and name the interface
MyMap and a concrete class MyHashMap , as shown in Figure 27.9.
«interface»
MyMap<K, V>
+clear(): void
+containsKey(key: K): boolean
Removes all entries from this map.
Returns true if this map contains an entry for the
specified key.
Returns true if this map maps one or more keys to the
specified value.
+containsValue(value: V): boolean
+entrySet(): Set<Entry<K, V>>
+get(key: K): V
+isEmpty(): boolean
+keySet(): Set<K>
+put(key: K, value: V): V
+remove(key: K): void
+size(): int
+values(): Set<V>
Returns a set consisting of the entries in this map.
Returns a value for the specified key in this map.
Returns true if this map contains no mappings.
Returns a set consisting of the keys in this map.
Puts a mapping in this map.
Removes the entries for the specified key.
Returns the number of mappings in this map.
Returns a set consisting of the values in this map.
MyHashMap<K, V>
+MyHashMap()
Creates an empty map with default capacity
4
and
default load factor threshold
0.75f
.
+MyHashMap(capacity: int)
Creates a map with a specified capacity and
default load factor threshold
0.75f
.
+MyHashMap(capacity: int,
loadFactorThreshold: float)
Creates a map with a specified capacity and
load factor threshold.
MyMap.Entry<K, V>
-key: K
-value: V
+Entry(key: K, value: V)
+getkey(): K
+getValue(): V
Constructs an entry with the specified key and value.
Returns the key in the entry.
Returns the value in the entry.
F IGURE 27.9
MyHashMap implements the MyMap interface.
 
 
 
Search WWH ::




Custom Search