001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: /*
019: * Note: originally released under the GNU LGPL v2.1,
020: * but rereleased by the original author under the ASF license (above).
021: */
022: package org.apache.commons.lang;
023:
024: /**
025: * <p>A hash map that uses primitive ints for the key rather than objects.</p>
026: *
027: * <p>Note that this class is for internal optimization purposes only, and may
028: * not be supported in future releases of Jakarta Commons Lang. Utilities of
029: * this sort may be included in future releases of Jakarta Commons Collections.</p>
030: *
031: * @author Justin Couch
032: * @author Alex Chaffee (alex@apache.org)
033: * @author Stephen Colebourne
034: * @since 2.0
035: * @version $Revision: 437554 $
036: * @see java.util.HashMap
037: */
038: class IntHashMap {
039:
040: /**
041: * The hash table data.
042: */
043: private transient Entry table[];
044:
045: /**
046: * The total number of entries in the hash table.
047: */
048: private transient int count;
049:
050: /**
051: * The table is rehashed when its size exceeds this threshold. (The
052: * value of this field is (int)(capacity * loadFactor).)
053: *
054: * @serial
055: */
056: private int threshold;
057:
058: /**
059: * The load factor for the hashtable.
060: *
061: * @serial
062: */
063: private float loadFactor;
064:
065: /**
066: * <p>Innerclass that acts as a datastructure to create a new entry in the
067: * table.</p>
068: */
069: private static class Entry {
070: int hash;
071: int key;
072: Object value;
073: Entry next;
074:
075: /**
076: * <p>Create a new entry with the given values.</p>
077: *
078: * @param hash The code used to hash the object with
079: * @param key The key used to enter this in the table
080: * @param value The value for this key
081: * @param next A reference to the next entry in the table
082: */
083: protected Entry(int hash, int key, Object value, Entry next) {
084: this .hash = hash;
085: this .key = key;
086: this .value = value;
087: this .next = next;
088: }
089: }
090:
091: /**
092: * <p>Constructs a new, empty hashtable with a default capacity and load
093: * factor, which is <code>20</code> and <code>0.75</code> respectively.</p>
094: */
095: public IntHashMap() {
096: this (20, 0.75f);
097: }
098:
099: /**
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: "
124: + initialCapacity);
125: }
126: if (loadFactor <= 0) {
127: throw new IllegalArgumentException("Illegal Load: "
128: + loadFactor);
129: }
130: if (initialCapacity == 0) {
131: initialCapacity = 1;
132: }
133:
134: this .loadFactor = loadFactor;
135: table = new Entry[initialCapacity];
136: threshold = (int) (initialCapacity * loadFactor);
137: }
138:
139: /**
140: * <p>Returns the number of keys in this hashtable.</p>
141: *
142: * @return the number of keys in this hashtable.
143: */
144: public int size() {
145: return count;
146: }
147:
148: /**
149: * <p>Tests if this hashtable maps no keys to values.</p>
150: *
151: * @return <code>true</code> if this hashtable maps no keys to values;
152: * <code>false</code> otherwise.
153: */
154: public boolean isEmpty() {
155: return count == 0;
156: }
157:
158: /**
159: * <p>Tests if some key maps into the specified value in this hashtable.
160: * This operation is more expensive than the <code>containsKey</code>
161: * method.</p>
162: *
163: * <p>Note that this method is identical in functionality to containsValue,
164: * (which is part of the Map interface in the collections framework).</p>
165: *
166: * @param value a value to search for.
167: * @return <code>true</code> if and only if some key maps to the
168: * <code>value</code> argument in this hashtable as
169: * determined by the <tt>equals</tt> method;
170: * <code>false</code> otherwise.
171: * @throws NullPointerException if the value is <code>null</code>.
172: * @see #containsKey(int)
173: * @see #containsValue(Object)
174: * @see java.util.Map
175: */
176: public boolean contains(Object value) {
177: if (value == null) {
178: throw new NullPointerException();
179: }
180:
181: Entry tab[] = table;
182: for (int i = tab.length; i-- > 0;) {
183: for (Entry e = tab[i]; e != null; e = e.next) {
184: if (e.value.equals(value)) {
185: return true;
186: }
187: }
188: }
189: return false;
190: }
191:
192: /**
193: * <p>Returns <code>true</code> if this HashMap maps one or more keys
194: * to this value.</p>
195: *
196: * <p>Note that this method is identical in functionality to contains
197: * (which predates the Map interface).</p>
198: *
199: * @param value value whose presence in this HashMap is to be tested.
200: * @return boolean <code>true</code> if the value is contained
201: * @see java.util.Map
202: * @since JDK1.2
203: */
204: public boolean containsValue(Object value) {
205: return contains(value);
206: }
207:
208: /**
209: * <p>Tests if the specified object is a key in this hashtable.</p>
210: *
211: * @param key possible key.
212: * @return <code>true</code> if and only if the specified object is a
213: * key in this hashtable, as determined by the <tt>equals</tt>
214: * method; <code>false</code> otherwise.
215: * @see #contains(Object)
216: */
217: public boolean containsKey(int key) {
218: Entry tab[] = table;
219: int hash = key;
220: int index = (hash & 0x7FFFFFFF) % tab.length;
221: for (Entry e = tab[index]; e != null; e = e.next) {
222: if (e.hash == hash) {
223: return true;
224: }
225: }
226: return false;
227: }
228:
229: /**
230: * <p>Returns the value to which the specified key is mapped in this map.</p>
231: *
232: * @param key a key in the hashtable.
233: * @return the value to which the key is mapped in this hashtable;
234: * <code>null</code> if the key is not mapped to any value in
235: * this hashtable.
236: * @see #put(int, Object)
237: */
238: public Object get(int key) {
239: Entry tab[] = table;
240: int hash = key;
241: int index = (hash & 0x7FFFFFFF) % tab.length;
242: for (Entry e = tab[index]; e != null; e = e.next) {
243: if (e.hash == hash) {
244: return e.value;
245: }
246: }
247: return null;
248: }
249:
250: /**
251: * <p>Increases the capacity of and internally reorganizes this
252: * hashtable, in order to accommodate and access its entries more
253: * efficiently.</p>
254: *
255: * <p>This method is called automatically when the number of keys
256: * in the hashtable exceeds this hashtable's capacity and load
257: * factor.</p>
258: */
259: protected void rehash() {
260: int oldCapacity = table.length;
261: Entry oldMap[] = table;
262:
263: int newCapacity = oldCapacity * 2 + 1;
264: Entry newMap[] = new Entry[newCapacity];
265:
266: threshold = (int) (newCapacity * loadFactor);
267: table = newMap;
268:
269: for (int i = oldCapacity; i-- > 0;) {
270: for (Entry old = oldMap[i]; old != null;) {
271: Entry e = old;
272: old = old.next;
273:
274: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
275: e.next = newMap[index];
276: newMap[index] = e;
277: }
278: }
279: }
280:
281: /**
282: * <p>Maps the specified <code>key</code> to the specified
283: * <code>value</code> in this hashtable. The key cannot be
284: * <code>null</code>. </p>
285: *
286: * <p>The value can be retrieved by calling the <code>get</code> method
287: * with a key that is equal to the original key.</p>
288: *
289: * @param key the hashtable key.
290: * @param value the value.
291: * @return the previous value of the specified key in this hashtable,
292: * or <code>null</code> if it did not have one.
293: * @throws NullPointerException if the key is <code>null</code>.
294: * @see #get(int)
295: */
296: public Object put(int key, Object value) {
297: // Makes sure the key is not already in the hashtable.
298: Entry tab[] = table;
299: int hash = key;
300: int index = (hash & 0x7FFFFFFF) % tab.length;
301: for (Entry e = tab[index]; e != null; e = e.next) {
302: if (e.hash == hash) {
303: Object old = e.value;
304: e.value = value;
305: return old;
306: }
307: }
308:
309: if (count >= threshold) {
310: // Rehash the table if the threshold is exceeded
311: rehash();
312:
313: tab = table;
314: index = (hash & 0x7FFFFFFF) % tab.length;
315: }
316:
317: // Creates the new entry.
318: Entry e = new Entry(hash, key, value, tab[index]);
319: tab[index] = e;
320: count++;
321: return null;
322: }
323:
324: /**
325: * <p>Removes the key (and its corresponding value) from this
326: * hashtable.</p>
327: *
328: * <p>This method does nothing if the key is not present in the
329: * hashtable.</p>
330: *
331: * @param key the key that needs to be removed.
332: * @return the value to which the key had been mapped in this hashtable,
333: * or <code>null</code> if the key did not have a mapping.
334: */
335: public Object remove(int key) {
336: Entry tab[] = table;
337: int hash = key;
338: int index = (hash & 0x7FFFFFFF) % tab.length;
339: for (Entry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
340: if (e.hash == hash) {
341: if (prev != null) {
342: prev.next = e.next;
343: } else {
344: tab[index] = e.next;
345: }
346: count--;
347: Object oldValue = e.value;
348: e.value = null;
349: return oldValue;
350: }
351: }
352: return null;
353: }
354:
355: /**
356: * <p>Clears this hashtable so that it contains no keys.</p>
357: */
358: public synchronized void clear() {
359: Entry tab[] = table;
360: for (int index = tab.length; --index >= 0;) {
361: tab[index] = null;
362: }
363: count = 0;
364: }
365:
366: }
|