· 6 years ago · May 14, 2019, 01:24 AM
1//---------------------------------------------------------------------------
2// HMap.java by Dale/Joyce/Weems Chapter 8
3//
4// Implements a map using an array-based hash table, linear probing collision
5// resolution.
6//
7// The remove operation is not supported. Invoking it will result in the
8// unchecked UnsupportedOperationException being thrown.
9//
10// A map provides (K = key, V = value) pairs, mapping the key onto the value.
11// Keys are unique. Keys cannot be null.
12//
13// Methods throw IllegalArgumentException if passed a null key argument.
14//
15// Values can be null, so a null value returned by put or get does
16// not necessarily mean that an entry did not exist.
17//---------------------------------------------------------------------------
18package Control;
19
20import java.util.Iterator;
21
22public class HMap<K, V> implements MapInterface<K,V>
23{
24 protected MapEntry[] map;
25 protected boolean[] removedMap;
26
27 protected final int DEFCAP = 997; // default capacity
28 protected final double DEFLOAD = 0.5; // default load
29
30 protected int origCap; // original capacity
31 protected int currCap; // current capacity
32 protected double load;
33
34 protected int numPairs = 0; // number of pairs in this map
35
36 public HMap()
37 {
38 map = new MapEntry[DEFCAP];
39 origCap = DEFCAP;
40 currCap = DEFCAP;
41 load = DEFLOAD;
42 removedMap = new boolean[DEFCAP];
43 }
44
45 public HMap(int initCap, double initLoad)
46 {
47 map = new MapEntry[initCap];
48 origCap = initCap;
49 currCap = initCap;
50 load = initLoad;
51 removedMap = new boolean[initCap];
52 }
53
54 private void enlarge()
55 // Increments the capacity of the map by an amount
56 // equal to the original capacity.
57 {
58 // create a snapshot iterator of the map and save current size
59 Iterator<MapEntry<K,V>> i = iterator();
60 int count = numPairs;
61
62 // create the larger array and reset variables
63 map = new MapEntry[currCap + origCap];
64 currCap = currCap + origCap;
65 numPairs = 0;
66
67 // put the contents of the current map into the larger array
68 MapEntry entry;
69 for (int n = 1; n <= count; n++)
70 {
71 entry = i.next();
72 this.put((K)entry.getKey(), (V)entry.getValue());
73 }
74 }
75
76 public V put(K k, V v)
77 // If an entry in this map with key k already exists then the value
78 // associated with that entry is replaced by value v and the original
79 // value is returned; otherwise, adds the (k, v) pair to the map and
80 // returns null.
81 {
82 if (k == null)
83 throw new IllegalArgumentException("Maps do not allow null keys.");
84
85 MapEntry<K, V> entry = new MapEntry<K, V>(k, v);
86
87 int location = Math.abs(k.hashCode()) % currCap;
88 int numLoops = 1;
89 int ogLocation = location;
90 while ((map[location] != null) && !(map[location].getKey().equals(k)))
91 {
92 location = (ogLocation + (int)Math.pow(numLoops, 2)) % currCap;
93 }
94
95 if (map[location] == null) // k was not in map
96 {
97 map[location] = entry;
98 numPairs++;
99 if ((float)numPairs/currCap > load)
100 enlarge();
101 return null;
102 }
103 else // k already in map
104 {
105 V temp = (V)map[location].getValue();
106 map[location] = entry;
107 return temp;
108 }
109 }
110
111 public V get(K k)
112 // If an entry in this map with a key k exists then the value associated
113 // with that entry is returned; otherwise null is returned.
114 {
115 if (k == null)
116 throw new IllegalArgumentException("Maps do not allow null keys.");
117
118 int location = Math.abs(k.hashCode()) % currCap;
119 while ((map[location] != null) && !(map[location].getKey().equals(k)))
120 location = (location + 1) % currCap;
121
122 if (map[location] == null) // k was not in map
123 return null;
124 else // k in map
125 return (V)map[location].getValue();
126 }
127
128 public V remove(K k)
129//returns the value of element k if it exists, otherwise returns null
130 {
131 if (k == null)
132 {
133 throw new IllegalArgumentException("Maps do not allow null keys.");
134 }
135 else if (contains(k))
136 {
137 int location = Math.abs(k.hashCode()) % currCap;
138 while (map[location] != null)
139 {
140 if (map[location].getKey().equals(k))
141 {
142 V val = (V)map[location].getValue();
143 map[location] = null;
144 removedMap[location] = true;
145 return val;
146 }
147 else
148 {
149 location = (location + 1) % currCap;
150 }
151 }
152 }
153 return null;
154 }
155
156 public boolean contains(K k)
157 // Returns true if an entry in this map with key k exists;
158 // Returns false otherwise.
159 {
160 if (k == null)
161 throw new IllegalArgumentException("Maps do not allow null keys.");
162
163 int location = Math.abs(k.hashCode()) % currCap;
164 while (map[location] != null)
165 if (removedMap[location] != true && map[location].getKey().equals(k))
166 return true;
167 else
168 location = (location + 1) % currCap;
169
170 // if get this far then no current entry is associated with k
171 return false;
172 }
173
174 public boolean isEmpty()
175 // Returns true if this map is empty; otherwise, returns false.
176 {
177 return (numPairs == 0);
178 }
179
180 public boolean isFull()
181 // Returns true if this map is full; otherwise, returns false.
182 {
183 return false; // An HMap is never full
184 }
185
186 public int size()
187 // Returns the number of entries in this map.
188 {
189 return numPairs;
190 }
191
192 private class MapIterator implements Iterator<MapEntry<K,V>>
193 // Provides a snapshot Iterator over this map.
194 // Remove is not supported and throws UnsupportedOperationException.
195 {
196 int listSize = size();
197 private MapEntry[] list = new MapEntry[listSize];
198 private int previousPos = -1; // previous position returned from list
199
200 public MapIterator()
201 {
202 int next = -1;
203 for (int i = 0; i < listSize; i++)
204 {
205 next++;
206 while (map[next] == null)
207 next++;
208 list[i] = map[next];
209 }
210 }
211
212 public boolean hasNext()
213 // Returns true if the iteration has more entries; otherwise returns false.
214 {
215 return (previousPos < (listSize - 1)) ;
216 }
217
218 public MapEntry<K,V> next()
219 // Returns the next entry in the iteration.
220 // Throws NoSuchElementException - if the iteration has no more entries
221 {
222 if (!hasNext())
223 throw new IndexOutOfBoundsException("illegal invocation of next " +
224 " in HMap iterator.\n");
225 previousPos++;
226 return list[previousPos];
227 }
228
229 public void remove()
230 // Throws UnsupportedOperationException.
231 // Not supported. Removal from snapshot iteration is meaningless.
232 {
233 throw new UnsupportedOperationException("Unsupported remove attempted on "
234 + "HMap iterator.\n");
235 }
236 }
237
238 public Iterator<MapEntry<K,V>> iterator()
239 // Returns a snapshot Iterator over this map.
240 // Remove is not supported and throws UnsupportedOperationException.
241
242 {
243 return new MapIterator();
244 }
245
246 @Override
247 public String toString()
248 {
249 String mapString = "";
250 for (int i = 0; i<map.length; ++i)
251 {
252 mapString += String.valueOf(i) + ": " +map[i].key + ":" + map[i].value + "\n";
253 }
254 return mapString;
255 }
256}