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  <K,V>
107     implements Map  <K,V>, Cloneable  , java.io.Serializable   {
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  ("Illegal Capacity: "+
158                                                initialCapacity);
159         if (loadFactor <= 0 || Float.isNaN(loadFactor))
160             throw new IllegalArgumentException  ("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  <? 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  <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  <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   value) {
270     if (value == null) {
271         throw new NullPointerException  ();
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   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   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   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  ();
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   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  <? extends K, ? extends V> t) {
467     Iterator  <? extends Map.Entry  <? extends K, ? extends V>> i = t.entrySet().iterator();
468     while (i.hasNext()) {
469         Map.Entry  <? 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   clone() {
493     try { 
494         Hashtable  <K,V> t = (Hashtable  <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   e) { 
506         // this shouldn't happen, since we are Cloneable
507         throw new InternalError  ();
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   toString() {
523     int max = size() - 1;
524     StringBuffer   buf = new StringBuffer  ();
525     Iterator  <Map.Entry  <K,V>> it = entrySet().iterator();
526 
527     buf.append("{");
528     for (int i = 0; i <= max; i++) {
529         Map.Entry  <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  <T> getEnumeration(int type) {
544     if (count == 0) {
545         return (Enumeration  <T>)emptyEnumerator;
546     } else {
547         return new Enumerator<T>(type, false);
548     }
549     }
550 
551     private <T> Iterator  <T> getIterator(int type) {
552     if (count == 0) {
553         return (Iterator  <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  <K> keySet = null;
567     private transient volatile Set  <Map.Entry  <K,V>> entrySet = null;
568     private transient volatile Collection  <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  <K> keySet() {
581     if (keySet == null)
582         keySet = Collections.synchronizedSet(new KeySet(), this);
583     return keySet;
584     }
585 
586     private class KeySet extends AbstractSet  <K> {
587         public Iterator  <K> iterator() {
588         return getIterator(KEYS);
589         }
590         public int size() {
591             return count;
592         }
593         public boolean contains(Object   o) {
594             return containsKey(o);
595         }
596         public boolean remove(Object   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  <Map.Entry  <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  /*<Map.Entry<K,V>>*/ {
623         public Iterator  /*<Map.Entry<K,V>>*/ iterator() {
624         return getIterator(ENTRIES);
625         }
626 
627     public boolean add(Object  /*Map.Entry<K,V>*/ o) {
628         return super.add(o);
629     }
630 
631         public boolean contains(Object   o) {
632             if (!(o instanceof Map.Entry  ))
633                 return false;
634             Map.Entry   entry = (Map.Entry  )o;
635             Object   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   o) {
647             if (!(o instanceof Map.Entry  ))
648                 return false;
649             Map.Entry  <K,V> entry = (Map.Entry  <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  <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  <V> {
699         public Iterator  <V> iterator() {
700         return getIterator(VALUES);
701         }
702         public int size() {
703             return count;
704         }
705         public boolean contains(Object   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   o) {
725     if (o == this)
726         return true;
727 
728     if (!(o instanceof Map  ))
729         return false;
730     Map  <K,V> t = (Map  <K,V>) o;
731     if (t.size() != size())
732         return false;
733 
734         try {
735             Iterator  <Map.Entry  <K,V>> i = entrySet().iterator();
736             while (i.hasNext()) {
737                 Map.Entry  <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   unused)   {
749             return false;
750         } catch(NullPointerException   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   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   s)
823          throws IOException, ClassNotFoundException  
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  ();
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  ();
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  <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   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  ();
921 
922         V oldValue = this.value;
923         this.value = value;
924         return oldValue;
925     }
926 
927     public boolean equals(Object   o) {
928         if (!(o instanceof Map.Entry  ))
929         return false;
930         Map.Entry   e = (Map.Entry  )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   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  <T>, Iterator  <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  ("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  ();
1021        return nextElement();
1022    }
1023
1024    public void remove() {
1025        if (!iterator)
1026        throw new UnsupportedOperationException  ();
1027        if (lastReturned == null)
1028        throw new IllegalStateException  ("Hashtable Enumerator");
1029        if (modCount != expectedModCount)
1030        throw new ConcurrentModificationException  ();
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  ();
1051        }
1052    }
1053    }
1054
1055   
1056    private static Enumeration   emptyEnumerator = new EmptyEnumerator();
1057    private static Iterator   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  <Object  > {
1064
1065    EmptyEnumerator() {
1066    }
1067
1068    public boolean hasMoreElements() {
1069        return false;
1070    }
1071
1072    public Object   nextElement() {
1073        throw new NoSuchElementException  ("Hashtable Enumerator");
1074    }
1075    }
1076
1077
1078    /**
1079     * A hashtable iterator class for empty hash tables
1080     */
1081    private static class EmptyIterator implements Iterator  <Object  > {
1082
1083    EmptyIterator() {
1084    }
1085
1086    public boolean hasNext() {
1087        return false;
1088    }
1089
1090    public Object   next() {
1091        throw new NoSuchElementException  ("Hashtable Iterator");
1092    }
1093
1094    public void remove() {
1095        throw new IllegalStateException  ("Hashtable Iterator");
1096    }
1097
1098    }
1099
1100}
1101
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags