KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > java > util > Hashtable


1 /*
2  * @(#)Hashtable.java 1.105 03/12/19
3  *
4  * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */

7
8 package java.util;
9 import java.io.*;
10
11 /**
12  * This class implements a hashtable, which maps keys to values. Any
13  * non-<code>null</code> object can be used as a key or as a value. <p>
14  *
15  * To successfully store and retrieve objects from a hashtable, the
16  * objects used as keys must implement the <code>hashCode</code>
17  * method and the <code>equals</code> method. <p>
18  *
19  * An instance of <code>Hashtable</code> has two parameters that affect its
20  * performance: <i>initial capacity</i> and <i>load factor</i>. The
21  * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
22  * <i>initial capacity</i> is simply the capacity at the time the hash table
23  * is created. Note that the hash table is <i>open</i>: in the case of a "hash
24  * collision", a single bucket stores multiple entries, which must be searched
25  * sequentially. The <i>load factor</i> is a measure of how full the hash
26  * table is allowed to get before its capacity is automatically increased.
27  * The initial capacity and load factor parameters are merely hints to
28  * the implementation. The exact details as to when and whether the rehash
29  * method is invoked are implementation-dependent.<p>
30  *
31  * Generally, the default load factor (.75) offers a good tradeoff between
32  * time and space costs. Higher values decrease the space overhead but
33  * increase the time cost to look up an entry (which is reflected in most
34  * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
35  *
36  * The initial capacity controls a tradeoff between wasted space and the
37  * need for <code>rehash</code> operations, which are time-consuming.
38  * No <code>rehash</code> operations will <i>ever</i> occur if the initial
39  * capacity is greater than the maximum number of entries the
40  * <tt>Hashtable</tt> will contain divided by its load factor. However,
41  * setting the initial capacity too high can waste space.<p>
42  *
43  * If many entries are to be made into a <code>Hashtable</code>,
44  * creating it with a sufficiently large capacity may allow the
45  * entries to be inserted more efficiently than letting it perform
46  * automatic rehashing as needed to grow the table. <p>
47  *
48  * This example creates a hashtable of numbers. It uses the names of
49  * the numbers as keys:
50  * <p><blockquote><pre>
51  * Hashtable numbers = new Hashtable();
52  * numbers.put("one", new Integer(1));
53  * numbers.put("two", new Integer(2));
54  * numbers.put("three", new Integer(3));
55  * </pre></blockquote>
56  * <p>
57  * To retrieve a number, use the following code:
58  * <p><blockquote><pre>
59  * Integer n = (Integer)numbers.get("two");
60  * if (n != null) {
61  * System.out.println("two = " + n);
62  * }
63  * </pre></blockquote>
64  * <p>
65  * As of the Java 2 platform v1.2, this class has been retrofitted to
66  * implement Map, so that it becomes a part of Java's collection framework.
67  * Unlike the new collection implementations, Hashtable is synchronized.<p>
68  *
69  * The Iterators returned by the iterator and listIterator methods
70  * of the Collections returned by all of Hashtable's "collection view methods"
71  * are <em>fail-fast</em>: if the Hashtable is structurally modified
72  * at any time after the Iterator is created, in any way except through the
73  * Iterator's own remove or add methods, the Iterator will throw a
74  * ConcurrentModificationException. Thus, in the face of concurrent
75  * modification, the Iterator fails quickly and cleanly, rather than risking
76  * arbitrary, non-deterministic behavior at an undetermined time in the future.
77  * The Enumerations returned by Hashtable's keys and values methods are
78  * <em>not</em> fail-fast.
79  *
80  * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
81  * as it is, generally speaking, impossible to make any hard guarantees in the
82  * presence of unsynchronized concurrent modification. Fail-fast iterators
83  * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
84  * Therefore, it would be wrong to write a program that depended on this
85  * exception for its correctness: <i>the fail-fast behavior of iterators
86  * should be used only to detect bugs.</i><p>
87  *
88  * This class is a member of the
89  * <a HREF="{@docRoot}/../guide/collections/index.html">
90  * Java Collections Framework</a>.
91  *
92  * @author Arthur van Hoff
93  * @author Josh Bloch
94  * @author Neal Gafter
95  * @version 1.105, 12/19/03
96  * @see Object#equals(java.lang.Object)
97  * @see Object#hashCode()
98  * @see Hashtable#rehash()
99  * @see Collection
100  * @see Map
101  * @see HashMap
102  * @see TreeMap
103  * @since JDK1.0
104  */

105 public class Hashtable<K,V>
106     extends Dictionary JavaDoc<K,V>
107     implements Map JavaDoc<K,V>, Cloneable JavaDoc, java.io.Serializable JavaDoc {
108
109     /**
110      * The hash table data.
111      */

112     private transient Entry[] table;
113
114     /**
115      * The total number of entries in the hash table.
116      */

117     private transient int count;
118
119     /**
120      * The table is rehashed when its size exceeds this threshold. (The
121      * value of this field is (int)(capacity * loadFactor).)
122      *
123      * @serial
124      */

125     private int threshold;
126
127     /**
128      * The load factor for the hashtable.
129      *
130      * @serial
131      */

132     private float loadFactor;
133
134     /**
135      * The number of times this Hashtable has been structurally modified
136      * Structural modifications are those that change the number of entries in
137      * the Hashtable or otherwise modify its internal structure (e.g.,
138      * rehash). This field is used to make iterators on Collection-views of
139      * the Hashtable fail-fast. (See ConcurrentModificationException).
140      */

141     private transient int modCount = 0;
142
143     /** use serialVersionUID from JDK 1.0.2 for interoperability */
144     private static final long serialVersionUID = 1421746759512286392L;
145
146     /**
147      * Constructs a new, empty hashtable with the specified initial
148      * capacity and the specified load factor.
149      *
150      * @param initialCapacity the initial capacity of the hashtable.
151      * @param loadFactor the load factor of the hashtable.
152      * @exception IllegalArgumentException if the initial capacity is less
153      * than zero, or if the load factor is nonpositive.
154      */

155     public Hashtable(int initialCapacity, float loadFactor) {
156     if (initialCapacity < 0)
157         throw new IllegalArgumentException JavaDoc("Illegal Capacity: "+
158                                                initialCapacity);
159         if (loadFactor <= 0 || Float.isNaN(loadFactor))
160             throw new IllegalArgumentException JavaDoc("Illegal Load: "+loadFactor);
161
162         if (initialCapacity==0)
163             initialCapacity = 1;
164     this.loadFactor = loadFactor;
165     table = new Entry[initialCapacity];
166     threshold = (int)(initialCapacity * loadFactor);
167     }
168
169     /**
170      * Constructs a new, empty hashtable with the specified initial capacity
171      * and default load factor, which is <tt>0.75</tt>.
172      *
173      * @param initialCapacity the initial capacity of the hashtable.
174      * @exception IllegalArgumentException if the initial capacity is less
175      * than zero.
176      */

177     public Hashtable(int initialCapacity) {
178     this(initialCapacity, 0.75f);
179     }
180
181     /**
182      * Constructs a new, empty hashtable with a default initial capacity (11)
183      * and load factor, which is <tt>0.75</tt>.
184      */

185     public Hashtable() {
186     this(11, 0.75f);
187     }
188
189     /**
190      * Constructs a new hashtable with the same mappings as the given
191      * Map. The hashtable is created with an initial capacity sufficient to
192      * hold the mappings in the given Map and a default load factor, which is
193      * <tt>0.75</tt>.
194      *
195      * @param t the map whose mappings are to be placed in this map.
196      * @throws NullPointerException if the specified map is null.
197      * @since 1.2
198      */

199     public Hashtable(Map JavaDoc<? extends K, ? extends V> t) {
200     this(Math.max(2*t.size(), 11), 0.75f);
201     putAll(t);
202     }
203
204     /**
205      * Returns the number of keys in this hashtable.
206      *
207      * @return the number of keys in this hashtable.
208      */

209     public synchronized int size() {
210     return count;
211     }
212
213     /**
214      * Tests if this hashtable maps no keys to values.
215      *
216      * @return <code>true</code> if this hashtable maps no keys to values;
217      * <code>false</code> otherwise.
218      */

219     public synchronized boolean isEmpty() {
220     return count == 0;
221     }
222
223     /**
224      * Returns an enumeration of the keys in this hashtable.
225      *
226      * @return an enumeration of the keys in this hashtable.
227      * @see Enumeration
228      * @see #elements()
229      * @see #keySet()
230      * @see Map
231      */

232     public synchronized Enumeration JavaDoc<K> keys() {
233     return this.<K>getEnumeration(KEYS);
234     }
235
236     /**
237      * Returns an enumeration of the values in this hashtable.
238      * Use the Enumeration methods on the returned object to fetch the elements
239      * sequentially.
240      *
241      * @return an enumeration of the values in this hashtable.
242      * @see java.util.Enumeration
243      * @see #keys()
244      * @see #values()
245      * @see Map
246      */

247     public synchronized Enumeration JavaDoc<V> elements() {
248     return this.<V>getEnumeration(VALUES);
249     }
250
251     /**
252      * Tests if some key maps into the specified value in this hashtable.
253      * This operation is more expensive than the <code>containsKey</code>
254      * method.<p>
255      *
256      * Note that this method is identical in functionality to containsValue,
257      * (which is part of the Map interface in the collections framework).
258      *
259      * @param value a value to search for.
260      * @return <code>true</code> if and only if some key maps to the
261      * <code>value</code> argument in this hashtable as
262      * determined by the <tt>equals</tt> method;
263      * <code>false</code> otherwise.
264      * @exception NullPointerException if the value is <code>null</code>.
265      * @see #containsKey(Object)
266      * @see #containsValue(Object)
267      * @see Map
268      */

269     public synchronized boolean contains(Object JavaDoc value) {
270     if (value == null) {
271         throw new NullPointerException JavaDoc();
272     }
273
274     Entry tab[] = table;
275     for (int i = tab.length ; i-- > 0 ;) {
276         for (Entry<K,V> e = tab[i] ; e != null ; e = e.next) {
277         if (e.value.equals(value)) {
278             return true;
279         }
280         }
281     }
282     return false;
283     }
284
285     /**
286      * Returns true if this Hashtable maps one or more keys to this value.<p>
287      *
288      * Note that this method is identical in functionality to contains
289      * (which predates the Map interface).
290      *
291      * @param value value whose presence in this Hashtable is to be tested.
292      * @return <tt>true</tt> if this map maps one or more keys to the
293      * specified value.
294      * @throws NullPointerException if the value is <code>null</code>.
295      * @see Map
296      * @since 1.2
297      */

298     public boolean containsValue(Object JavaDoc value) {
299     return contains(value);
300     }
301
302     /**
303      * Tests if the specified object is a key in this hashtable.
304      *
305      * @param key possible key.
306      * @return <code>true</code> if and only if the specified object
307      * is a key in this hashtable, as determined by the
308      * <tt>equals</tt> method; <code>false</code> otherwise.
309      * @throws NullPointerException if the key is <code>null</code>.
310      * @see #contains(Object)
311      */

312     public synchronized boolean containsKey(Object JavaDoc key) {
313     Entry tab[] = table;
314     int hash = key.hashCode();
315     int index = (hash & 0x7FFFFFFF) % tab.length;
316     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
317         if ((e.hash == hash) && e.key.equals(key)) {
318         return true;
319         }
320     }
321     return false;
322     }
323
324     /**
325      * Returns the value to which the specified key is mapped in this hashtable.
326      *
327      * @param key a key in the hashtable.
328      * @return the value to which the key is mapped in this hashtable;
329      * <code>null</code> if the key is not mapped to any value in
330      * this hashtable.
331      * @throws NullPointerException if the key is <code>null</code>.
332      * @see #put(Object, Object)
333      */

