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