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