334     public synchronized V get(Object JavaDoc key) {
335     Entry tab[] = table;
336     int hash = key.hashCode();
337     int index = (hash & 0x7FFFFFFF) % tab.length;
338     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
339         if ((e.hash == hash) && e.key.equals(key)) {
340         return e.value;
341         }
342     }
343     return null;
344     }
345
346     /**
347      * Increases the capacity of and internally reorganizes this
348      * hashtable, in order to accommodate and access its entries more
349      * efficiently. This method is called automatically when the
350      * number of keys in the hashtable exceeds this hashtable's capacity
351      * and load factor.
352      */

353     protected void rehash() {
354     int oldCapacity = table.length;
355     Entry[] oldMap = table;
356
357     int newCapacity = oldCapacity * 2 + 1;
358     Entry[] newMap = new Entry[newCapacity];
359
360     modCount++;
361     threshold = (int)(newCapacity * loadFactor);
362     table = newMap;
363
364     for (int i = oldCapacity ; i-- > 0 ;) {
365         for (Entry<K,V> old = oldMap[i] ; old != null ; ) {
366         Entry<K,V> e = old;
367         old = old.next;
368
369         int index = (e.hash & 0x7FFFFFFF) % newCapacity;
370         e.next = newMap[index];
371         newMap[index] = e;
372         }
373     }
374     }
375
376     /**
377      * Maps the specified <code>key</code> to the specified
378      * <code>value</code> in this hashtable. Neither the key nor the
379      * value can be <code>null</code>. <p>
380      *
381      * The value can be retrieved by calling the <code>get</code> method
382      * with a key that is equal to the original key.
383      *
384      * @param key the hashtable key.
385      * @param value the value.
386      * @return the previous value of the specified key in this hashtable,
387      * or <code>null</code> if it did not have one.
388      * @exception NullPointerException if the key or value is
389      * <code>null</code>.
390      * @see Object#equals(Object)
391      * @see #get(Object)
392      */

393     public synchronized V put(K key, V value) {
394     // Make sure the value is not null
395
if (value == null) {
396         throw new NullPointerException JavaDoc();
397     }
398
399     // Makes sure the key is not already in the hashtable.
400
Entry tab[] = table;
401     int hash = key.hashCode();
402     int index = (hash & 0x7FFFFFFF) % tab.length;
403     for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
404         if ((e.hash == hash) && e.key.equals(key)) {
405         V old = e.value;
406         e.value = value;
407         return old;
408         }
409     }
410
411     modCount++;
412     if (count >= threshold) {
413         // Rehash the table if the threshold is exceeded
414
rehash();
415
416             tab = table;
417             index = (hash & 0x7FFFFFFF) % tab.length;
418     }
419
420     // Creates the new entry.
421
Entry<K,V> e = tab[index];
422     tab[index] = new Entry<K,V>(hash, key, value, e);
423     count++;
424     return null;
425     }
426
427     /**
428      * Removes the key (and its corresponding value) from this
429      * hashtable. This method does nothing if the key is not in the hashtable.
430      *
431      * @param key the key that needs to be removed.
432      * @return the value to which the key had been mapped in this hashtable,
433      * or <code>null</code> if the key did not have a mapping.
434      * @throws NullPointerException if the key is <code>null</code>.
435      */

436     public synchronized V remove(Object JavaDoc key) {
437     Entry tab[] = table;
438     int hash = key.hashCode();
439     int index = (hash & 0x7FFFFFFF) % tab.length;
440     for (Entry<K,V> e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
441         if ((e.hash == hash) && e.key.equals(key)) {
442         modCount++;
443         if (prev != null) {
444             prev.next = e.next;
445         } else {
446             tab[index] = e.next;
447         }
448         count--;
449         V oldValue = e.value;
450         e.value = null;
451         return oldValue;
452         }
453     }
454     return null;
455     }
456
457     /**
458      * Copies all of the mappings from the specified Map to this Hashtable
459      * These mappings will replace any mappings that this Hashtable had for any
460      * of the keys currently in the specified Map.
461      *
462      * @param t Mappings to be stored in this map.
463      * @throws NullPointerException if the specified map is null.
464      * @since 1.2
465      */

466     public synchronized void putAll(Map JavaDoc<? extends K, ? extends V> t) {
467     Iterator JavaDoc<? extends Map.Entry JavaDoc<? extends K, ? extends V>> i = t.entrySet().iterator();
468     while (i.hasNext()) {
469         Map.Entry JavaDoc<? extends K, ? extends V> e = i.next();
470         put(e.getKey(), e.getValue());
471     }
472     }
473
474     /**
475      * Clears this hashtable so that it contains no keys.
476      */

477     public synchronized void clear() {
478     Entry tab[] = table;
479     modCount++;
480     for (int index = tab.length; --index >= 0; )
481         tab[index] = null;
482     count = 0;
483     }
484
485     /**
486      * Creates a shallow copy of this hashtable. All the structure of the
487      * hashtable itself is copied, but the keys and values are not cloned.
488      * This is a relatively expensive operation.
489      *
490      * @return a clone of the hashtable.
491      */

492     public synchronized Object JavaDoc clone() {
493     try {
494         Hashtable JavaDoc<K,V> t = (Hashtable JavaDoc<K,V>) super.clone();
495         t.table = new Entry[table.length];
496         for (int i = table.length ; i-- > 0 ; ) {
497         t.table[i] = (table[i] != null)
498             ? (Entry<K,V>) table[i].clone() : null;
499         }
500         t.keySet = null;
501         t.entrySet = null;
502             t.values = null;
503         t.modCount = 0;
504         return t;
505     } catch (CloneNotSupportedException JavaDoc e) {
506         // this shouldn't happen, since we are Cloneable
507
throw new InternalError JavaDoc();
508     }
509     }
510
511     /**
512      * Returns a string representation of this <tt>Hashtable</tt> object
513      * in the form of a set of entries, enclosed in braces and separated
514      * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each
515      * entry is rendered as the key, an equals sign <tt>=</tt>, and the
516      * associated element, where the <tt>toString</tt> method is used to
517      * convert the key and element to strings. <p>Overrides to
518      * <tt>toString</tt> method of <tt>Object</tt>.
519      *
520      * @return a string representation of this hashtable.
521      */

