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