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        @Override
209        public Enumeration keys() {
210        return getEnumeration(KEYS);
211        }
212    
213        @Override
214        public Enumeration elements() {
215        return getEnumeration(VALUES);
216        }
217    
218        public boolean contains(Object value) {
219                if (value == null) {
220                    throw new NullPointerException();
221                }
222            
223                Entry tab[] = table;
224                for (int i = tab.length ; i-- > 0 ;) {
225                    for (Entry e = tab[i] ; e != null ; e = e.next) {
226                    if (e.value.equals(value)) {
227                        return true;
228                    }
229                    }
230                }
231                return false;
232        }
233    
234        @Override
235        public boolean containsValue(Object value) {
236        return contains(value);
237        }
238    
239        @Override
240        public boolean containsKey(Object key) {
241        Entry tab[] = table;
242        int hash = key.hashCode();
243        int index = (hash & 0x7FFFFFFF) % tab.length;
244        for (Entry e = tab[index] ; e != null ; e = e.next) {
245            if ((e.hash == hash) && e.key.equals(key)) {
246            return true;
247            }
248        }
249        return false;
250        }
251    
252        @Override
253        public Object get(Object key) {
254                Entry tab[] = table;
255                int hash = key.hashCode();
256                int index = (hash & 0x7FFFFFFF) % tab.length;
257                for (Entry e = tab[index] ; e != null ; e = e.next) {
258                    if ((e.hash == hash) && e.key.equals(key)) {
259                            return e.value;
260                    }
261                }
262                return null;
263        }
264    
265        /**
266         * Increases the capacity of and internally reorganizes this 
267         * hashtable, in order to accommodate and access its entries more 
268         * efficiently.  This method is called automatically when the 
269         * number of keys in the hashtable exceeds this hashtable's capacity 
270         * and load factor. 
271         */
272        protected void rehash() {
273        int oldCapacity = table.length;
274        Entry oldMap[] = table;
275    
276        int newCapacity = oldCapacity * 2 + 1;
277        Entry newMap[] = new Entry[newCapacity];
278    
279        modCount++;
280        threshold = (int)(newCapacity * loadFactor);
281        table = newMap;
282    
283        for (int i = oldCapacity ; i-- > 0 ;) {
284            for (Entry old = oldMap[i] ; old != null ; ) {
285            Entry e = old;
286            old = old.next;
287    
288            int index = (e.hash & 0x7FFFFFFF) % newCapacity;
289            e.next = newMap[index];
290            newMap[index] = e;
291            }
292        }
293        }
294    
295        @Override
296        public Object put(Object key, Object value) {
297                // Make sure the value is not null
298                if (value == null) {
299                    return remove(key);
300                }
301            
302                // Makes sure the key is not already in the hashtable.
303                Entry tab[] = table;
304                int hash = key.hashCode();
305                int index = (hash & 0x7FFFFFFF) % tab.length;
306                for (Entry e = tab[index] ; e != null ; e = e.next) {
307                    if ((e.hash == hash) && e.key.equals(key)) {
308                    Object old = e.value;
309                    e.value = value;
310                    return old;
311                }
312        }
313    
314        modCount++;
315        if (count >= threshold) {
316            // Rehash the table if the threshold is exceeded
317            rehash();
318    
319                tab = table;
320                index = (hash & 0x7FFFFFFF) % tab.length;
321        } 
322    
323        // Creates the new entry.
324        Entry e = new Entry(hash, key, value, tab[index]);
325        tab[index] = e;
326        count++;
327        return null;
328        }
329    
330        /**
331         * Removes the key (and its corresponding value) from this 
332         * hashtable. This method does nothing if the key is not in the hashtable.
333         *
334         * @param   key   the key that needs to be removed.
335         * @return  the value to which the key had been mapped in this hashtable,
336         *          or <code>null</code> if the key did not have a mapping.
337         */
338        public Object remove(Object key) {
339        Entry tab[] = table;
340        int hash = key.hashCode();
341        int index = (hash & 0x7FFFFFFF) % tab.length;
342        for (Entry e = tab[index], prev = null ; e != null ; prev = e, e = e.next) {
343            if ((e.hash == hash) && e.key.equals(key)) {
344            modCount++;
345            if (prev != null) {
346                prev.next = e.next;
347            } else {
348                tab[index] = e.next;
349            }
350            count--;
351            Object oldValue = e.value;
352            e.value = null;
353            return oldValue;
354            }
355        }
356        return null;
357        }
358    
359        /**
360         * Copies all of the mappings from the specified Map to this Hashtable
361         * These mappings will replace any mappings that this Hashtable had for any
362         * of the keys currently in the specified Map. 
363         *
364         * @param t Mappings to be stored in this map.
365         * @throws NullPointerException if the specified map is null.
366    *
367         */
368        public void putAll(Map t) {
369        Iterator i = t.entrySet().iterator();
370        while (i.hasNext()) {
371            Map.Entry e = (Map.Entry) i.next();
372            put(e.getKey(), e.getValue());
373        }
374        }
375    
376        /**
377         * Clears this hashtable so that it contains no keys. 
378         */
379        public void clear() {
380        Entry tab[] = table;
381        modCount++;
382        for (int index = tab.length; --index >= 0; )
383            tab[index] = null;
384        count = 0;
385        }
386    
387        /**
388         * Creates a shallow copy of this hashtable. All the structure of the 
389         * hashtable itself is copied, but the keys and values are not cloned. 
390         * This is a relatively expensive operation.
391         *
392         * @return  a clone of the hashtable.
393         */
394        public Object clone() {
395        try { 
396            HashTableNotSync t = (HashTableNotSync)super.clone();
397            t.table = new Entry[table.length];
398            for (int i = table.length ; i-- > 0 ; ) {
399            t.table[i] = (table[i] != null) 
400                ? (Entry)table[i].clone() : null;
401            }
402            t.keySet = null;
403            t.entrySet = null;
404                t.values = null;
405            t.modCount = 0;
406            return t;
407        } catch (CloneNotSupportedException e) { 
408            // this shouldn't happen, since we are Cloneable
409            throw new InternalError();
410        }
411        }
412    
413        /**
414         * Returns a string representation of this <tt>Hashtable</tt> object 
415         * in the form of a set of entries, enclosed in braces and separated 
416         * by the ASCII characters "<tt>,&nbsp;</tt>" (comma and space). Each 
417         * entry is rendered as the key, an equals sign <tt>=</tt>, and the 
418         * associated element, where the <tt>toString</tt> method is used to 
419         * convert the key and element to strings. <p>Overrides to 
420         * <tt>toString</tt> method of <tt>Object</tt>.
421         *
422         * @return  a string representation of this hashtable.
423         */
424        public String toString() {
425        int max = size() - 1;
426        StringBuffer buf = new StringBuffer();
427        Iterator it = entrySet().iterator();
428    
429        buf.append("{");
430        for (int i = 0; i <= max; i++) {
431            Map.Entry e = (Map.Entry) (it.next());
432                Object key = e.getKey();
433                Object value = e.getValue();
434                buf.append((key   == this ? "(this Map)" : key) + "=" + 
435                           (value == this ? "(this Map)" : value));
436    
437            if (i < max)
438            buf.append(", ");
439        }
440        buf.append("}");
441        return buf.toString();
442        }
443    
444    
445        private Enumeration getEnumeration(int type) {
446            if (count == 0) {
447                return emptyEnumerator;
448            } 
449            return new Enumerator(type, false);
450            
451        }
452    
453        private Iterator getIterator(int type) {
454            if (count == 0) {
455                return emptyIterator;
456            } 
457            return new Enumerator(type, true);
458        }
459    
460        // Views
461    
462        /**
463         * Each of these fields are initialized to contain an instance of the
464         * appropriate view the first time this view is requested.  The views are
465         * stateless, so there's no reason to create more than one of each.
466         */
467        private transient volatile Set keySet = null;
468        private transient volatile Set entrySet = null;
469        private transient volatile Collection values = null;
470    
471        /**
472         * Returns a Set view of the keys contained in this Hashtable.  The Set
473         * is backed by the Hashtable, so changes to the Hashtable are reflected
474         * in the Set, and vice-versa.  The Set supports element removal
475         * (which removes the corresponding entry from the Hashtable), but not
476         * element addition.
477         *
478         * @return a set view of the keys contained in this map.
479    *
480         */
481        public Set keySet() {
482        if (keySet == null)
483            keySet = Collections.synchronizedSet(new KeySet(), this);
484        return keySet;
485        }
486    
487        private class KeySet extends AbstractSet {
488            @Override
489            public Iterator iterator() {
490            return getIterator(KEYS);
491            }
492            @Override
493            public int size() {
494                return count;
495            }
496            @Override
497            public boolean contains(Object o) {
498                return containsKey(o);
499            }
500            @Override
501            public boolean remove(Object o) {
502                return HashTableNotSync.this.remove(o) != null;
503            }
504            @Override
505            public void clear() {
506                HashTableNotSync.this.clear();
507            }
508        }
509    
510        @Override
511        public Set entrySet() {
512        if (entrySet==null)
513            entrySet = Collections.synchronizedSet(new EntrySet(), this);
514        return entrySet;
515        }
516    
517        private class EntrySet extends AbstractSet {
518            @Override
519            public Iterator iterator() {
520            return getIterator(ENTRIES);
521            }
522    
523            @Override
524            public boolean contains(Object o) {
525                if (!(o instanceof Map.Entry))
526                    return false;
527                Map.Entry entry = (Map.Entry)o;
528                Object key = entry.getKey();
529                Entry tab[] = table;
530                int hash = key.hashCode();
531                int index = (hash & 0x7FFFFFFF) % tab.length;
532    
533                for (Entry e = tab[index]; e != null; e = e.next)
534                    if (e.hash==hash && e.equals(entry))
535                        return true;
536                return false;
537            }
538    
539            @Override
540            public boolean remove(Object o) {
541                if (!(o instanceof Map.Entry))
542                    return false;
543                Map.Entry entry = (Map.Entry)o;
544                Object key = entry.getKey();
545                Entry tab[] = table;
546                int hash = key.hashCode();
547                int index = (hash & 0x7FFFFFFF) % tab.length;
548    
549                for (Entry e = tab[index], prev = null; e != null;
550                     prev = e, e = e.next) {
551                    if (e.hash==hash && e.equals(entry)) {
552                        modCount++;
553                        if (prev != null)
554                            prev.next = e.next;
555                        else
556                            tab[index] = e.next;
557    
558                        count--;
559                        e.value = null;
560                        return true;
561                    }
562                }
563                return false;
564            }
565    
566            @Override
567            public int size() {
568                return count;
569            }
570    
571            @Override
572            public void clear() {
573                HashTableNotSync.this.clear();
574            }
575        }
576    
577        /**
578         * Returns a Collection view of the values contained in this Hashtable.
579         * The Collection is backed by the Hashtable, so changes to the Hashtable
580         * are reflected in the Collection, and vice-versa.  The Collection
581         * supports element removal (which removes the corresponding entry from
582         * the Hashtable), but not element addition.
583         *
584         * @return a collection view of the values contained in this map.
585    *
586         */
587        public Collection values() {
588        if (values==null)
589            values = Collections.synchronizedCollection(new ValueCollection(),
590                                                            this);
591            return values;
592        }
593    
594        private class ValueCollection extends AbstractCollection {
595            @Override
596            public Iterator iterator() {
597            return getIterator(VALUES);
598            }
599            @Override
600            public int size() {
601                return count;
602            }
603            @Override
604            public boolean contains(Object o) {
605                return containsValue(o);
606            }
607            @Override
608            public void clear() {
609                HashTableNotSync.this.clear();
610            }
611        }
612    
613        // Comparison and hashing
614    
615        @Override
616        public boolean equals(Object o) {
617        if (o == this)
618            return true;
619    
620        if (!(o instanceof Map))
621            return false;
622        Map t = (Map) o;
623        if (t.size() != size())
624            return false;
625    
626            try {
627                Iterator i = entrySet().iterator();
628                while (i.hasNext()) {
629                    Map.Entry e = (Map.Entry) i.next();
630                    Object key = e.getKey();
631                    Object value = e.getValue();
632                    if (value == null) {
633                        if (!(t.get(key)==null && t.containsKey(key)))
634                            return false;
635                    } else {
636                        if (!value.equals(t.get(key)))
637                            return false;
638                    }
639                }
640            } catch(ClassCastException unused)   {
641                return false;
642            } catch(NullPointerException unused) {
643                return false;
644            }
645    
646        return true;
647        }
648    
649        @Override
650        public int hashCode() {
651            /*
652             * This code detects the recursion caused by computing the hash code
653             * of a self-referential hash table and prevents the stack overflow
654             * that would otherwise result.  This allows certain 1.1-era
655             * applets with self-referential hash tables to work.  This code
656             * abuses the loadFactor field to do double-duty as a hashCode
657             * in progress flag, so as not to worsen the space performance.
658             * A negative load factor indicates that hash code computation is
659             * in progress.
660             */
661            int h = 0;
662            if (count == 0 || loadFactor < 0)
663                return h;  // Returns zero
664    
665            loadFactor = -loadFactor;  // Mark hashCode computation in progress
666            Entry tab[] = table;
667            for (int i = 0; i < tab.length; i++)
668                for (Entry e = tab[i]; e != null; e = e.next)
669                    h += e.key.hashCode() ^ e.value.hashCode();
670            loadFactor = -loadFactor;  // Mark hashCode computation complete
671    
672        return h;
673        }
674    
675        /**
676         * Save the state of the Hashtable to a stream (i.e., serialize it).
677         * @param s
678         * @throws IOException
679         *
680         * @serialData The <i>capacity</i> of the Hashtable (the length of the
681         *         bucket array) is emitted (int), followed  by the
682         *         <i>size</i> of the Hashtable (the number of key-value
683         *         mappings), followed by the key (Object) and value (Object)
684         *         for each key-value mapping represented by the Hashtable
685         *         The key-value mappings are emitted in no particular order.
686         */
687        private void writeObject(java.io.ObjectOutputStream s)
688            throws IOException
689        {
690        // Write out the length, threshold, loadfactor
691        s.defaultWriteObject();
692    
693        // Write out length, count of elements and then the key/value objects
694        s.writeInt(table.length);
695        s.writeInt(count);
696        for (int index = table.length-1; index >= 0; index--) {
697            Entry entry = table[index];
698    
699            while (entry != null) {
700            s.writeObject(entry.key);
701            s.writeObject(entry.value);
702            entry = entry.next;
703            }
704        }
705        }
706    
707        /**
708         * Reconstitute the Hashtable from a stream (i.e., deserialize it).
709         * @param s
710         * @throws IOException
711         * @throws ClassNotFoundException
712         */
713        private void readObject(java.io.ObjectInputStream s)
714             throws IOException, ClassNotFoundException
715        {
716        // Read in the length, threshold, and loadfactor
717        s.defaultReadObject();
718    
719        // Read the original length of the array and number of elements
720        int origlength = s.readInt();
721        int elements = s.readInt();
722    
723        // Compute new size with a bit of room 5% to grow but
724        // No larger than the original size.  Make the length
725        // odd if it's large enough, this helps distribute the entries.
726        // Guard against the length ending up zero, that's not valid.
727        int length = (int)(elements * loadFactor) + (elements / 20) + 3;
728        if (length > elements && (length & 1) == 0)
729            length--;
730        if (origlength > 0 && length > origlength)
731            length = origlength;
732    
733        table = new Entry[length];
734        count = 0;
735    
736        // Read the number of elements and then all the key/value objects
737        for (; elements > 0; elements--) {
738            Object key = s.readObject();
739            Object value = s.readObject();
740            put(key, value);
741        }
742        }
743    
744    
745        /**
746         * Hashtable collision list.
747         */
748        private static class Entry implements Map.Entry {
749        int hash;
750        Object key;
751        Object value;
752        Entry next;
753    
754        /**
755         * @param hash
756         * @param key
757         * @param value
758         * @param next
759         */
760        protected Entry(int hash, Object key, Object value, Entry next) {
761            this.hash = hash;
762            this.key = key;
763            this.value = value;
764            this.next = next;
765        }
766    
767        @Override
768        protected Object clone() {
769            return new Entry(hash, key, value,
770                     (next==null ? null : (Entry)next.clone()));
771        }
772    
773        // Map.Entry Ops 
774    
775        @Override
776        public Object getKey() {
777            return key;
778        }
779    
780        @Override
781        public Object getValue() {
782            return value;
783        }
784    
785        @Override
786        public Object setValue(Object value) {
787            if (value == null)
788            throw new NullPointerException();
789    
790            Object oldValue = this.value;
791            this.value = value;
792            return oldValue;
793        }
794    
795        @Override
796        public boolean equals(Object o) {
797            if (!(o instanceof Map.Entry))
798            return false;
799            Map.Entry e = (Map.Entry)o;
800    
801            return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
802               (value==null ? e.getValue()==null : value.equals(e.getValue()));
803        }
804    
805        @Override
806        public int hashCode() {
807            return hash ^ (value==null ? 0 : value.hashCode());
808        }
809    
810        @Override
811        public String toString() {
812            return key.toString()+"="+value.toString();
813        }
814        }
815    
816        // Types of Enumerations/Iterations
817        private static final int KEYS = 0;
818        private static final int VALUES = 1;
819        private static final int ENTRIES = 2;
820    
821        /**
822         * A hashtable enumerator class.  This class implements both the
823         * Enumeration and Iterator interfaces, but individual instances
824         * can be created with the Iterator methods disabled.  This is necessary
825         * to avoid unintentionally increasing the capabilities granted a user
826         * by passing an Enumeration.
827         */
828        private class Enumerator implements Enumeration, Iterator {
829        Entry[] table = HashTableNotSync.this.table;
830        int index = table.length;
831        Entry entry = null;
832        Entry lastReturned = null;
833        int type;
834    
835        /**
836         * Indicates whether this Enumerator is serving as an Iterator
837         * or an Enumeration.  (true -> Iterator).
838         */
839        boolean iterator;
840    
841        /**
842         * The modCount value that the iterator believes that the backing
843         * List should have.  If this expectation is violated, the iterator
844         * has detected concurrent modification.
845         */
846        protected int expectedModCount = modCount;
847    
848        Enumerator(int type, boolean iterator) {
849            this.type = type;
850            this.iterator = iterator;
851        }
852    
853        @Override
854        public boolean hasMoreElements() {
855            Entry e = entry;
856            int i = index;
857            Entry t[] = table;
858            /* Use locals for faster loop iteration */
859            while (e == null && i > 0) { 
860            e = t[--i];
861            }
862            entry = e;
863            index = i;
864            return e != null;
865        }
866    
867        @Override
868        public Object nextElement() {
869            Entry et = entry;
870            int i = index;
871            Entry t[] = table;
872            /* Use locals for faster loop iteration */
873            while (et == null && i > 0) { 
874            et = t[--i];
875            }
876            entry = et;
877            index = i;
878            if (et != null) {
879            Entry e = lastReturned = entry;
880            entry = e.next;
881            return type == KEYS ? e.key : (type == VALUES ? e.value : e);
882            }
883            throw new NoSuchElementException("Hashtable Enumerator");
884        }
885    
886        @Override
887        // Iterator methods
888        public boolean hasNext() {
889            return hasMoreElements();
890        }
891    
892        @Override
893        public Object next() {
894            if (modCount != expectedModCount)
895            throw new ConcurrentModificationException();
896            return nextElement();
897        }
898    
899        @Override
900        public void remove() {
901            if (!iterator)
902            throw new UnsupportedOperationException();
903            if (lastReturned == null)
904            throw new IllegalStateException("Hashtable Enumerator");
905            if (modCount != expectedModCount)
906            throw new ConcurrentModificationException();
907    
908            synchronized(HashTableNotSync.this) {
909            Entry[] tab = HashTableNotSync.this.table;
910            int index = (lastReturned.hash & 0x7FFFFFFF) % tab.length;
911    
912            for (Entry e = tab[index], prev = null; e != null;
913                 prev = e, e = e.next) {
914                if (e == lastReturned) {
915                modCount++;
916                expectedModCount++;
917                if (prev == null)
918                    tab[index] = e.next;
919                else
920                    prev.next = e.next;
921                count--;
922                lastReturned = null;
923                return;
924                }
925            }
926            throw new ConcurrentModificationException();
927            }
928        }
929        }
930    
931       
932        private static EmptyEnumerator emptyEnumerator = new EmptyEnumerator();
933        private static EmptyIterator emptyIterator = new EmptyIterator();
934    
935        /**
936         * A hashtable enumerator class for empty hash tables, specializes
937         * the general Enumerator
938         */
939        private static class EmptyEnumerator implements Enumeration {
940    
941        EmptyEnumerator() {
942        }
943    
944        @Override
945        public boolean hasMoreElements() {
946            return false;
947        }
948    
949        @Override
950        public Object nextElement() {
951            throw new NoSuchElementException("Hashtable Enumerator");
952        }
953        }
954    
955    
956        /**
957         * A hashtable iterator class for empty hash tables
958         */
959        private static class EmptyIterator implements Iterator {
960    
961        EmptyIterator() {
962        }
963    
964        @Override
965        public boolean hasNext() {
966            return false;
967        }
968    
969        @Override
970        public Object next() {
971            throw new NoSuchElementException("Hashtable Iterator");
972        }
973    
974        @Override
975        public void remove() {
976            throw new IllegalStateException("Hashtable Iterator");
977        }
978    
979        }
980    
981    }