001    /*
002     * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
003     * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
004     *
005     *
006     *
007     *
008     *
009     *
010     *
011     *
012     *
013     *
014     *
015     *
016     *
017     *
018     *
019     *
020     *
021     *
022     *
023     *
024     */
025    
026    package railo.commons.util.mod;
027    import java.io.IOException;
028    import java.io.InvalidObjectException;
029    import java.io.Serializable;
030    import java.util.Collection;
031    import java.util.ConcurrentModificationException;
032    import java.util.HashMap;
033    import java.util.Iterator;
034    import java.util.Map;
035    import java.util.NoSuchElementException;
036    import java.util.Set;
037    
038    import railo.runtime.exp.PageException;
039    
040    public class HashMapPro<K,V>
041        extends AbstractMapPro<K,V>
042        implements Map<K,V>, MapPro<K,V>, Cloneable, Serializable
043    {
044    
045        /**
046         * The default initial capacity - MUST be a power of two.
047         */
048        static final int DEFAULT_INITIAL_CAPACITY = 16;
049    
050        /**
051         * The maximum capacity, used if a higher value is implicitly specified
052         * by either of the constructors with arguments.
053         * MUST be a power of two <= 1<<30.
054         */
055        static final int MAXIMUM_CAPACITY = 1 << 30;
056    
057        /**
058         * The load factor used when none specified in constructor.
059         */
060        static final float DEFAULT_LOAD_FACTOR = 0.75f;
061    
062        /**
063         * The table, resized as necessary. Length MUST Always be a power of two.
064         */
065        transient Entry<K,V>[] table;
066    
067        /**
068         * The number of key-value mappings contained in this map.
069         */
070        transient int size;
071    
072        /**
073         * The next size value at which to resize (capacity * load factor).
074         * @serial
075         */
076        int threshold;
077    
078        /**
079         * The load factor for the hash table.
080         *
081         * @serial
082         */
083        final float loadFactor;
084    
085        /**
086         * The number of times this HashMap has been structurally modified
087         * Structural modifications are those that change the number of mappings in
088         * the HashMap or otherwise modify its internal structure (e.g.,
089         * rehash).  This field is used to make iterators on Collection-views of
090         * the HashMap fail-fast.  (See ConcurrentModificationException).
091         */
092        transient int modCount;
093    
094        /**
095         * The default threshold of map capacity above which alternative hashing is
096         * used for String keys. Alternative hashing reduces the incidence of
097         * collisions due to weak hash code calculation for String keys.
098         * <p/>
099         * This value may be overridden by defining the system property
100         * {@code jdk.map.althashing.threshold}. A property value of {@code 1}
101         * forces alternative hashing to be used at all times whereas
102         * {@code -1} value ensures that alternative hashing is never used.
103         */
104        static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
105    
106        /**
107         * holds values which can't be initialized until after VM is booted.
108         */
109        private static class Holder {
110    
111                // Unsafe mechanics
112            /**
113             * Unsafe utilities
114             */
115            static final sun.misc.Unsafe UNSAFE;
116    
117            /**
118             * Offset of "final" hashSeed field we must set in readObject() method.
119             */
120            static final long HASHSEED_OFFSET;
121    
122            /**
123             * Table capacity above which to switch to use alternative hashing.
124             */
125            static final int ALTERNATIVE_HASHING_THRESHOLD;
126    
127            static {
128                String altThreshold = java.security.AccessController.doPrivileged(
129                    new sun.security.action.GetPropertyAction(
130                        "jdk.map.althashing.threshold"));
131    
132                int threshold;
133                try {
134                    threshold = (null != altThreshold)
135                            ? Integer.parseInt(altThreshold)
136                            : ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
137    
138                    // disable alternative hashing if -1
139                    if (threshold == -1) {
140                        threshold = Integer.MAX_VALUE;
141                    }
142    
143                    if (threshold < 0) {
144                        throw new IllegalArgumentException("value must be positive integer.");
145                    }
146                } catch(IllegalArgumentException failed) {
147                    throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
148                }
149                ALTERNATIVE_HASHING_THRESHOLD = threshold;
150    
151                try {
152                    UNSAFE = sun.misc.Unsafe.getUnsafe();
153                    HASHSEED_OFFSET = UNSAFE.objectFieldOffset(
154                        HashMapPro.class.getDeclaredField("hashSeed"));
155                } 
156                catch (NoSuchFieldException e) {
157                    throw new Error("Failed to record hashSeed offset", e);
158                }
159                catch (SecurityException e) {
160                    throw new Error("Failed to record hashSeed offset", e);
161                }
162            }
163        }
164    
165        /**
166         * If {@code true} then perform alternative hashing of String keys to reduce
167         * the incidence of collisions due to weak hash code calculation.
168         */
169        transient final boolean useAltHashing=false;
170    
171        /**
172         * A randomizing value associated with this instance that is applied to
173         * hash code of keys to make hash collisions harder to find.
174         */
175        transient final int hashSeed = Hashing.randomHashSeed(this);
176    
177        /**
178         * Constructs an empty <tt>HashMap</tt> with the specified initial
179         * capacity and load factor.
180         *
181         * @param  initialCapacity the initial capacity
182         * @param  loadFactor      the load factor
183         * @throws IllegalArgumentException if the initial capacity is negative
184         *         or the load factor is nonpositive
185         */
186        public HashMapPro(int initialCapacity, float loadFactor) {
187            if (initialCapacity < 0)
188                throw new IllegalArgumentException("Illegal initial capacity: " +
189                                                   initialCapacity);
190            if (initialCapacity > MAXIMUM_CAPACITY)
191                initialCapacity = MAXIMUM_CAPACITY;
192            if (loadFactor <= 0 || Float.isNaN(loadFactor))
193                throw new IllegalArgumentException("Illegal load factor: " +
194                                                   loadFactor);
195    
196            // Find a power of 2 >= initialCapacity
197            int capacity = 1;
198            while (capacity < initialCapacity)
199                capacity <<= 1;
200    
201            this.loadFactor = loadFactor;
202            threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
203            table = new Entry[capacity];
204            //useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
205            init();
206        }
207    
208        /**
209         * Constructs an empty <tt>HashMap</tt> with the specified initial
210         * capacity and the default load factor (0.75).
211         *
212         * @param  initialCapacity the initial capacity.
213         * @throws IllegalArgumentException if the initial capacity is negative.
214         */
215        public HashMapPro(int initialCapacity) {
216            this(initialCapacity, DEFAULT_LOAD_FACTOR);
217        }
218    
219        /**
220         * Constructs an empty <tt>HashMap</tt> with the default initial capacity
221         * (16) and the default load factor (0.75).
222         */
223        public HashMapPro() {
224            this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
225        }
226    
227        /**
228         * Constructs a new <tt>HashMap</tt> with the same mappings as the
229         * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with
230         * default load factor (0.75) and an initial capacity sufficient to
231         * hold the mappings in the specified <tt>Map</tt>.
232         *
233         * @param   m the map whose mappings are to be placed in this map
234         * @throws  NullPointerException if the specified map is null
235         */
236        public HashMapPro(Map<? extends K, ? extends V> m) {
237            this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
238                          DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
239            putAllForCreate(m);
240        }
241    
242        // internal utilities
243    
244        /**
245         * Initialization hook for subclasses. This method is called
246         * in all constructors and pseudo-constructors (clone, readObject)
247         * after HashMap has been initialized but before any entries have
248         * been inserted.  (In the absence of this method, readObject would
249         * require explicit knowledge of subclasses.)
250         */
251        void init() {
252        }
253    
254        /**
255         * Retrieve object hash code and applies a supplemental hash function to the
256         * result hash, which defends against poor quality hash functions.  This is
257         * critical because HashMap uses power-of-two length hash tables, that
258         * otherwise encounter collisions for hashCodes that do not differ
259         * in lower bits. Note: Null keys always map to hash 0, thus index 0.
260         */
261        final int hash(Object k) {
262            int h = 0;
263            /*if (useAltHashing) {
264                if (k instanceof String) {
265                    return Hashing.stringHash32((String) k);
266                }
267                h = hashSeed;
268            }*/
269    
270            h ^= k.hashCode();
271    
272            // This function ensures that hashCodes that differ only by
273            // constant multiples at each bit position have a bounded
274            // number of collisions (approximately 8 at default load factor).
275            h ^= (h >>> 20) ^ (h >>> 12);
276            return h ^ (h >>> 7) ^ (h >>> 4);
277        }
278    
279        /**
280         * Returns index for hash code h.
281         */
282        static int indexFor(int h, int length) {
283            return h & (length-1);
284        }
285    
286        /**
287         * Returns the number of key-value mappings in this map.
288         *
289         * @return the number of key-value mappings in this map
290         */
291        public int size() {
292            return size;
293        }
294    
295        /**
296         * Returns <tt>true</tt> if this map contains no key-value mappings.
297         *
298         * @return <tt>true</tt> if this map contains no key-value mappings
299         */
300        public boolean isEmpty() {
301            return size == 0;
302        }
303    
304        @Override
305        public V get(Object key) {
306            if (key == null)
307                return getForNullKey();
308            Entry<K,V> entry = getEntry(key);
309    
310            return null == entry ? null : entry.getValue();
311        }
312        
313        public V g(K key, V defaultValue) {
314            if (key == null) return getForNullKey();
315    
316            int hash = hash(key);
317            for (Entry<K,V> e = table[indexFor(hash, table.length)];
318                 e != null;
319                 e = e.next) {
320                Object k;
321                if (e.hash == hash &&
322                    ((k = e.key) == key || key.equals(k)))
323                    return e.getValue();
324            }
325            return defaultValue;
326        }
327        
328        public V g(K key) throws PageException {
329            if (key == null) return getForNullKey();
330    
331            int hash = hash(key);
332            for (Entry<K,V> e = table[indexFor(hash, table.length)];
333                 e != null;
334                 e = e.next) {
335                Object k;
336                if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
337                    return e.getValue();
338            }
339            throw invalidKey(this, key,false);
340        }
341    
342        /**
343         * Offloaded version of get() to look up null keys.  Null keys map
344         * to index 0.  This null case is split out into separate methods
345         * for the sake of performance in the two most commonly used
346         * operations (get and put), but incorporated with conditionals in
347         * others.
348         */
349        private V getForNullKey() {
350            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
351                if (e.key == null)
352                    return e.value;
353            }
354            return null;
355        }
356    
357        /**
358         * Returns <tt>true</tt> if this map contains a mapping for the
359         * specified key.
360         *
361         * @param   key   The key whose presence in this map is to be tested
362         * @return <tt>true</tt> if this map contains a mapping for the specified
363         * key.
364         */
365        public boolean containsKey(Object key) {
366            return getEntry(key) != null;
367        }
368    
369        /**
370         * Returns the entry associated with the specified key in the
371         * HashMap.  Returns null if the HashMap contains no mapping
372         * for the key.
373         */
374        final Entry<K,V> getEntry(Object key) {
375            int hash = (key == null) ? 0 : hash(key);
376            for (Entry<K,V> e = table[indexFor(hash, table.length)];
377                 e != null;
378                 e = e.next) {
379                Object k;
380                if (e.hash == hash &&
381                    ((k = e.key) == key || (key != null && key.equals(k))))
382                    return e;
383            }
384            return null;
385        }
386    
387    
388        /**
389         * Associates the specified value with the specified key in this map.
390         * If the map previously contained a mapping for the key, the old
391         * value is replaced.
392         *
393         * @param key key with which the specified value is to be associated
394         * @param value value to be associated with the specified key
395         * @return the previous value associated with <tt>key</tt>, or
396         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
397         *         (A <tt>null</tt> return can also indicate that the map
398         *         previously associated <tt>null</tt> with <tt>key</tt>.)
399         */
400        public V put(K key, V value) {
401            if (key == null)
402                return putForNullKey(value);
403            int hash = hash(key);
404            int i = indexFor(hash, table.length);
405            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
406                Object k;
407                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
408                    V oldValue = e.value;
409                    e.value = value;
410                    e.recordAccess(this);
411                    return oldValue;
412                }
413            }
414    
415            modCount++;
416            addEntry(hash, key, value, i);
417            return null;
418        }
419    
420        /**
421         * Offloaded version of put for null keys
422         */
423        private V putForNullKey(V value) {
424            for (Entry<K,V> e = table[0]; e != null; e = e.next) {
425                if (e.key == null) {
426                    V oldValue = e.value;
427                    e.value = value;
428                    e.recordAccess(this);
429                    return oldValue;
430                }
431            }
432            modCount++;
433            addEntry(0, null, value, 0);
434            return null;
435        }
436    
437        /**
438         * This method is used instead of put by constructors and
439         * pseudoconstructors (clone, readObject).  It does not resize the table,
440         * check for comodification, etc.  It calls createEntry rather than
441         * addEntry.
442         */
443        private void putForCreate(K key, V value) {
444            int hash = null == key ? 0 : hash(key);
445            int i = indexFor(hash, table.length);
446    
447            /**
448             * Look for preexisting entry for key.  This will never happen for
449             * clone or deserialize.  It will only happen for construction if the
450             * input Map is a sorted map whose ordering is inconsistent w/ equals.
451             */
452            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
453                Object k;
454                if (e.hash == hash &&
455                    ((k = e.key) == key || (key != null && key.equals(k)))) {
456                    e.value = value;
457                    return;
458                }
459            }
460    
461            createEntry(hash, key, value, i);
462        }
463    
464        private void putAllForCreate(Map<? extends K, ? extends V> m) {
465            for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
466                putForCreate(e.getKey(), e.getValue());
467        }
468    
469        /**
470         * Rehashes the contents of this map into a new array with a
471         * larger capacity.  This method is called automatically when the
472         * number of keys in this map reaches its threshold.
473         *
474         * If current capacity is MAXIMUM_CAPACITY, this method does not
475         * resize the map, but sets threshold to Integer.MAX_VALUE.
476         * This has the effect of preventing future calls.
477         *
478         * @param newCapacity the new capacity, MUST be a power of two;
479         *        must be greater than current capacity unless current
480         *        capacity is MAXIMUM_CAPACITY (in which case value
481         *        is irrelevant).
482         */
483        void resize(int newCapacity) {
484            Entry[] oldTable = table;
485            int oldCapacity = oldTable.length;
486            if (oldCapacity == MAXIMUM_CAPACITY) {
487                threshold = Integer.MAX_VALUE;
488                return;
489            }
490    
491            Entry[] newTable = new Entry[newCapacity];
492            boolean oldAltHashing = useAltHashing;
493            //useAltHashing |= sun.misc.VM.isBooted() && (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
494            boolean rehash = oldAltHashing ^ useAltHashing;
495            transfer(newTable, rehash);
496            table = newTable;
497            threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
498        }
499    
500        /**
501         * Transfers all entries from current table to newTable.
502         */
503        void transfer(Entry[] newTable, boolean rehash) {
504            int newCapacity = newTable.length;
505            for (Entry<K,V> e : table) {
506                while(null != e) {
507                    Entry<K,V> next = e.next;
508                    if (rehash) {
509                        e.hash = null == e.key ? 0 : hash(e.key);
510                    }
511                    int i = indexFor(e.hash, newCapacity);
512                    e.next = newTable[i];
513                    newTable[i] = e;
514                    e = next;
515                }
516            }
517        }
518    
519        /**
520         * Copies all of the mappings from the specified map to this map.
521         * These mappings will replace any mappings that this map had for
522         * any of the keys currently in the specified map.
523         *
524         * @param m mappings to be stored in this map
525         * @throws NullPointerException if the specified map is null
526         */
527        public void putAll(Map<? extends K, ? extends V> m) {
528            int numKeysToBeAdded = m.size();
529            if (numKeysToBeAdded == 0)
530                return;
531    
532            /*
533             * Expand the map if the map if the number of mappings to be added
534             * is greater than or equal to threshold.  This is conservative; the
535             * obvious condition is (m.size() + size) >= threshold, but this
536             * condition could result in a map with twice the appropriate capacity,
537             * if the keys to be added overlap with the keys already in this map.
538             * By using the conservative calculation, we subject ourself
539             * to at most one extra resize.
540             */
541            if (numKeysToBeAdded > threshold) {
542                int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
543                if (targetCapacity > MAXIMUM_CAPACITY)
544                    targetCapacity = MAXIMUM_CAPACITY;
545                int newCapacity = table.length;
546                while (newCapacity < targetCapacity)
547                    newCapacity <<= 1;
548                if (newCapacity > table.length)
549                    resize(newCapacity);
550            }
551    
552            for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
553                put(e.getKey(), e.getValue());
554        }
555    
556        /**
557         * Removes the mapping for the specified key from this map if present.
558         *
559         * @param  key key whose mapping is to be removed from the map
560         * @return the previous value associated with <tt>key</tt>, or
561         *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
562         *         (A <tt>null</tt> return can also indicate that the map
563         *         previously associated <tt>null</tt> with <tt>key</tt>.)
564         */
565        public V remove(Object key) {
566            Entry<K,V> e = removeEntryForKey(key);
567            return (e == null ? null : e.value);
568        }
569    
570        public V r(K key,V defaultValue) {
571            Entry<K,V> e = removeEntryForKey(key);
572            return (e == null ? defaultValue : e.value);
573        }
574        
575        public V r(K key) throws PageException {
576            Entry<K,V> e = removeEntryForKey(key);
577            if(e==null) throw invalidKey(this, key,true);
578            return e.value;
579        }
580    
581        
582        
583        
584        
585        /**
586         * Removes and returns the entry associated with the specified key
587         * in the HashMap.  Returns null if the HashMap contains no mapping
588         * for this key.
589         */
590        final Entry<K,V> removeEntryForKey(Object key) {
591            int hash = (key == null) ? 0 : hash(key);
592            int i = indexFor(hash, table.length);
593            Entry<K,V> prev = table[i];
594            Entry<K,V> e = prev;
595    
596            while (e != null) {
597                Entry<K,V> next = e.next;
598                Object k;
599                if (e.hash == hash &&
600                    ((k = e.key) == key || (key != null && key.equals(k)))) {
601                    modCount++;
602                    size--;
603                    if (prev == e)
604                        table[i] = next;
605                    else
606                        prev.next = next;
607                    e.recordRemoval(this);
608                    return e;
609                }
610                prev = e;
611                e = next;
612            }
613    
614            return e;
615        }
616    
617        /**
618         * Special version of remove for EntrySet using {@code Map.Entry.equals()}
619         * for matching.
620         */
621        final Entry<K,V> removeMapping(Object o) {
622            if (!(o instanceof Map.Entry))
623                return null;
624    
625            Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
626            Object key = entry.getKey();
627            int hash = (key == null) ? 0 : hash(key);
628            int i = indexFor(hash, table.length);
629            Entry<K,V> prev = table[i];
630            Entry<K,V> e = prev;
631    
632            while (e != null) {
633                Entry<K,V> next = e.next;
634                if (e.hash == hash && e.equals(entry)) {
635                    modCount++;
636                    size--;
637                    if (prev == e)
638                        table[i] = next;
639                    else
640                        prev.next = next;
641                    e.recordRemoval(this);
642                    return e;
643                }
644                prev = e;
645                e = next;
646            }
647    
648            return e;
649        }
650    
651        /**
652         * Removes all of the mappings from this map.
653         * The map will be empty after this call returns.
654         */
655        public void clear() {
656            modCount++;
657            Entry[] tab = table;
658            for (int i = 0; i < tab.length; i++)
659                tab[i] = null;
660            size = 0;
661        }
662    
663        /**
664         * Returns <tt>true</tt> if this map maps one or more keys to the
665         * specified value.
666         *
667         * @param value value whose presence in this map is to be tested
668         * @return <tt>true</tt> if this map maps one or more keys to the
669         *         specified value
670         */
671        public boolean containsValue(Object value) {
672            if (value == null)
673                return containsNullValue();
674    
675            Entry[] tab = table;
676            for (int i = 0; i < tab.length ; i++)
677                for (Entry e = tab[i] ; e != null ; e = e.next)
678                    if (value.equals(e.value))
679                        return true;
680            return false;
681        }
682    
683        /**
684         * Special-case code for containsValue with null argument
685         */
686        private boolean containsNullValue() {
687            Entry[] tab = table;
688            for (int i = 0; i < tab.length ; i++)
689                for (Entry e = tab[i] ; e != null ; e = e.next)
690                    if (e.value == null)
691                        return true;
692            return false;
693        }
694    
695        /**
696         * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
697         * values themselves are not cloned.
698         *
699         * @return a shallow copy of this map
700         */
701        public Object clone() {
702            HashMapPro<K,V> result = null;
703            try {
704                result = (HashMapPro<K,V>)super.clone();
705            } catch (CloneNotSupportedException e) {
706                // assert false;
707            }
708            result.table = new Entry[table.length];
709            result.entrySet = null;
710            result.modCount = 0;
711            result.size = 0;
712            result.init();
713            result.putAllForCreate(this);
714    
715            return result;
716        }
717    
718        static class Entry<K,V> implements Map.Entry<K,V> {
719            final K key;
720            V value;
721            Entry<K,V> next;
722            int hash;
723    
724            /**
725             * Creates new entry.
726             */
727            Entry(int h, K k, V v, Entry<K,V> n) {
728                value = v;
729                next = n;
730                key = k;
731                hash = h;
732            }
733    
734            public final K getKey() {
735                return key;
736            }
737    
738            public final V getValue() {
739                return value;
740            }
741    
742            public final V setValue(V newValue) {
743                V oldValue = value;
744                value = newValue;
745                return oldValue;
746            }
747    
748            public final boolean equals(Object o) {
749                if (!(o instanceof Map.Entry))
750                    return false;
751                Map.Entry e = (Map.Entry)o;
752                Object k1 = getKey();
753                Object k2 = e.getKey();
754                if (k1 == k2 || (k1 != null && k1.equals(k2))) {
755                    Object v1 = getValue();
756                    Object v2 = e.getValue();
757                    if (v1 == v2 || (v1 != null && v1.equals(v2)))
758                        return true;
759                }
760                return false;
761            }
762    
763            public final int hashCode() {
764                return (key==null   ? 0 : key.hashCode()) ^
765                       (value==null ? 0 : value.hashCode());
766            }
767    
768            public final String toString() {
769                return getKey() + "=" + getValue();
770            }
771    
772            /**
773             * This method is invoked whenever the value in an entry is
774             * overwritten by an invocation of put(k,v) for a key k that's already
775             * in the HashMap.
776             */
777            void recordAccess(HashMapPro<K,V> m) {
778            }
779    
780            /**
781             * This method is invoked whenever the entry is
782             * removed from the table.
783             */
784            void recordRemoval(HashMapPro<K,V> m) {
785            }
786        }
787    
788        /**
789         * Adds a new entry with the specified key, value and hash code to
790         * the specified bucket.  It is the responsibility of this
791         * method to resize the table if appropriate.
792         *
793         * Subclass overrides this to alter the behavior of put method.
794         */
795        void addEntry(int hash, K key, V value, int bucketIndex) {
796            if ((size >= threshold) && (null != table[bucketIndex])) {
797                resize(2 * table.length);
798                hash = (null != key) ? hash(key) : 0;
799                bucketIndex = indexFor(hash, table.length);
800            }
801    
802            createEntry(hash, key, value, bucketIndex);
803        }
804    
805        /**
806         * Like addEntry except that this version is used when creating entries
807         * as part of Map construction or "pseudo-construction" (cloning,
808         * deserialization).  This version needn't worry about resizing the table.
809         *
810         * Subclass overrides this to alter the behavior of HashMap(Map),
811         * clone, and readObject.
812         */
813        void createEntry(int hash, K key, V value, int bucketIndex) {
814            Entry<K,V> e = table[bucketIndex];
815            table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
816            size++;
817        }
818    
819        private abstract class HashIterator<E> implements Iterator<E> {
820            Entry<K,V> next;        // next entry to return
821            int expectedModCount;   // For fast-fail
822            int index;              // current slot
823            Entry<K,V> current;     // current entry
824    
825            HashIterator() {
826                expectedModCount = modCount;
827                if (size > 0) { // advance to first entry
828                    Entry[] t = table;
829                    while (index < t.length && (next = t[index++]) == null)
830                        ;
831                }
832            }
833    
834            public final boolean hasNext() {
835                return next != null;
836            }
837    
838            final Entry<K,V> nextEntry() {
839                if (modCount != expectedModCount)
840                    throw new ConcurrentModificationException();
841                Entry<K,V> e = next;
842                if (e == null)
843                    throw new NoSuchElementException();
844    
845                if ((next = e.next) == null) {
846                    Entry[] t = table;
847                    while (index < t.length && (next = t[index++]) == null)
848                        ;
849                }
850                current = e;
851                return e;
852            }
853    
854            public void remove() {
855                if (current == null)
856                    throw new IllegalStateException();
857                if (modCount != expectedModCount)
858                    throw new ConcurrentModificationException();
859                Object k = current.key;
860                current = null;
861                HashMapPro.this.removeEntryForKey(k);
862                expectedModCount = modCount;
863            }
864        }
865    
866        private final class ValueIterator extends HashIterator<V> {
867            public V next() {
868                return nextEntry().value;
869            }
870        }
871    
872        private final class KeyIterator extends HashIterator<K> {
873            public K next() {
874                return nextEntry().getKey();
875            }
876        }
877    
878        private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
879            public Map.Entry<K,V> next() {
880                return nextEntry();
881            }
882        }
883    
884        // Subclass overrides these to alter behavior of views' iterator() method
885        Iterator<K> newKeyIterator()   {
886            return new KeyIterator();
887        }
888        Iterator<V> newValueIterator()   {
889            return new ValueIterator();
890        }
891        Iterator<Map.Entry<K,V>> newEntryIterator()   {
892            return new EntryIterator();
893        }
894    
895    
896        // Views
897    
898        private transient Set<Map.Entry<K,V>> entrySet = null;
899    
900        /**
901         * Returns a {@link Set} view of the keys contained in this map.
902         * The set is backed by the map, so changes to the map are
903         * reflected in the set, and vice-versa.  If the map is modified
904         * while an iteration over the set is in progress (except through
905         * the iterator's own <tt>remove</tt> operation), the results of
906         * the iteration are undefined.  The set supports element removal,
907         * which removes the corresponding mapping from the map, via the
908         * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>,
909         * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt>
910         * operations.  It does not support the <tt>add</tt> or <tt>addAll</tt>
911         * operations.
912         */
913        public Set<K> keySet() {
914            Set<K> ks = keySet;
915            return (ks != null ? ks : (keySet = new KeySet()));
916        }
917    
918        private final class KeySet extends AbstractSet<K> {
919            public Iterator<K> iterator() {
920                return newKeyIterator();
921            }
922            public int size() {
923                return size;
924            }
925            public boolean contains(Object o) {
926                return containsKey(o);
927            }
928            public boolean remove(Object o) {
929                return HashMapPro.this.removeEntryForKey(o) != null;
930            }
931            public void clear() {
932                HashMapPro.this.clear();
933            }
934        }
935    
936        /**
937         * Returns a {@link Collection} view of the values contained in this map.
938         * The collection is backed by the map, so changes to the map are
939         * reflected in the collection, and vice-versa.  If the map is
940         * modified while an iteration over the collection is in progress
941         * (except through the iterator's own <tt>remove</tt> operation),
942         * the results of the iteration are undefined.  The collection
943         * supports element removal, which removes the corresponding
944         * mapping from the map, via the <tt>Iterator.remove</tt>,
945         * <tt>Collection.remove</tt>, <tt>removeAll</tt>,
946         * <tt>retainAll</tt> and <tt>clear</tt> operations.  It does not
947         * support the <tt>add</tt> or <tt>addAll</tt> operations.
948         */
949        public Collection<V> values() {
950            Collection<V> vs = values;
951            return (vs != null ? vs : (values = new Values()));
952        }
953    
954        private final class Values extends AbstractCollection<V> {
955            public Iterator<V> iterator() {
956                return newValueIterator();
957            }
958            public int size() {
959                return size;
960            }
961            public boolean contains(Object o) {
962                return containsValue(o);
963            }
964            public void clear() {
965                HashMapPro.this.clear();
966            }
967        }
968    
969        /**
970         * Returns a {@link Set} view of the mappings contained in this map.
971         * The set is backed by the map, so changes to the map are
972         * reflected in the set, and vice-versa.  If the map is modified
973         * while an iteration over the set is in progress (except through
974         * the iterator's own <tt>remove</tt> operation, or through the
975         * <tt>setValue</tt> operation on a map entry returned by the
976         * iterator) the results of the iteration are undefined.  The set
977         * supports element removal, which removes the corresponding
978         * mapping from the map, via the <tt>Iterator.remove</tt>,
979         * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
980         * <tt>clear</tt> operations.  It does not support the
981         * <tt>add</tt> or <tt>addAll</tt> operations.
982         *
983         * @return a set view of the mappings contained in this map
984         */
985        public Set<Map.Entry<K,V>> entrySet() {
986            return entrySet0();
987        }
988    
989        private Set<Map.Entry<K,V>> entrySet0() {
990            Set<Map.Entry<K,V>> es = entrySet;
991            return es != null ? es : (entrySet = new EntrySet());
992        }
993    
994        private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
995            public Iterator<Map.Entry<K,V>> iterator() {
996                return newEntryIterator();
997            }
998            public boolean contains(Object o) {
999                if (!(o instanceof Map.Entry))
1000                    return false;
1001                Map.Entry<K,V> e = (Map.Entry<K,V>) o;
1002                Entry<K,V> candidate = getEntry(e.getKey());
1003                return candidate != null && candidate.equals(e);
1004            }
1005            public boolean remove(Object o) {
1006                return removeMapping(o) != null;
1007            }
1008            public int size() {
1009                return size;
1010            }
1011            public void clear() {
1012                HashMapPro.this.clear();
1013            }
1014        }
1015    
1016        /**
1017         * Save the state of the <tt>HashMap</tt> instance to a stream (i.e.,
1018         * serialize it).
1019         *
1020         * @serialData The <i>capacity</i> of the HashMap (the length of the
1021         *             bucket array) is emitted (int), followed by the
1022         *             <i>size</i> (an int, the number of key-value
1023         *             mappings), followed by the key (Object) and value (Object)
1024         *             for each key-value mapping.  The key-value mappings are
1025         *             emitted in no particular order.
1026         */
1027        private void writeObject(java.io.ObjectOutputStream s)
1028            throws IOException
1029        {
1030            Iterator<Map.Entry<K,V>> i =
1031                (size > 0) ? entrySet0().iterator() : null;
1032    
1033            // Write out the threshold, loadfactor, and any hidden stuff
1034            s.defaultWriteObject();
1035    
1036            // Write out number of buckets
1037            s.writeInt(table.length);
1038    
1039            // Write out size (number of Mappings)
1040            s.writeInt(size);
1041    
1042            // Write out keys and values (alternating)
1043            if (size > 0) {
1044                for(Map.Entry<K,V> e : entrySet0()) {
1045                    s.writeObject(e.getKey());
1046                    s.writeObject(e.getValue());
1047                }
1048            }
1049        }
1050    
1051        private static final long serialVersionUID = 362498820763181265L;
1052    
1053        /**
1054         * Reconstitute the {@code HashMap} instance from a stream (i.e.,
1055         * deserialize it).
1056         */
1057        private void readObject(java.io.ObjectInputStream s)
1058             throws IOException, ClassNotFoundException
1059        {
1060            // Read in the threshold (ignored), loadfactor, and any hidden stuff
1061            s.defaultReadObject();
1062            if (loadFactor <= 0 || Float.isNaN(loadFactor))
1063                throw new InvalidObjectException("Illegal load factor: " +
1064                                                   loadFactor);
1065    
1066            // set hashSeed (can only happen after VM boot)
1067            Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
1068                    Hashing.randomHashSeed(this));
1069    
1070            // Read in number of buckets and allocate the bucket array;
1071            s.readInt(); // ignored
1072    
1073            // Read number of mappings
1074            int mappings = s.readInt();
1075            if (mappings < 0)
1076                throw new InvalidObjectException("Illegal mappings count: " +
1077                                                   mappings);
1078    
1079            int initialCapacity = (int) Math.min(
1080                    // capacity chosen by number of mappings
1081                    // and desired load (if >= 0.25)
1082                    mappings * Math.min(1 / loadFactor, 4.0f),
1083                    // we have limits...
1084                    HashMapPro.MAXIMUM_CAPACITY);
1085            int capacity = 1;
1086            // find smallest power of two which holds all mappings
1087            while (capacity < initialCapacity) {
1088                capacity <<= 1;
1089            }
1090    
1091            table = new Entry[capacity];
1092            threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
1093            //useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
1094    
1095            init();  // Give subclass a chance to do its thing.
1096    
1097            // Read the keys and values, and put the mappings in the HashMap
1098            for (int i=0; i<mappings; i++) {
1099                K key = (K) s.readObject();
1100                V value = (V) s.readObject();
1101                putForCreate(key, value);
1102            }
1103        }
1104    
1105        // These methods are used when serializing HashSets
1106        int   capacity()     { return table.length; }
1107        float loadFactor()   { return loadFactor;   }
1108        
1109        
1110    
1111    }