522     public synchronized String JavaDoc toString() {
523     int max = size() - 1;
524     StringBuffer JavaDoc buf = new StringBuffer JavaDoc();
525     Iterator JavaDoc<Map.Entry JavaDoc<K,V>> it = entrySet().iterator();
526
527     buf.append("{");
528     for (int i = 0; i <= max; i++) {
529         Map.Entry JavaDoc<K,V> e = it.next();
530             K key = e.getKey();
531             V value = e.getValue();
532             buf.append((key == this ? "(this Map)" : (""+key)) + "=" +
533                        (value == this ? "(this Map)" : (""+value)));
534
535         if (i < max)
536         buf.append(", ");
537     }
538     buf.append("}");
539     return buf.toString();
540     }
541
542
543     private <T> Enumeration JavaDoc<T> getEnumeration(int type) {
544     if (count == 0) {
545         return (Enumeration JavaDoc<T>)emptyEnumerator;
546     } else {
547         return new Enumerator<T>(type, false);
548     }
549     }
550
551     private <T> Iterator JavaDoc<T> getIterator(int type) {
552     if (count == 0) {
553         return (Iterator JavaDoc<T>) emptyIterator;
554     } else {
555         return new Enumerator<T>(type, true);
556     }
557     }
558
559     // Views
560

561     /**
562      * Each of these fields are initialized to contain an instance of the
563      * appropriate view the first time this view is requested. The views are
564      * stateless, so there's no reason to create more than one of each.
565      */

566     private transient volatile Set JavaDoc<K> keySet = null;
567     private transient volatile Set JavaDoc<Map.Entry JavaDoc<K,V>> entrySet = null;
568     private transient volatile Collection JavaDoc<V> values = null;
569
570     /**
571      * Returns a Set view of the keys contained in this Hashtable. The Set
572      * is backed by the Hashtable, so changes to the Hashtable are reflected
573      * in the Set, and vice-versa. The Set supports element removal
574      * (which removes the corresponding entry from the Hashtable), but not
575      * element addition.
576      *
577      * @return a set view of the keys contained in this map.
578      * @since 1.2
579      */

580     public Set JavaDoc<K> keySet() {
581     if (keySet == null)
582         keySet = Collections.synchronizedSet(new KeySet(), this);
583     return keySet;
584     }
585
586     private class KeySet extends AbstractSet JavaDoc<K> {
587         public Iterator JavaDoc<K> iterator() {
588         return getIterator(KEYS);
589         }
590         public int size() {
591             return count;
592         }
593         public boolean contains(Object JavaDoc o) {
594             return containsKey(o);
595         }
596         public boolean remove(Object JavaDoc o) {
597             return Hashtable.this.remove(o) != null;
598         }
599         public void clear() {
600             Hashtable.this.clear();
601         }
602     }
603
604     /**
605      * Returns a Set view of the entries contained in this Hashtable.
606      * Each element in this collection is a Map.Entry. The Set is
607      * backed by the Hashtable, so changes to the Hashtable are reflected in
608      * the Set, and vice-versa. The Set supports element removal
609      * (which removes the corresponding entry from the Hashtable),
610      * but not element addition.
611      *
612      * @return a set view of the mappings contained in this map.
613      * @see Map.Entry
614      * @since 1.2
615      */

616     public Set JavaDoc<Map.Entry JavaDoc<K,V>> entrySet() {
617     if (entrySet==null)
618         entrySet = Collections.synchronizedSet(new EntrySet(), this);
619     return entrySet;
620     }
621
622     private class EntrySet extends AbstractSet JavaDoc/*<Map.Entry<K,V>>*/ {
623         public Iterator JavaDoc/*<Map.Entry<K,V>>*/ iterator() {
624         return getIterator(ENTRIES);
625         }
626
627     public boolean add(Object JavaDoc/*Map.Entry<K,V>*/ o) {
628         return super.add(o);
629     }
630
631         public boolean contains(Object JavaDoc o) {
632             if (!(o instanceof Map.Entry JavaDoc))
633                 return false;
634             Map.Entry JavaDoc entry = (Map.Entry JavaDoc)o;
635             Object JavaDoc key = entry.getKey();
636             Entry[] tab = table;
637             int hash = key.hashCode();
638             int index = (hash & 0x7FFFFFFF) % tab.length;
639
640             for (Entry e = tab[index]; e != null; e = e.next)
641                 if (e.hash==hash && e.equals(entry))
642                     return true;
643             return false;
644         }
645
646         public boolean remove(Object JavaDoc o) {
647             if (!(o instanceof Map.Entry JavaDoc))
648                 return false;
649             Map.Entry JavaDoc<K,V> entry = (Map.Entry JavaDoc<K,V>) o;
650         K key = entry.getKey();
651             Entry[] tab = table;
652             int hash = key.hashCode();
653             int index = (hash & 0x7FFFFFFF) % tab.length;
654
655             for (Entry<K,V> e = tab[index], prev = null; e != null;
656                  prev = e, e = e.next) {
657                 if (e.hash==hash && e.equals(entry)) {
658                     modCount++;
659                     if (prev != null)
660                         prev.next = e.next;
661                     else
662                         tab[index] = e.next;
663
664                     count--;
665                     e.value = null;
666                     return true;
667                 }
668             }
669             return false;
670         }
671
672         public int size() {
673             return count;
674         }
675
676         public void clear() {
677             Hashtable.this.clear();
678         }
679     }
680
681     /**
682      * Returns a Collection view of the values contained in this Hashtable.
683      * The Collection is backed by the Hashtable, so changes to the Hashtable
684      * are reflected in the Collection, and vice-versa. The Collection
685      * supports element removal (which removes the corresponding entry from
686      * the Hashtable), but not element addition.
687      *
688      * @return a collection view of the values contained in this map.
689      * @since 1.2
690      */

