001: /*
002: *
003: *
004: * Copyright 1990-2007 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
006: *
007: * This program is free software; you can redistribute it and/or
008: * modify it under the terms of the GNU General Public License version
009: * 2 only, as published by the Free Software Foundation.
010: *
011: * This program is distributed in the hope that it will be useful, but
012: * WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014: * General Public License version 2 for more details (a copy is
015: * included at /legal/license.txt).
016: *
017: * You should have received a copy of the GNU General Public License
018: * version 2 along with this work; if not, write to the Free Software
019: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
020: * 02110-1301 USA
021: *
022: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
023: * Clara, CA 95054 or visit www.sun.com if you need additional
024: * information or have any questions.
025: */
026:
027: package java.util;
028:
029: import java.io.*;
030:
031: /**
032: * This class implements a hashtable, which maps keys to values. Any
033: * non-<code>null</code> object can be used as a key or as a value.
034: * <p>
035: * To successfully store and retrieve objects from a hashtable, the
036: * objects used as keys must implement the <code>hashCode</code>
037: * method and the <code>equals</code> method.
038: * <p>
039: * An instance of <code>Hashtable</code> has two parameters that
040: * affect its efficiency: its <i>capacity</i> and its <i>load
041: * factor</i>. The load factor in the CLDC implementation of
042: * the hashtable class is always 75 percent. When the number
043: * of entries in the hashtable exceeds the product of the
044: * load factor and the current capacity, the capacity is increased
045: * by calling the <code>rehash</code> method.
046: * <p>
047: * If many entries are to be made into a <code>Hashtable</code>,
048: * creating it with a sufficiently large capacity may allow the
049: * entries to be inserted more efficiently than letting it perform
050: * automatic rehashing as needed to grow the table.
051: * <p>
052: * This example creates a hashtable of numbers. It uses the names of
053: * the numbers as keys:
054: * <p><blockquote><pre>
055: * Hashtable numbers = new Hashtable();
056: * numbers.put("one", new Integer(1));
057: * numbers.put("two", new Integer(2));
058: * numbers.put("three", new Integer(3));
059: * </pre></blockquote>
060: * <p>
061: * To retrieve a number, use the following code:
062: * <p><blockquote><pre>
063: * Integer n = (Integer)numbers.get("two");
064: * if (n != null) {
065: * System.out.println("two = " + n);
066: * }
067: * </pre></blockquote>
068: *
069: * @version 12/17/01 (CLDC 1.1)
070: * @see java.lang.Object#equals(java.lang.Object)
071: * @see java.lang.Object#hashCode()
072: * @see java.util.Hashtable#rehash()
073: * @since JDK1.0, CLDC 1.0
074: */
075: public class Hashtable {
076:
077: /**
078: * The hash table data.
079: */
080: private transient HashtableEntry table[];
081:
082: /**
083: * The total number of entries in the hash table.
084: */
085: private transient int count;
086:
087: /**
088: * Rehashes the table when count exceeds this threshold.
089: */
090: private int threshold;
091:
092: /**
093: * The load factor for the hashtable. In CLDC,
094: * the default load factor is 75%.
095: */
096: private static final int loadFactorPercent = 75;
097:
098: /**
099: * Constructs a new, empty hashtable with the specified initial
100: * capacity.
101: *
102: * @param initialCapacity the initial capacity of the hashtable.
103: * @exception IllegalArgumentException if the initial capacity is less
104: * than zero
105: * @since JDK1.0
106: */
107: public Hashtable(int initialCapacity) {
108: if (initialCapacity < 0) {
109: throw new IllegalArgumentException();
110: }
111: if (initialCapacity == 0) {
112: initialCapacity = 1;
113: }
114: table = new HashtableEntry[initialCapacity];
115: threshold = (int) ((initialCapacity * loadFactorPercent) / 100);
116: }
117:
118: /**
119: * Constructs a new, empty hashtable with a default capacity and load
120: * factor.
121: *
122: * @since JDK1.0
123: */
124: public Hashtable() {
125: this (11);
126: }
127:
128: /**
129: * Returns the number of keys in this hashtable.
130: *
131: * @return the number of keys in this hashtable.
132: * @since JDK1.0
133: */
134: public int size() {
135: return count;
136: }
137:
138: /**
139: * Tests if this hashtable maps no keys to values.
140: *
141: * @return <code>true</code> if this hashtable maps no keys to values;
142: * <code>false</code> otherwise.
143: * @since JDK1.0
144: */
145: public boolean isEmpty() {
146: return count == 0;
147: }
148:
149: /**
150: * Returns an enumeration of the keys in this hashtable.
151: *
152: * @return an enumeration of the keys in this hashtable.
153: * @see java.util.Enumeration
154: * @see java.util.Hashtable#elements()
155: * @since JDK1.0
156: */
157: public synchronized Enumeration keys() {
158: return new HashtableEnumerator(table, true);
159: }
160:
161: /**
162: * Returns an enumeration of the values in this hashtable.
163: * Use the Enumeration methods on the returned object to fetch the elements
164: * sequentially.
165: *
166: * @return an enumeration of the values in this hashtable.
167: * @see java.util.Enumeration
168: * @see java.util.Hashtable#keys()
169: * @since JDK1.0
170: */
171: public synchronized Enumeration elements() {
172: return new HashtableEnumerator(table, false);
173: }
174:
175: /**
176: * Tests if some key maps into the specified value in this hashtable.
177: * This operation is more expensive than the <code>containsKey</code>
178: * method.
179: *
180: * @param value a value to search for.
181: * @return <code>true</code> if some key maps to the
182: * <code>value</code> argument in this hashtable;
183: * <code>false</code> otherwise.
184: * @exception NullPointerException if the value is <code>null</code>.
185: * @see java.util.Hashtable#containsKey(java.lang.Object)
186: * @since JDK1.0
187: */
188: public synchronized boolean contains(Object value) {
189: if (value == null) {
190: throw new NullPointerException();
191: }
192:
193: HashtableEntry tab[] = table;
194: for (int i = tab.length; i-- > 0;) {
195: for (HashtableEntry e = tab[i]; e != null; e = e.next) {
196: if (e.value.equals(value)) {
197: return true;
198: }
199: }
200: }
201: return false;
202: }
203:
204: /**
205: * Tests if the specified object is a key in this hashtable.
206: *
207: * @param key possible key.
208: * @return <code>true</code> if the specified object is a key in this
209: * hashtable; <code>false</code> otherwise.
210: * @see java.util.Hashtable#contains(java.lang.Object)
211: * @since JDK1.0
212: */
213: public synchronized boolean containsKey(Object key) {
214: HashtableEntry tab[] = table;
215: int hash = key.hashCode();
216: int index = (hash & 0x7FFFFFFF) % tab.length;
217: for (HashtableEntry e = tab[index]; e != null; e = e.next) {
218: if ((e.hash == hash) && e.key.equals(key)) {
219: return true;
220: }
221: }
222: return false;
223: }
224:
225: /**
226: * Returns the value to which the specified key is mapped in this hashtable.
227: *
228: * @param key a key in the hashtable.
229: * @return the value to which the key is mapped in this hashtable;
230: * <code>null</code> if the key is not mapped to any value in
231: * this hashtable.
232: * @see java.util.Hashtable#put(java.lang.Object, java.lang.Object)
233: * @since JDK1.0
234: */
235: public synchronized Object get(Object key) {
236: HashtableEntry tab[] = table;
237: int hash = key.hashCode();
238: int index = (hash & 0x7FFFFFFF) % tab.length;
239: for (HashtableEntry e = tab[index]; e != null; e = e.next) {
240: if ((e.hash == hash) && e.key.equals(key)) {
241: return e.value;
242: }
243: }
244: return null;
245: }
246:
247: /**
248: * Rehashes the contents of the hashtable into a hashtable with a
249: * larger capacity. This method is called automatically when the
250: * number of keys in the hashtable exceeds this hashtable's capacity
251: * and load factor.
252: *
253: * @since JDK1.0
254: */
255: protected void rehash() {
256: int oldCapacity = table.length;
257: HashtableEntry oldTable[] = table;
258:
259: int newCapacity = oldCapacity * 2 + 1;
260: HashtableEntry newTable[] = new HashtableEntry[newCapacity];
261:
262: threshold = (int) ((newCapacity * loadFactorPercent) / 100);
263: table = newTable;
264:
265: for (int i = oldCapacity; i-- > 0;) {
266: for (HashtableEntry old = oldTable[i]; old != null;) {
267: HashtableEntry e = old;
268: old = old.next;
269:
270: int index = (e.hash & 0x7FFFFFFF) % newCapacity;
271: e.next = newTable[index];
272: newTable[index] = e;
273: }
274: }
275: }
276:
277: /**
278: * Maps the specified <code>key</code> to the specified
279: * <code>value</code> in this hashtable. Neither the key nor the
280: * value can be <code>null</code>.
281: * <p>
282: * The value can be retrieved by calling the <code>get</code> method
283: * with a key that is equal to the original key.
284: *
285: * @param key the hashtable key.
286: * @param value the value.
287: * @return the previous value of the specified key in this hashtable,
288: * or <code>null</code> if it did not have one.
289: * @exception NullPointerException if the key or value is
290: * <code>null</code>.
291: * @see java.lang.Object#equals(java.lang.Object)
292: * @see java.util.Hashtable#get(java.lang.Object)
293: * @since JDK1.0
294: */
295: public synchronized Object put(Object key, Object value) {
296: // Make sure the value is not null
297: if (value == null) {
298: throw new NullPointerException();
299: }
300:
301: // Makes sure the key is not already in the hashtable.
302: HashtableEntry tab[] = table;
303: int hash = key.hashCode();
304: int index = (hash & 0x7FFFFFFF) % tab.length;
305: for (HashtableEntry e = tab[index]; e != null; e = e.next) {
306: if ((e.hash == hash) && e.key.equals(key)) {
307: Object old = e.value;
308: e.value = value;
309: return old;
310: }
311: }
312:
313: if (count >= threshold) {
314: // Rehash the table if the threshold is exceeded
315: rehash();
316: return put(key, value);
317: }
318:
319: // Creates the new entry.
320: HashtableEntry e = new HashtableEntry();
321: e.hash = hash;
322: e.key = key;
323: e.value = value;
324: e.next = tab[index];
325: tab[index] = e;
326: count++;
327: return null;
328: }
329:
330: /**
331: * Removes the key (and its corresponding value) from this
332: * hashtable. This method does nothing if the key is not in the hashtable.
333: *
334: * @param key the key that needs to be removed.
335: * @return the value to which the key had been mapped in this hashtable,
336: * or <code>null</code> if the key did not have a mapping.
337: * @since JDK1.0
338: */
339: public synchronized Object remove(Object key) {
340: HashtableEntry tab[] = table;
341: int hash = key.hashCode();
342: int index = (hash & 0x7FFFFFFF) % tab.length;
343: //this loop was reviewed - code is approved!
344: for (HashtableEntry e = tab[index], prev = null; e != null; prev = e, e = e.next) {
345: if ((e.hash == hash) && e.key.equals(key)) {
346: if (prev != null) {
347: prev.next = e.next;
348: } else {
349: tab[index] = e.next;
350: }
351: count--;
352: return e.value;
353: }
354: }
355: return null;
356: }
357:
358: /**
359: * Clears this hashtable so that it contains no keys.
360: *
361: * @since JDK1.0
362: */
363: public synchronized void clear() {
364: HashtableEntry tab[] = table;
365: for (int index = tab.length; --index >= 0;)
366: tab[index] = null;
367: count = 0;
368: }
369:
370: /**
371: * Returns a rather long string representation of this hashtable.
372: *
373: * @return a string representation of this hashtable.
374: * @since JDK1.0
375: */
376: public synchronized String toString() {
377: int max = size() - 1;
378: StringBuffer buf = new StringBuffer();
379: Enumeration k = keys();
380: Enumeration e = elements();
381: buf.append("{");
382:
383: for (int i = 0; i <= max; i++) {
384: String s1 = k.nextElement().toString();
385: String s2 = e.nextElement().toString();
386: buf.append(s1 + "=" + s2);
387: if (i < max) {
388: buf.append(", ");
389: }
390: }
391: buf.append("}");
392: return buf.toString();
393: }
394:
395: /**
396: * A hashtable enumerator class. This class should remain opaque
397: * to the client. It will use the Enumeration interface.
398: */
399: class HashtableEnumerator implements Enumeration {
400: boolean keys;
401: int index;
402: HashtableEntry table[];
403: HashtableEntry entry;
404:
405: HashtableEnumerator(HashtableEntry table[], boolean keys) {
406: this .table = table;
407: this .keys = keys;
408: this .index = table.length;
409: }
410:
411: public boolean hasMoreElements() {
412: if (entry != null) {
413: return true;
414: }
415: while (index-- > 0) {
416: if ((entry = table[index]) != null) {
417: return true;
418: }
419: }
420: return false;
421: }
422:
423: public Object nextElement() {
424: if (entry == null) {
425: while ((index-- > 0)
426: && ((entry = table[index]) == null))
427: ;
428: }
429: if (entry != null) {
430: HashtableEntry e = entry;
431: entry = e.next;
432: return keys ? e.key : e.value;
433: }
434: throw new NoSuchElementException(
435: /* #ifdef VERBOSE_EXCEPTIONS */
436: /// skipped "HashtableEnumerator"
437: /* #endif */
438: );
439: }
440: }
441: }
442:
443: /**
444: * Hashtable collision list.
445: */
446: class HashtableEntry {
447: int hash;
448: Object key;
449: Object value;
450: HashtableEntry next;
451: }
|