Java Reference
In-Depth Information
How do you implement
MyHashMap
? If you use an
ArrayList
and store a new entry at
the end of the list, the search time will be
O
(
n
). If you implement
MyHashMa
p using a binary
tree, the search time will be
O
(log
n
) if the tree is well balanced. Nevertheless, you can imple-
ment
MyHashMa
p using hashing to obtain an
O
(1) time search algorithm. Listing 27.1 shows
the
MyMap
interface and Listing 27.2 implements
MyHashMap
using separate chaining.
L
ISTING
27.1
MyMap.java
1
public interface
MyMap<K, V> {
2
interface
MyMap
/** Remove all of the entries from this map */
3
public void
clear();
clear
4
5
/** Return true if the specified key is in the map */
6
public boolean
containsKey(K key);
containsKey
7
8
/** Return true if this map contains the specified value */
9
public boolean
containsValue(V value);
containsValue
10
11
/** Return a set of entries in the map */
12
public
java.util.Set<Entry<K, V>> entrySet();
entrySet
13
14
/** Return the value that matches the specified key */
15
public
V get(K key);
get
16
17
/** Return true if this map doesn't contain any entries */
18
public boolean
isEmpty();
isEmpty
19
20
/** Return a set consisting of the keys in this map */
21
public
java.util.Set<K> keySet();
keySet
22
23
/** Add an entry (key, value) into the map */
24
public
V put(K key, V value);
put
25
26
/** Remove an entry for the specified key */
27
public void
remove(K key);
remove
28
29
/** Return the number of mappings in this map */
30
public int
size();
size
31
32
/** Return a set consisting of the values in this map */
33
public
java.util.Set<V> values();
values
34
35
/** Define an inner class for Entry */
36
public static class
Entry<K, V> {
37 K key;
38 V value;
39
40
Entry
inner class
public
Entry(K key, V value) {
41
this
.key = key;
42
this
.value = value;
43 }
44
45
public
K getKey() {
46
return
key;
47 }
48
49
public
V getValue() {
50
return
value;
51 }
52
Search WWH ::
Custom Search