691     public Collection JavaDoc<V> values() {
692     if (values==null)
693         values = Collections.synchronizedCollection(new ValueCollection(),
694                                                         this);
695         return values;
696     }
697
698     private class ValueCollection extends AbstractCollection JavaDoc<V> {
699         public Iterator JavaDoc<V> iterator() {
700         return getIterator(VALUES);
701         }
702         public int size() {
703             return count;
704         }
705         public boolean contains(Object JavaDoc o) {
706             return containsValue(o);
707         }
708         public void clear() {
709             Hashtable.this.clear();
710         }
711     }
712
713     // Comparison and hashing
714

715     /**
716      * Compares the specified Object with this Map for equality,
717      * as per the definition in the Map interface.
718      *
719      * @param o object to be compared for equality with this Hashtable
720      * @return true if the specified Object is equal to this Map.
721      * @see Map#equals(Object)
722      * @since 1.2
723      */

724     public synchronized boolean equals(Object JavaDoc o) {
725     if (o == this)
726         return true;
727
728     if (!(o instanceof Map JavaDoc))
729         return false;
730     Map JavaDoc<K,V> t = (Map JavaDoc<K,V>) o;
731     if (t.size() != size())
732         return false;
733
734         try {
735             Iterator JavaDoc<Map.Entry JavaDoc<K,V>> i = entrySet().iterator();
736             while (i.hasNext()) {
737                 Map.Entry JavaDoc<K,V> e = i.next();
738                 K key = e.getKey();
739                 V value = e.getValue();
740                 if (value == null) {
741                     if (!(t.get(key)==null && t.containsKey(key)))
742                         return false;
743                 } else {
744                     if (!value.equals(t.get(key)))
745                         return false;
746                 }
747             }
748         } catch(ClassCastException JavaDoc unused) {
749             return false;
750         } catch(NullPointerException JavaDoc unused) {
751             return false;
752         }
753
754     return true;
755     }
756
757     /**
758      * Returns the hash code value for this Map as per the definition in the
759      * Map interface.
760      *
761      * @see Map#hashCode()
762      * @since 1.2
763      */

764     public synchronized int hashCode() {
765         /*
766          * This code detects the recursion caused by computing the hash code
767          * of a self-referential hash table and prevents the stack overflow
768          * that would otherwise result. This allows certain 1.1-era
769          * applets with self-referential hash tables to work. This code
770          * abuses the loadFactor field to do double-duty as a hashCode
771          * in progress flag, so as not to worsen the space performance.
772          * A negative load factor indicates that hash code computation is
773          * in progress.
774          */

775         int h = 0;
776         if (count == 0 || loadFactor < 0)
777             return h; // Returns zero
778

779         loadFactor = -loadFactor; // Mark hashCode computation in progress
780
Entry[] tab = table;
781         for (int i = 0; i < tab.length; i++)
782             for (Entry e = tab[i]; e != null; e = e.next)
783                 h += e.key.hashCode() ^ e.value.hashCode();
784         loadFactor = -loadFactor; // Mark hashCode computation complete
785

786     return h;
787     }
788
789     /**
790      * Save the state of the Hashtable to a stream (i.e., serialize it).
791      *
792      * @serialData The <i>capacity</i> of the Hashtable (the length of the
793      * bucket array) is emitted (int), followed by the
794      * <i>size</i> of the Hashtable (the number of key-value
795      * mappings), followed by the key (Object) and value (Object)
796      * for each key-value mapping represented by the Hashtable
797      * The key-value mappings are emitted in no particular order.
798      */

799     private synchronized void writeObject(java.io.ObjectOutputStream JavaDoc s)
800         throws IOException
801     {
802     // Write out the length, threshold, loadfactor
803
s.defaultWriteObject();
804
805     // Write out length, count of elements and then the key/value objects
806
s.writeInt(table.length);
807     s.writeInt(count);
808     for (int index = table.length-1; index >= 0; index--) {
809         Entry entry = table[index];
810
811         while (entry != null) {
812         s.writeObject(entry.key);
813         s.writeObject(entry.value);
814         entry = entry.next;
815         }
816     }
817     }
818
819     /**
820      * Reconstitute the Hashtable from a stream (i.e., deserialize it).
821      */

822     private void readObject(java.io.ObjectInputStream JavaDoc s)
823          throws IOException, ClassNotFoundException JavaDoc
824     {
825     // Read in the length, threshold, and loadfactor
826
s.defaultReadObject();
827
828     // Read the original length of the array and number of elements
829
int origlength = s.readInt();
830     int elements = s.readInt();
831
832     // Compute new size with a bit of room 5% to grow but
833
// no larger than the original size. Make the length
834
// odd if it's large enough, this helps distribute the entries.
835
// Guard against the length ending up zero, that's not valid.
836
int length = (int)(elements * loadFactor) + (elements / 20) + 3;
837     if (length > elements && (length & 1) == 0)
838         length--;
839     if (origlength > 0 && length > origlength)
840         length = origlength;
841
842     table = new Entry[length];
843     count = 0;
844
845     // Read the number of elements and then all the key/value objects
846
for (; elements > 0; elements--) {
847         K key = (K)s.readObject();
848         V value = (V)s.readObject();
849             // synch could be eliminated for performance
850
reconstitutionPut(key, value);
851     }
852     }
853
854     /**
855      * The put method used by readObject. This is provided because put
856      * is overridable and should not be called in readObject since the
857      * subclass will not yet be initialized.
858      *
859      * <p>This differs from the regular put method in several ways. No
860      * checking for rehashing is necessary since the number of elements
861      * initially in the table is known. The modCount is not incremented
862      * because we are creating a new instance. Also, no return value
863      * is needed.
864      */

865     private void reconstitutionPut(K key, V value)
866         throws StreamCorruptedException
867     {
868         if (value == null) {
869             throw new java.io.StreamCorruptedException JavaDoc();
870         }
871         // Makes sure the key is not already in the hashtable.
872
// This should not happen in deserialized version.
873
Entry[] tab = table;
874         int hash = key.hashCode();
875         int index = (hash & 0x7FFFFFFF) % tab.length;
876         for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
877             if ((e.hash == hash) && e.key.equals(key)) {
878                 throw new java.io.StreamCorruptedException JavaDoc();
879             }
880         }
881         // Creates the new entry.
882
Entry<K,V> e = tab[index];
883         tab[index] = new Entry<K,V>(hash, key, value, e);
884         count++;
885     }
886
887     /**
888      * Hashtable collision list.
889      */

890     private static class Entry<K,V> implements Map.Entry JavaDoc<K,V> {
891     int hash;
892     K key;
893     V value;
894     Entry<K,V> next;
895
896     protected Entry(int hash, K key, V value, Entry<K,V> next) {
897         this.hash = hash;
898         this.key = key;
899         this.value = value;
900         this.next = next;
901     }
902
903     protected Object JavaDoc clone() {
904         return new Entry<K,V>(hash, key, value,
905                   (next==null ? null : (Entry<K,V>) next.clone()));
906     }
907
908     // Map.Entry Ops
909

910     public K getKey() {
911         return key;
912     }
913
914     public V getValue() {
915         return value;
916     }
917
918     public V setValue(V value) {
919         if (value == null)
920         throw new NullPointerException JavaDoc();
921
922         V oldValue = this.value;
923         this.value = value;
924         return oldValue;
925     }
926
927     public boolean equals(Object JavaDoc o) {
928         if (!(o instanceof Map.Entry JavaDoc))
929         return false;
930         Map.Entry JavaDoc e = (Map.Entry JavaDoc)o;
931
932         return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
933            (value==null ? e.getValue()==null : value.equals(e.getValue()));
934     }
935
936     public int hashCode() {
937         return hash ^ (value==null ? 0 : value.hashCode());
938     }
939
940     public String JavaDoc toString() {
941         return key.toString()+"="+value.toString();
942     }
943     }
944
945     // Types of Enumerations/Iterations
946
private static final int KEYS = 0;
947     private static final int VALUES = 1;
948     private static final int ENTRIES = 2;
949
950     /**
951      * A hashtable enumerator class. This class implements both the
952      * Enumeration and Iterator interfaces, but individual instances
953      * can be created with the Iterator methods disabled. This is necessary
954      * to avoid unintentionally increasing the capabilities granted a user
955      * by passing an Enumeration.
956      */

