001    package railo.commons.collections;
002    
003    import java.io.IOException;
004    import java.util.AbstractCollection;
005    import java.util.AbstractSet;
006    import java.util.Collection;
007    import java.util.ConcurrentModificationException;
008    import java.util.Dictionary;
009    import java.util.Enumeration;
010    import java.util.Iterator;
011    import java.util.Map;
012    import java.util.NoSuchElementException;
013    import java.util.Set;
014    
015    /**
016     * This class implements a hashtable, which maps keys to values. Any 
017     * non-<code>null</code> object can be used as a key or as a value. <p>
018     *
019     * To successfully store and retrieve objects from a hashtable, the 
020     * objects used as keys must implement the <code>hashCode</code> 
021     * method and the <code>equals</code> method. <p>
022     *
023     * An instance of <code>Hashtable</code> has two parameters that affect its
024     * performance: <i>initial capacity</i> and <i>load factor</i>.  The
025     * <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the
026     * <i>initial capacity</i> is simply the capacity at the time the hash table
027     * is created.  Note that the hash table is <i>open</i>: in the case a "hash
028     * collision", a single bucket stores multiple entries, which must be searched
029     * sequentially.  The <i>load factor</i> is a measure of how full the hash
030     * table is allowed to get before its capacity is automatically increased.
031     * When the number of entries in the hashtable exceeds the product of the load
032     * factor and the current capacity, the capacity is increased by calling the
033     * <code>rehash</code> method.<p>
034     *
035     * Generally, the default load factor (.75) offers a good tradeoff between
036     * time and space costs.  Higher values decrease the space overhead but
037     * increase the time cost to look up an entry (which is reflected in most
038     * <tt>Hashtable</tt> operations, including <tt>get</tt> and <tt>put</tt>).<p>
039     *
040     * The initial capacity controls a tradeoff between wasted space and the
041     * need for <code>rehash</code> operations, which are time-consuming.
042     * No <code>rehash</code> operations will <i>ever</i> occur if the initial
043     * capacity is greater than the maximum number of entries the
044     * <tt>Hashtable</tt> will contain divided by its load factor.  However,
045     * setting the initial capacity too high can waste space.<p>
046     *
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. <p>
051     *
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     * <p>
069     * As of the Java 2 platform v1.2, this class has been retrofitted to
070     * implement Map, so that it becomes a part of Java's collection framework.
071     * Unlike the new collection implementations, Hashtable is synchronized.<p>
072     *
073     * The Iterators returned by the iterator and listIterator methods
074     * of the Collections returned by all of Hashtable's "collection view methods"
075     * are <em>fail-fast</em>: if the Hashtable is structurally modified
076     * at any time after the Iterator is created, in any way except through the
077     * Iterator's own remove or add methods, the Iterator will throw a
078     * ConcurrentModificationException.  Thus, in the face of concurrent
079     * modification, the Iterator fails quickly and cleanly, rather than risking
080     * arbitrary, non-deterministic behavior at an undetermined time in the future.
081     * The Enumerations returned by Hashtable's keys and values methods are
082     * <em>not</em> fail-fast.
083     *
084     * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
085     * as it is, generally speaking, impossible to make any hard guarantees in the
086     * presence of unsynchronized concurrent modification.  Fail-fast iterators
087     * throw <tt>ConcurrentModificationException</tt> on a best-effort basis. 
088     * Therefore, it would be wrong to write a program that depended on this
089     * exception for its correctness: <i>the fail-fast behavior of iterators
090     * should be used only to detect bugs.</i>
091     */
092    public final class HashTableNotSync extends Dictionary implements Map, Cloneable,
093                                                       java.io.Serializable {
094        /**
095         * The hash table data.
096         */
097        private transient Entry table[];
098    
099        /**
100         * The total number of entries in the hash table.
101         */
102        private transient int count;
103    
104        /**
105         * The table is rehashed when its size exceeds this threshold.  (The
106         * value of this field is (int)(capacity * loadFactor).)
107         *
108         * @serial
109         */
110        private int threshold;
111                                 
112        /**
113         * The load factor for the hashtable.
114         *
115         * @serial
116         */
117        private float loadFactor;
118    
119        /**
120         * The number of times this Hashtable has been structurally modified
121         * Structural modifications are those that change the number of entries in
122         * the Hashtable or otherwise modify its internal structure (e.g.,
123         * rehash).  This field is used to make iterators on Collection-views of
124         * the Hashtable fail-fast.  (See ConcurrentModificationException).
125         */
126        private transient int modCount = 0;
127    
128        /** use serialVersionUID from JDK 1.0.2 for interoperability */
129        private static final long serialVersionUID = 1421746759512286392L;
130    
131        /**
132         * Constructs a new, empty hashtable with the specified initial 
133         * capacity and the specified load factor.
134         *
135         * @param      initialCapacity   the initial capacity of the hashtable.
136         * @param      loadFactor        the load factor of the hashtable.
137         * @exception  IllegalArgumentException  if the initial capacity is less
138         *             than zero, or if the load factor is nonpositive.
139         */
140        public HashTableNotSync(int initialCapacity, float loadFactor) {
141        if (initialCapacity < 0)
142            throw new IllegalArgumentException("Illegal Capacity: "+
143                                                   initialCapacity);
144            if (loadFactor <= 0 || Float.isNaN(loadFactor))
145                throw new IllegalArgumentException("Illegal Load: "+loadFactor);
146    
147            if (initialCapacity==0)
148                initialCapacity = 1;
149        this.loadFactor = loadFactor;
150        table = new Entry[initialCapacity];
151        threshold = (int)(initialCapacity * loadFactor);
152        }
153    
154        /**
155         * Constructs a new, empty hashtable with the specified initial capacity
156         * and default load factor, which is <tt>0.75</tt>.
157         *
158         * @param     initialCapacity   the initial capacity of the hashtable.
159         * @exception IllegalArgumentException if the initial capacity is less
160         *              than zero.
161         */
162        public HashTableNotSync(int initialCapacity) {
163        this(initialCapacity, 0.75f);
164        }
165    
166        /**
167         * Constructs a new, empty hashtable with a default initial capacity (11)
168         * and load factor, which is <tt>0.75</tt>. 
169         */
170        public HashTableNotSync() {
171        this(11, 0.75f);
172        }
173    
174        /**
175         * Constructs a new hashtable with the same mappings as the given 
176         * Map.  The hashtable is created with an initial capacity sufficient to
177         * hold the mappings in the given Map and a default load factor, which is
178         * <tt>0.75</tt>.
179         *
180         * @param t the map whose mappings are to be placed in this map.
181         * @throws NullPointerException if the specified map is null.
182         *
183         */
184        public HashTableNotSync(Map t) {
185        this(Math.max(2*t.size(), 11), 0.75f);
186        putAll(t);
187        }
188    
189        /**
190         * Returns the number of keys in this hashtable.
191         *
192         * @return  the number of keys in this hashtable.
193         */
194        public int size() {
195        return count;
196        }
197    
198        /**
199         * Tests if this hashtable maps no keys to values.
200         *
201         * @return  <code>true</code> if this hashtable maps no keys to values;
202         *          <code>false</code> otherwise.
203         */
204        public boolean isEmpty() {
205        return count == 0;
206        }
207    
208        /**
209         * Returns an enumeration of the keys in this hashtable.
210         *
211         * @return  an enumeration of the keys in this hashtable.
212         * @see     Enumeration
213         * @see     #elements()
214         * @see #keySet()
215         * @see Map
216         */
217        public Enumeration keys() {
218        return getEnumeration(KEYS);
219        }
220    
221        /**
222         * Returns an enumeration of the values in this hashtable.
223         * Use the Enumeration methods on the returned object to fetch the elements
224         * sequentially.
225         *
226         * @return  an enumeration of the values in this hashtable.
227         * @see     java.util.Enumeration
228         * @see     #keys()
229         * @see #values()
230         * @see Map
231         */
232        public Enumeration elements() {
233        return getEnumeration(VALUES);
234        }
235    
236        /**
237         * Tests if some key maps into the specified value in this hashtable.
238         * This operation is more expensive than the <code>containsKey</code>
239         * method.<p>
240         *
241         * Note that this method is identical in functionality to containsValue,
242         * (which is part of the Map interface in the collections framework).
243         * 
244         * @param      value   a value to search for.
245         * @return     <code>true</code> if and only if some key maps to the
246         *             <code>value</code> argument in this hashtable as 
247         *             determined by the <tt>equals</tt> method;
248         *             <code>false</code> otherwise.
249         * @exception  NullPointerException  if the value is <code>null</code>.
250         * @see        #containsKey(Object)
251         * @see        #containsValue(Object)
252         * @see    Map
253         */
254        public boolean contains(Object value) {
255                if (value == null) {
256                    throw new NullPointerException();
257                }
258            
259                Entry tab[] = table;
260                for (int i = tab.length ; i-- > 0 ;) {
261                    for (Entry e = tab[i] ; e != null ; e = e.next) {
262                    if (e.value.equals(value)) {
263                        return true;
264                    }
265                    }
266                }
267                return false;
268        }
269    
270        /**
271         * Returns true if this Hashtable maps one or more keys to this value.<p>
272         *
273         * Note that this method is identical in functionality to contains
274         * (which predates the Map interface).
275         *
276         * @param value value whose presence in this Hashtable is to be tested.
277         * @return <tt>true</tt> if this map maps one or more keys to the
278         *         specified value.
279         * @see    Map
280    *
281         */
282        public boolean containsValue(Object value) {
283        return contains(value);
284        }
285    
286        /**
287         * Tests if the specified object is a key in this hashtable.
288         * 
289         * @param   key   possible key.
290         * @return  <code>true</code> if and only if the specified object 
291         *          is a key in this hashtable, as determined by the 
292         *          <tt>equals</tt> method; <code>false</code> otherwise.
293         * @see     #contains(Object)
294         */
295        public boolean containsKey(Object key) {
296        Entry tab[] = table;
297        int hash = key.hashCode();
298        int index = (hash & 0x7FFFFFFF) % tab.length;
299        for (Entry e = tab[index] ; e != null ; e = e.next) {
300            if ((e.hash == hash) && e.key.equals(key)) {
301            return true;
302            }
303        }
304        return false;
305        }
306    
307        /**
308         * Returns the value to which the specified key is mapped in this hashtable.
309         *
310         * @param   key   a key in the hashtable.
311         * @return  the value to which the key is mapped in this hashtable;
312         *          <code>null</code> if the key is not mapped to any value in
313         *          this hashtable.
314         * @see     #put(Object, Object)
315         */
316        public Object get(Object key) {
317                Entry tab[] = table;
318                int hash = key.hashCode();
319                int index = (hash & 0x7FFFFFFF) % tab.length;
320                for (Entry e = tab[index] ; e != null ; e = e.next) {
321                    if ((e.hash == hash) && e.key.equals(key)) {
322                            return e.value;
323                    }
324                }
325                return null;
326        }
327    
328        /**
329         * Increases the capacity of and internally reorganizes this 
330         * hashtable, in order to accommodate and access its entries more 
331         * efficiently.  This method is called automatically when the 
332         * number of keys in the hashtable exceeds this hashtable's capacity 
333         * and load factor. 
334         */
335        protected void rehash() {
336        int oldCapacity = table.length;
337        Entry oldMap[] = table;
338    
339        int newCapacity = oldCapacity * 2 + 1;
340        Entry newMap[] = new Entry[newCapacity];
341    
342        modCount++;
343        threshold = (int)(newCapacity * loadFactor);
344        table = newMap;
345    
346        for (int i = oldCapacity ; i-- > 0 ;) {
347            for (Entry old = oldMap[i] ; old != null ; ) {
348            Entry e = old;
349            old = old.next;
350    
351            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
352            e.next = newMap[index];
353            newMap[index] = e;
354            }
355        }
356        }
357    
358        /**
359         * Maps the specified <code>key</code> to the specified 
360         * <code>value</code> in this hashtable. Neither the key nor the 
361         * value can be <code>null</code>. <p>
362         *
363         * The value can be retrieved by calling the <code>get</code> method 
364         * with a key that is equal to the original key. 
365         *
366         * @param      key     the hashtable key.
367         * @param      value   the value.
368         * @return     the previous value of the specified key in this hashtable,
369         *             or <code>null</code> if it did not have one.
370         * @exception  NullPointerException  if the key or value is
371         *               <code>null</code>.
372         * @see     Object#equals(Object)
373         * @see     #get(Object)
374         */
375        public Object put(Object key, Object value) {
376                // Make sure the value is not null
377                if (value == null) {
378                    return remove(key);
379                }
380            
381                // Makes sure the key is not already in the hashtable.
382                Entry tab[] = table;
383                int hash = key.hashCode();
384                int index = (hash & 0x7FFFFFFF) % tab.length;
385                for (Entry e = tab[index] ; e != null ; e = e.next) {
386                    if ((e.hash == hash) && e.key.equals(key)) {
387                    Object old = e.value;
388                    e.value = value;
389                    return old;
390                }
391        }
392    
393        modCount++;
394        if (count >= threshold) {
395            // Rehash the table if the threshold is exceeded
396            rehash();
397    
398                tab = table;
399                index = (hash & 0x7FFFFFFF) % tab.length;
400        } 
401    
402        // Creates the new entry.
403        Entry e = new Entry(hash, key, value, tab[index]);
404        tab[index] = e;
405        count++;
406        return null;
407        }
408    
409        /**
410         * Removes the key (and its corresponding value) from this 
411         * hashtable. This method does nothing if the key is not in the hashtable.
412         *
413         * @param   key   the key that needs to be removed.
414         * @return  the value to which the key had been mapped in this hashtable,
415         *          or <code>null</code> if the key did not have a mapping.
416         */
417        public Object remove(Object key) {
418        Entry tab[] = table;
419        int hash = key.hashCode();
420        int index = (hash & 0x7FFFFFFF) % tab.length;
421        for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
422            if ((e.hash == hash) && e.key.equals(key)) {
423            modCount++;
424            if (prev != null) {
425                prev.next = e.next;
426            } else {
427                tab[index] = e.next;
428            }
429            count--;
430            Object oldValue = e.value;
431            e.value = null;
432            return oldValue;
433            }
434        }
435        return null;
436        }
437    
438        /**
439         * Copies all of the mappings from the specified Map to this Hashtable
440         * These mappings will replace any mappings that this Hashtable had for any
441         * of the keys currently in the specified Map. 
442         *
443         * @param t Mappings to be stored in this map.
444         * @throws NullPointerException if the specified map is null.
445    *
446         */
447        public void putAll(Map t) {
448        Iterator i = t.entrySet().iterator();
449        while (i.hasNext()) {
450            Map.Entry e = (Map.Entry) i.next();
451            put(e.getKey(), e.getValue());
452        }
453        }
454    
455        /**
456         * Clears this hashtable so that it contains no keys. 
457         */
458        public void clear() {
459        Entry tab[] = table;
460        modCount++;
461        for (int index = tab.length; --index >= 0; )
462            tab[index] = null;
463        count = 0;
464        }
465    
466        /**
467         * Creates a shallow copy of this hashtable. All the structure of the 
468         * hashtable itself is copied, but the keys and values are not cloned. 
469         * This is a relatively expensive operation.
470         *
471         * @return  a clone of the hashtable.
472         */
473        public Object clone() {
474        try { 
475            HashTableNotSync t = (HashTableNotSync)super.clone();
476            t.table = new Entry[table.length];
477            for (int i = table.length ; i-- > 0 ; ) {
478            t.table[i] = (table[i] != null) 
479                ? (Entry)table[i].clone() : null;
480            }
481            t.keySet = null;
482            t.entrySet = null;
483                t.values = null;
484            t.modCount = 0;
485            return t;
486        } catch (CloneNotSupportedException e) { 
487            // this shouldn't happen, since we are Cloneable
488            throw new InternalError();
489        }
490        }
491    
492        /**
493         * Returns a string representation of this <tt>Hashtable</tt> object 
494         * in the form of a set of entries, enclosed in braces and separated 
495         * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each 
496         * entry is rendered as the key, an equals sign <tt>=</tt>, and the 
497         * associated element, where the <tt>toString</tt> method is used to 
498         * convert the key and element to strings. <p>Overrides to 
499         * <tt>toString</tt> method of <tt>Object</tt>.
500         *
501         * @return  a string representation of this hashtable.
502         */
503        public String toString() {
504        int max = size() - 1;
505        StringBuffer buf = new StringBuffer();
506        Iterator it = entrySet().iterator();
507    
508        buf.append("{");
509        for (int i = 0; i <= max; i++) {
510            Map.Entry e = (Map.Entry) (it.next());
511                Object key = e.getKey();
512                Object value = e.getValue();
513                buf.append((key   == this ? "(this Map)" : key) + "=" + 
514                           (value == this ? "(this Map)" : value));
515    
516            if (i < max)
517            buf.append(", ");
518        }
519        buf.append("}");
520        return buf.toString();
521        }
522    
523    
524        private Enumeration getEnumeration(int type) {
525            if (count == 0) {
526                return emptyEnumerator;
527            } 
528            return new Enumerator(type, false);
529            
530        }
531    
532        private Iterator getIterator(int type) {
533            if (count == 0) {
534                return emptyIterator;
535            } 
536            return new Enumerator(type, true);
537        }
538    
539        // Views
540    
541        /**
542         * Each of these fields are initialized to contain an instance of the
543         * appropriate view the first time this view is requested.  The views are
544         * stateless, so there's no reason to create more than one of each.
545         */
546        private transient volatile Set keySet = null;
547        private transient volatile Set entrySet = null;
548        private transient volatile Collection values = null;
549    
550        /**
551         * Returns a Set view of the keys contained in this Hashtable.  The Set
552         * is backed by the Hashtable, so changes to the Hashtable are reflected
553         * in the Set, and vice-versa.  The Set supports element removal
554         * (which removes the corresponding entry from the Hashtable), but not
555         * element addition.
556         *
557         * @return a set view of the keys contained in this map.
558    *
559         */
560        public Set keySet() {
561        if (keySet == null)
562            keySet = Collections.synchronizedSet(new KeySet(), this);
563        return keySet;
564        }
565    
566        private class KeySet extends AbstractSet {
567            /**
568             * @see java.util.Set#iterator()
569             */
570            public Iterator iterator() {
571            return getIterator(KEYS);
572            }
573            /**
574             * @see java.util.Set#size()
575             */
576            public int size() {
577                return count;
578            }
579            /**
580             * @see java.util.Set#contains(java.lang.Object)
581             */
582            public boolean contains(Object o) {
583                return containsKey(o);
584            }
585            /**
586             * @see java.util.Set#remove(java.lang.Object)
587             */
588            public boolean remove(Object o) {
589                return HashTableNotSync.this.remove(o) != null;
590            }
591            /**
592             * @see java.util.Set#clear()
593             */
594            public void clear() {
595                HashTableNotSync.this.clear();
596            }
597        }
598    
599        /**
600         * Returns a Set view of the entries contained in this Hashtable.
601         * Each element in this collection is a Map.Entry.  The Set is
602         * backed by the Hashtable, so changes to the Hashtable are reflected in
603         * the Set, and vice-versa.  The Set supports element removal
604         * (which removes the corresponding entry from the Hashtable),
605         * but not element addition.
606         *
607         * @return a set view of the mappings contained in this map.
608         * @see   Map.Entry
609    *
610         */
611        public Set entrySet() {
612        if (entrySet==null)
613            entrySet = Collections.synchronizedSet(new EntrySet(), this);
614        return entrySet;
615        }
616    
617        private class EntrySet extends AbstractSet {
618            /**
619             * @see java.util.Set#iterator()
620             */
621            public Iterator iterator() {
622            return getIterator(ENTRIES);
623            }
624    
625            /**
626             * @see java.util.Set#contains(java.lang.Object)
627             */
628            public boolean contains(Object o) {
629                if (!(o instanceof Map.Entry))
630                    return false;
631                Map.Entry entry = (Map.Entry)o;
632                Object key = entry.getKey();
633                Entry tab[] = table;
634                int hash = key.hashCode();
635                int index = (hash & 0x7FFFFFFF) % tab.length;
636    
637                for (Entry e = tab[index]; e != null; e = e.next)
638                    if (e.hash==hash && e.equals(entry))
639                        return true;
640                return false;
641            }
642    
643            /**
644             * @see java.util.Set#remove(java.lang.Object)
645             */
646            public boolean remove(Object o) {
647                if (!(o instanceof Map.Entry))
648                    return false;
649                Map.Entry entry = (Map.Entry)o;
650                Object key = entry.getKey();
651                Entry tab[] = table;
652                int hash = key.hashCode();
653                int index = (hash & 0x7FFFFFFF) % tab.length;
654    
655                for (Entry 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            /**
673             * @see java.util.Set#size()
674             */
675            public int size() {
676                return count;
677            }
678    
679            /**
680             * @see java.util.Set#clear()
681             */
682            public void clear() {
683                HashTableNotSync.this.clear();
684            }
685        }
686    
687        /**
688         * Returns a Collection view of the values contained in this Hashtable.
689         * The Collection is backed by the Hashtable, so changes to the Hashtable
690         * are reflected in the Collection, and vice-versa.  The Collection
691         * supports element removal (which removes the corresponding entry from
692         * the Hashtable), but not element addition.
693         *
694         * @return a collection view of the values contained in this map.
695    *
696         */
697        public Collection values() {
698        if (values==null)
699            values = Collections.synchronizedCollection(new ValueCollection(),
700                                                            this);
701            return values;
702        }
703    
704        private class ValueCollection extends AbstractCollection {
705            /**
706             * @see java.util.AbstractCollection#iterator()
707             */
708            public Iterator iterator() {
709            return getIterator(VALUES);
710            }
711            /**
712             * @see java.util.AbstractCollection#size()
713             */
714            public int size() {
715                return count;
716            }
717            /**
718             * @see java.util.AbstractCollection#contains(java.lang.Object)
719             */
720            public boolean contains(Object o) {
721                return containsValue(o);
722            }
723            /**
724             * @see java.util.AbstractCollection#clear()
725             */
726            public void clear() {
727                HashTableNotSync.this.clear();
728            }
729        }
730    
731        // Comparison and hashing
732    
733        /**
734         * Compares the specified Object with this Map for equality,
735         * as per the definition in the Map interface.
736         *
737         * @param  o object to be compared for equality with this Hashtable
738         * @return true if the specified Object is equal to this Map.
739         * @see Map#equals(Object)
740    *
741         */
742        public boolean equals(Object o) {
743        if (o == this)
744            return true;
745    
746        if (!(o instanceof Map))
747            return false;
748        Map t = (Map) o;
749        if (t.size() != size())
750            return false;
751    
752            try {
753                Iterator i = entrySet().iterator();
754                while (i.hasNext()) {
755                    Map.Entry e = (Map.Entry) i.next();
756                    Object key = e.getKey();
757                    Object value = e.getValue();
758                    if (value == null) {
759                        if (!(t.get(key)==null && t.containsKey(key)))
760                            return false;
761                    } else {
762                        if (!value.equals(t.get(key)))
763                            return false;
764                    }
765                }
766            } catch(ClassCastException unused)   {
767                return false;
768            } catch(NullPointerException unused) {
769                return false;
770            }
771    
772        return true;
773        }
774    
775        /**
776         * Returns the hash code value for this Map as per the definition in the
777         * Map interface.
778         *
779         * @see Map#hashCode()
780    *
781         */
782        public int hashCode() {
783            /*
784             * This code detects the recursion caused by computing the hash code
785             * of a self-referential hash table and prevents the stack overflow
786             * that would otherwise result.  This allows certain 1.1-era
787             * applets with self-referential hash tables to work.  This code
788             * abuses the loadFactor field to do double-duty as a hashCode
789             * in progress flag, so as not to worsen the space performance.
790             * A negative load factor indicates that hash code computation is
791             * in progress.
792             */
793            int h = 0;
794            if (count == 0 || loadFactor < 0)
795                return h;  // Returns zero
796    
797            loadFactor = -loadFactor;  // Mark hashCode computation in progress
798            Entry tab[] = table;
799            for (int i = 0; i < tab.length; i++)
800                for (Entry e = tab[i]; e != null; e = e.next)
801                    h += e.key.hashCode() ^ e.value.hashCode();
802            loadFactor = -loadFactor;  // Mark hashCode computation complete
803    
804        return h;
805        }
806    
807        /**
808         * Save the state of the Hashtable to a stream (i.e., serialize it).
809         * @param s
810         * @throws IOException
811         *
812         * @serialData The <i>capacity</i> of the Hashtable (the length of the
813         *         bucket array) is emitted (int), followed  by the
814         *         <i>size</i> of the Hashtable (the number of key-value
815         *         mappings), followed by the key (Object) and value (Object)
816         *         for each key-value mapping represented by the Hashtable
817         *         The key-value mappings are emitted in no particular order.
818         */
819        private void writeObject(java.io.ObjectOutputStream s)
820            throws IOException
821        {
822        // Write out the length, threshold, loadfactor
823        s.defaultWriteObject();
824    
825        // Write out length, count of elements and then the key/value objects
826        s.writeInt(table.length);
827        s.writeInt(count);
828        for (int index = table.length-1; index >= 0; index--) {
829            Entry entry = table[index];
830    
831            while (entry != null) {
832            s.writeObject(entry.key);
833            s.writeObject(entry.value);
834            entry = entry.next;
835            }
836        }
837        }
838    
839        /**
840         * Reconstitute the Hashtable from a stream (i.e., deserialize it).
841         * @param s
842         * @throws IOException
843         * @throws ClassNotFoundException
844         */
845        private void readObject(java.io.ObjectInputStream s)
846             throws IOException, ClassNotFoundException
847        {
848        // Read in the length, threshold, and loadfactor
849        s.defaultReadObject();
850    
851        // Read the original length of the array and number of elements
852        int origlength = s.readInt();
853        int elements = s.readInt();
854    
855        // Compute new size with a bit of room 5% to grow but
856        // No larger than the original size.  Make the length
857        // odd if it's large enough, this helps distribute the entries.
858        // Guard against the length ending up zero, that's not valid.
859        int length = (int)(elements * loadFactor) + (elements / 20) + 3;
860        if (length > elements && (length & 1) == 0)
861            length--;
862        if (origlength > 0 && length > origlength)
863            length = origlength;
864    
865        table = new Entry[length];
866        count = 0;
867    
868        // Read the number of elements and then all the key/value objects
869        for (; elements > 0; elements--) {
870            Object key = s.readObject();
871            Object value = s.readObject();
872            put(key, value);
873        }
874        }
875    
876    
877        /**
878         * Hashtable collision list.
879         */
880        private static class Entry implements Map.Entry {
881        int hash;
882        Object key;
883        Object value;
884        Entry next;
885    
886        /**
887         * @param hash
888         * @param key
889         * @param value
890         * @param next
891         */
892        protected Entry(int hash, Object key, Object value, Entry next) {
893            this.hash = hash;
894            this.key = key;
895            this.value = value;
896            this.next = next;
897        }
898    
899        /**
900         * @see java.lang.Object#clone()
901         */
902        protected Object clone() {
903            return new Entry(hash, key, value,
904                     (next==null ? null : (Entry)next.clone()));
905        }
906    
907        // Map.Entry Ops 
908    
909        /**
910         * @see java.util.Map.Entry#getKey()
911         */
912        public Object getKey() {
913            return key;
914        }
915    
916        /**
917         * @see java.util.Map.Entry#getValue()
918         */
919        public Object getValue() {
920            return value;
921        }
922    
923        /**
924         * @see java.util.Map.Entry#setValue(java.lang.Object)
925         */
926        public Object setValue(Object value) {
927            if (value == null)
928            throw new NullPointerException();
929    
930            Object oldValue = this.value;
931            this.value = value;
932            return oldValue;
933        }
934    
935        /**
936         * @see java.util.Map.Entry#equals(java.lang.Object)
937         */
938        public boolean equals(Object o) {
939            if (!(o instanceof Map.Entry))
940            return false;
941            Map.Entry e = (Map.Entry)o;
942    
943            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
944               (value==null ? e.getValue()==null : value.equals(e.getValue()));
945        }
946    
947        /**
948         * @see java.util.Map.Entry#hashCode()
949         */
950        public int hashCode() {
951            return hash ^ (value==null ? 0 : value.hashCode());
952        }
953    
954        /**
955         * @see java.lang.Object#toString()
956         */
957        public String toString() {
958            return key.toString()+"="+value.toString();
959        }
960        }
961    
962        // Types of Enumerations/Iterations
963        private static final int KEYS = 0;
964        private static final int VALUES = 1;
965        private static final int ENTRIES = 2;
966    
967        /**
968         * A hashtable enumerator class.  This class implements both the
969         * Enumeration and Iterator interfaces, but individual instances
970         * can be created with the Iterator methods disabled.  This is necessary
971         * to avoid unintentionally increasing the capabilities granted a user
972         * by passing an Enumeration.
973         */
974        private class Enumerator implements Enumeration, Iterator {
975        Entry[] table = HashTableNotSync.this.table;
976        int index = table.length;
977        Entry entry = null;
978        Entry lastReturned = null;
979        int type;
980    
981        /**
982         * Indicates whether this Enumerator is serving as an Iterator
983         * or an Enumeration.  (true -> Iterator).
984         */
985        boolean iterator;
986    
987        /**
988         * The modCount value that the iterator believes that the backing
989         * List should have.  If this expectation is violated, the iterator
990         * has detected concurrent modification.
991         */
992        protected int expectedModCount = modCount;
993    
994        Enumerator(int type, boolean iterator) {
995            this.type = type;
996            this.iterator = iterator;
997        }
998    
999        /**
1000         * @see java.util.Enumeration#hasMoreElements()
1001         */
1002        public boolean hasMoreElements() {
1003            Entry e = entry;
1004            int i = index;
1005            Entry t[] = table;
1006            /* Use locals for faster loop iteration */
1007            while (e == null && i > 0) { 
1008            e = t[--i];
1009            }
1010            entry = e;
1011            index = i;
1012            return e != null;
1013        }
1014    
1015        /**
1016         * @see java.util.Enumeration#nextElement()
1017         */
1018        public Object nextElement() {
1019            Entry et = entry;
1020            int i = index;
1021            Entry t[] = table;
1022            /* Use locals for faster loop iteration */
1023            while (et == null && i > 0) { 
1024            et = t[--i];
1025            }
1026            entry = et;
1027            index = i;
1028            if (et != null) {
1029            Entry e = lastReturned = entry;
1030            entry = e.next;
1031            return type == KEYS ? e.key : (type == VALUES ? e.value : e);
1032            }
1033            throw new NoSuchElementException("Hashtable Enumerator");
1034        }
1035    
1036        /**
1037         * @see java.util.Iterator#hasNext()
1038         */
1039        // Iterator methods
1040        public boolean hasNext() {
1041            return hasMoreElements();
1042        }
1043    
1044        /**
1045         * @see java.util.Iterator#next()
1046         */
1047        public Object next() {
1048            if (modCount != expectedModCount)
1049            throw new ConcurrentModificationException();
1050            return nextElement();
1051        }
1052    
1053        /**
1054         * @see java.util.Iterator#remove()
1055         */
1056        public void remove() {
1057            if (!iterator)
1058            throw new UnsupportedOperationException();
1059            if (lastReturned == null)
1060            throw new IllegalStateException("Hashtable Enumerator");
1061            if (modCount != expectedModCount)
1062            throw new ConcurrentModificationException();
1063    
1064            synchronized(HashTableNotSync.this) {
1065            Entry[] tab = HashTableNotSync.this.table;
1066            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
1067    
1068            for (Entry e = tab[index], prev = null; e != null;
1069                 prev = e, e = e.next) {
1070                if (e == lastReturned) {
1071                modCount++;
1072                expectedModCount++;
1073                if (prev == null)
1074                    tab[index] = e.next;
1075                else
1076                    prev.next = e.next;
1077                count--;
1078                lastReturned = null;
1079                return;
1080                }
1081            }
1082            throw new ConcurrentModificationException();
1083            }
1084        }
1085        }
1086    
1087       
1088        private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
1089        private static EmptyIterator emptyIterator = new EmptyIterator();
1090    
1091        /**
1092         * A hashtable enumerator class for empty hash tables, specializes
1093         * the general Enumerator
1094         */
1095        private static class EmptyEnumerator implements Enumeration {
1096    
1097        EmptyEnumerator() {
1098        }
1099    
1100        /**
1101         * @see java.util.Enumeration#hasMoreElements()
1102         */
1103        public boolean hasMoreElements() {
1104            return false;
1105        }
1106    
1107        /**
1108         * @see java.util.Enumeration#nextElement()
1109         */
1110        public Object nextElement() {
1111            throw new NoSuchElementException("Hashtable Enumerator");
1112        }
1113        }
1114    
1115    
1116        /**
1117         * A hashtable iterator class for empty hash tables
1118         */
1119        private static class EmptyIterator implements Iterator {
1120    
1121        EmptyIterator() {
1122        }
1123    
1124        /**
1125         * @see java.util.Iterator#hasNext()
1126         */
1127        public boolean hasNext() {
1128            return false;
1129        }
1130    
1131        /**
1132         * @see java.util.Iterator#next()
1133         */
1134        public Object next() {
1135            throw new NoSuchElementException("Hashtable Iterator");
1136        }
1137    
1138        /**
1139         * @see java.util.Iterator#remove()
1140         */
1141        public void remove() {
1142            throw new IllegalStateException("Hashtable Iterator");
1143        }
1144    
1145        }
1146    
1147    }