1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17
18 /*
19 * Note: originally released under the GNU LGPL v2.1,
20 * but rereleased by the original author under the ASF license (above).
21 */
22 package org.apache.commons.lang;
23
24 /**
25 * <p>A hash map that uses primitive ints for the key rather than objects.</p>
26 *
27 * <p>Note that this class is for internal optimization purposes only, and may
28 * not be supported in future releases of Apache Commons Lang. Utilities of
29 * this sort may be included in future releases of Apache Commons Collections.</p>
30 *
31 * @author Justin Couch
32 * @author Alex Chaffee (alex@apache.org)
33 * @author Stephen Colebourne
34 * @since 2.0
35 * @version $Revision: 561230 $
36 * @see java.util.HashMap
37 */
38 class IntHashMap {
39
40 /**
41 * The hash table data.
42 */
43 private transient Entry table[];
44
45 /**
46 * The total number of entries in the hash table.
47 */
48 private transient int count;
49
50 /**
51 * The table is rehashed when its size exceeds this threshold. (The
52 * value of this field is (int)(capacity * loadFactor).)
53 *
54 * @serial
55 */
56 private int threshold;
57
58 /**
59 * The load factor for the hashtable.
60 *
61 * @serial
62 */
63 private float loadFactor;
64
65 /**
66 * <p>Innerclass that acts as a datastructure to create a new entry in the
67 * table.</p>
68 */
69 private static class Entry {
70 int hash;
71 int key;
72 Object value;
73 Entry next;
74
75 /**
76 * <p>Create a new entry with the given values.</p>
77 *
78 * @param hash The code used to hash the object with
79 * @param key The key used to enter this in the table
80 * @param value The value for this key
81 * @param next A reference to the next entry in the table
82 */
83 protected Entry(int hash, int key, Object value, Entry next) {
84 this.hash = hash;
85 this.key = key;
86 this.value = value;
87 this.next = next;
88 }
89 }
90
91 /**
92 * <p>Constructs a new, empty hashtable with a default capacity and load
93 * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
94 */
95 public IntHashMap() {
96 this(20, 0.75f);
97 }
98
99 /**
100 * <p>Constructs a new, empty hashtable with the specified initial capacity
101 * and default load factor, which is <code>0.75</code>.</p>
102 *
103 * @param initialCapacity the initial capacity of the hashtable.
104 * @throws IllegalArgumentException if the initial capacity is less
105 * than zero.
106 */
107 public IntHashMap(int initialCapacity) {
108 this(initialCapacity, 0.75f);
109 }
110
111 /**
112 * <p>Constructs a new, empty hashtable with the specified initial
113 * capacity and the specified load factor.</p>
114 *
115 * @param initialCapacity the initial capacity of the hashtable.
116 * @param loadFactor the load factor of the hashtable.
117 * @throws IllegalArgumentException if the initial capacity is less
118 * than zero, or if the load factor is nonpositive.
119 */
120 public IntHashMap(int initialCapacity, float loadFactor) {
121 super();
122 if (initialCapacity < 0) {
123 throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
124 }
125 if (loadFactor <= 0) {
126 throw new IllegalArgumentException("Illegal Load: " + loadFactor);
127 }
128 if (initialCapacity == 0) {
129 initialCapacity = 1;
130 }
131
132 this.loadFactor = loadFactor;
133 table = new Entry[initialCapacity];
134 threshold = (int) (initialCapacity * loadFactor);
135 }
136
137 /**
138 * <p>Returns the number of keys in this hashtable.</p>
139 *
140 * @return the number of keys in this hashtable.
141 */
142 public int size() {
143 return count;
144 }
145
146 /**
147 * <p>Tests if this hashtable maps no keys to values.</p>
148 *
149 * @return <code>true</code> if this hashtable maps no keys to values;
150 * <code>false</code> otherwise.
151 */
152 public boolean isEmpty() {
153 return count == 0;
154 }
155
156 /**
157 * <p>Tests if some key maps into the specified value in this hashtable.
158 * This operation is more expensive than the <code>containsKey</code>
159 * method.</p>
160 *
161 * <p>Note that this method is identical in functionality to containsValue,
162 * (which is part of the Map interface in the collections framework).</p>
163 *
164 * @param value a value to search for.
165 * @return <code>true</code> if and only if some key maps to the
166 * <code>value</code> argument in this hashtable as
167 * determined by the <tt>equals</tt> method;
168 * <code>false</code> otherwise.
169 * @throws NullPointerException if the value is <code>null</code>.
170 * @see #containsKey(int)
171 * @see #containsValue(Object)
172 * @see java.util.Map
173 */
174 public boolean contains(Object value) {
175 if (value == null) {
176 throw new NullPointerException();
177 }
178
179 Entry tab[] = table;
180 for (int i = tab.length; i-- > 0;) {
181 for (Entry e = tab[i]; e != null; e = e.next) {
182 if (e.value.equals(value)) {
183 return true;
184 }
185 }
186 }
187 return false;
188 }
189
190 /**
191 * <p>Returns <code>true</code> if this HashMap maps one or more keys
192 * to this value.</p>
193 *
194 * <p>Note that this method is identical in functionality to contains
195 * (which predates the Map interface).</p>
196 *
197 * @param value value whose presence in this HashMap is to be tested.
198 * @return boolean <code>true</code> if the value is contained
199 * @see java.util.Map
200 * @since JDK1.2
201 */
202 public boolean containsValue(Object value) {
203 return contains(value);
204 }
205
206 /**
207 * <p>Tests if the specified object is a key in this hashtable.</p>
208 *
209 * @param key possible key.
210 * @return <code>true</code> if and only if the specified object is a
211 * key in this hashtable, as determined by the <tt>equals</tt>
212 * method; <code>false</code> otherwise.
213 * @see #contains(Object)
214 */
215 public boolean containsKey(int key) {
216 Entry tab[] = table;
217 int hash = key;
218 int index = (hash & 0x7FFFFFFF) % tab.length;
219 for (Entry e = tab[index]; e != null; e = e.next) {
220 if (e.hash == hash) {
221 return true;
222 }
223 }
224 return false;
225 }
226
227 /**
228 * <p>Returns the value to which the specified key is mapped in this map.</p>
229 *
230 * @param key a key in the hashtable.
231 * @return the value to which the key is mapped in this hashtable;
232 * <code>null</code> if the key is not mapped to any value in
233 * this hashtable.
234 * @see #put(int, Object)
235 */
236 public Object get(int key) {
237 Entry tab[] = table;
238 int hash = key;
239 int index = (hash & 0x7FFFFFFF) % tab.length;
240 for (Entry e = tab[index]; e != null; e = e.next) {
241 if (e.hash == hash) {
242 return e.value;
243 }
244 }
245 return null;
246 }
247
248 /**
249 * <p>Increases the capacity of and internally reorganizes this
250 * hashtable, in order to accommodate and access its entries more
251 * efficiently.</p>
252 *
253 * <p>This method is called automatically when the number of keys
254 * in the hashtable exceeds this hashtable's capacity and load
255 * factor.</p>
256 */
257 protected void rehash() {
258 int oldCapacity = table.length;
259 Entry oldMap[] = table;
260
261 int newCapacity = oldCapacity * 2 + 1;
262 Entry newMap[] = new Entry[newCapacity];
263
264 threshold = (int) (newCapacity * loadFactor);
265 table = newMap;
266
267 for (int i = oldCapacity; i-- > 0;) {
268 for (Entry old = oldMap[i]; old != null;) {
269 Entry e = old;
270 old = old.next;
271
272 int index = (e.hash & 0x7FFFFFFF) % newCapacity;
273 e.next = newMap[index];
274 newMap[index] = e;
275 }
276 }
277 }
278
279 /**
280 * <p>Maps the specified <code>key</code> to the specified
281 * <code>value</code> in this hashtable. The key cannot be
282 * <code>null</code>. </p>
283 *
284 * <p>The value can be retrieved by calling the <code>get</code> method
285 * with a key that is equal to the original key.</p>
286 *
287 * @param key the hashtable key.
288 * @param value the value.
289 * @return the previous value of the specified key in this hashtable,
290 * or <code>null</code> if it did not have one.
291 * @throws NullPointerException if the key is <code>null</code>.
292 * @see #get(int)
293 */
294 public Object put(int key, Object value) {
295 // Makes sure the key is not already in the hashtable.
296 Entry tab[] = table;
297 int hash = key;
298 int index = (hash & 0x7FFFFFFF) % tab.length;
299 for (Entry e = tab[index]; e != null; e = e.next) {
300 if (e.hash == hash) {
301 Object old = e.value;
302 e.value = value;
303 return old;
304 }
305 }
306
307 if (count >= threshold) {
308 // Rehash the table if the threshold is exceeded
309 rehash();
310
311 tab = table;
312 index = (hash & 0x7FFFFFFF) % tab.length;
313 }
314
315 // Creates the new entry.
316 Entry e = new Entry(hash, key, value, tab[index]);
317 tab[index] = e;
318 count++;
319 return null;
320 }
321
322 /**
323 * <p>Removes the key (and its corresponding value) from this
324 * hashtable.</p>
325 *
326 * <p>This method does nothing if the key is not present in the
327 * hashtable.</p>
328 *
329 * @param key the key that needs to be removed.
330 * @return the value to which the key had been mapped in this hashtable,
331 * or <code>null</code> if the key did not have a mapping.
332 */
333 public Object remove(int key) {
334 Entry tab[] = table;
335 int hash = key;
336 int index = (hash & 0x7FFFFFFF) % tab.length;
337 for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
338 if (e.hash == hash) {
339 if (prev != null) {
340 prev.next = e.next;
341 } else {
342 tab[index] = e.next;
343 }
344 count--;
345 Object oldValue = e.value;
346 e.value = null;
347 return oldValue;
348 }
349 }
350 return null;
351 }
352
353 /**
354 * <p>Clears this hashtable so that it contains no keys.</p>
355 */
356 public synchronized void clear() {
357 Entry tab[] = table;
358 for (int index = tab.length; --index >= 0;) {
359 tab[index] = null;
360 }
361 count = 0;
362 }
363
364 }