957     private class Enumerator<T> implements Enumeration JavaDoc<T>, Iterator JavaDoc<T> {
958     Entry[] table = Hashtable.this.table;
959     int index = table.length;
960     Entry<K,V> entry = null;
961     Entry<K,V> lastReturned = null;
962     int type;
963
964     /**
965      * Indicates whether this Enumerator is serving as an Iterator
966      * or an Enumeration. (true -> Iterator).
967      */

968     boolean iterator;
969
970     /**
971      * The modCount value that the iterator believes that the backing
972      * List should have. If this expectation is violated, the iterator
973      * has detected concurrent modification.
974      */

975     protected int expectedModCount = modCount;
976
977     Enumerator(int type, boolean iterator) {
978         this.type = type;
979         this.iterator = iterator;
980     }
981
982     public boolean hasMoreElements() {
983         Entry<K,V> e = entry;
984         int i = index;
985         Entry[] t = table;
986         /* Use locals for faster loop iteration */
987         while (e == null && i > 0) {
988         e = t[--i];
989         }
990         entry = e;
991         index = i;
992         return e != null;
993     }
994
995     public T nextElement() {
996         Entry<K,V> et = entry;
997         int i = index;
998         Entry[] t = table;
999         /* Use locals for faster loop iteration */
1000        while (et == null && i > 0) {
1001        et = t[--i];
1002        }
1003        entry = et;
1004        index = i;
1005        if (et != null) {
1006        Entry<K,V> e = lastReturned = entry;
1007        entry = e.next;
1008        return type == KEYS ? (T)e.key : (type == VALUES ? (T)e.value : (T)e);
1009        }
1010        throw new NoSuchElementException JavaDoc("Hashtable Enumerator");
1011    }
1012
1013    // Iterator methods
1014
public boolean hasNext() {
1015        return hasMoreElements();
1016    }
1017
1018    public T next() {
1019        if (modCount != expectedModCount)
1020        throw new ConcurrentModificationException JavaDoc();
1021        return nextElement();
1022    }
1023
1024    public void remove() {
1025        if (!iterator)
1026        throw new UnsupportedOperationException JavaDoc();
1027        if (lastReturned == null)
1028        throw new IllegalStateException JavaDoc("Hashtable Enumerator");
1029        if (modCount != expectedModCount)
1030        throw new ConcurrentModificationException JavaDoc();
1031
1032        synchronized(Hashtable.this) {
1033        Entry[] tab = Hashtable.this.table;
1034        int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1035
1036        for (Entry<K,V> e = tab[index], prev = null; e != null;
1037             prev = e, e = e.next) {
1038            if (e == lastReturned) {
1039            modCount++;
1040            expectedModCount++;
1041            if (prev == null)
1042                tab[index] = e.next;
1043            else
1044                prev.next = e.next;
1045            count--;
1046            lastReturned = null;
1047            return;
1048            }
1049        }
1050        throw new ConcurrentModificationException JavaDoc();
1051        }
1052    }
1053    }
1054
1055   
1056    private static Enumeration JavaDoc emptyEnumerator = new EmptyEnumerator();
1057    private static Iterator JavaDoc emptyIterator = new EmptyIterator();
1058
1059    /**
1060     * A hashtable enumerator class for empty hash tables, specializes
1061     * the general Enumerator
1062     */

1063    private static class EmptyEnumerator implements Enumeration JavaDoc<Object JavaDoc> {
1064
1065    EmptyEnumerator() {
1066    }
1067
1068    public boolean hasMoreElements() {
1069        return false;
1070    }
1071
1072    public Object JavaDoc nextElement() {
1073        throw new NoSuchElementException JavaDoc("Hashtable Enumerator");
1074    }
1075    }
1076
1077
1078    /**
1079     * A hashtable iterator class for empty hash tables
1080     */

1081    private static class EmptyIterator implements Iterator JavaDoc<Object JavaDoc> {
1082
1083    EmptyIterator() {
1084    }
1085
1086    public boolean hasNext() {
1087        return false;
1088    }
1089
1090    public Object JavaDoc next() {
1091        throw new NoSuchElementException JavaDoc("Hashtable Iterator");
1092    }
1093
1094    public void remove() {
1095        throw new IllegalStateException JavaDoc("Hashtable Iterator");
1096    }
1097
1098    }
1099
1100}
1101
Popular Tags