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