/*

 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.util;

import java.io.*;

import java.lang.reflect.ParameterizedType;

import java.lang.reflect.Type;

import java.util.function.Consumer;

import java.util.function.BiFunction;

import java.util.function.Function;

/**

 * Hash table based implementation of the <tt>Map</tt> interface.  This

 * implementation provides all of the optional map operations, and permits

 * <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>

 * class is roughly equivalent to <tt>Hashtable</tt>, except that it is

 * unsynchronized and permits nulls.)  This class makes no guarantees as to

 * the order of the map; in particular, it does not guarantee that the order

 * will remain constant over time.

 *

 * <p>This implementation provides constant-time performance for the basic

 * operations (<tt>get</tt> and <tt>put</tt>), assuming the hash function

 * disperses the elements properly among the buckets.  Iteration over

 * collection views requires time proportional to the "capacity" of the

 * <tt>HashMap</tt> instance (the number of buckets) plus its size (the number

 * of key-value mappings).  Thus, it's very important not to set the initial

 * capacity too high (or the load factor too low) if iteration performance is

 * important.

 *

 * <p>An instance of <tt>HashMap</tt> has two parameters that affect its

 * performance: <i>initial capacity</i> and <i>load factor</i>.  The

 * <i>capacity</i> is the number of buckets in the hash table, and the initial

 * capacity is simply the capacity at the time the hash table is created.  The

 * <i>load factor</i> is a measure of how full the hash table is allowed to

 * get before its capacity is automatically increased.  When the number of

 * entries in the hash table exceeds the product of the load factor and the

 * current capacity, the hash table is <i>rehashed</i> (that is, internal data

 * structures are rebuilt) so that the hash table has approximately twice the

 * number of buckets.

 *

 * <p>As a general rule, the default load factor (.75) offers a good tradeoff

 * between time and space costs.  Higher values decrease the space overhead

 * but increase the lookup cost (reflected in most of the operations of the

 * <tt>HashMap</tt> class, including <tt>get</tt> and <tt>put</tt>).  The

 * expected number of entries in the map and its load factor should be taken

 * into account when setting its initial capacity, so as to minimize the

 * number of rehash operations.  If the initial capacity is greater

 * than the maximum number of entries divided by the load factor, no

 * rehash operations will ever occur.

 *

 * <p>If many mappings are to be stored in a <tt>HashMap</tt> instance,

 * creating it with a sufficiently large capacity will allow the mappings to

 * be stored more efficiently than letting it perform automatic rehashing as

 * needed to grow the table.

 *

 * <p><strong>Note that this implementation is not synchronized.</strong>

 * If multiple threads access a hash map concurrently, and at least one of

 * the threads modifies the map structurally, it <i>must</i> be

 * synchronized externally.  (A structural modification is any operation

 * that adds or deletes one or more mappings; merely changing the value

 * associated with a key that an instance already contains is not a

 * structural modification.)  This is typically accomplished by

 * synchronizing on some object that naturally encapsulates the map.

 *

 * If no such object exists, the map should be "wrapped" using the

 * {@link Collections#synchronizedMap Collections.synchronizedMap}

 * method.  This is best done at creation time, to prevent accidental

 * unsynchronized access to the map:<pre>

 *   Map m = Collections.synchronizedMap(new HashMap(...));</pre>

 *

 * <p>The iterators returned by all of this class's "collection view methods"

 * are <i>fail-fast</i>: if the map is structurally modified at any time after

 * the iterator is created, in any way except through the iterator's own

 * <tt>remove</tt> method, the iterator will throw a

 * {@link ConcurrentModificationException}.  Thus, in the face of concurrent

 * modification, the iterator fails quickly and cleanly, rather than risking

 * arbitrary, non-deterministic behavior at an undetermined time in the

 * future.

 *

 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed

 * as it is, generally speaking, impossible to make any hard guarantees in the

 * presence of unsynchronized concurrent modification.  Fail-fast iterators

 * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.

 * Therefore, it would be wrong to write a program that depended on this

 * exception for its correctness: <i>the fail-fast behavior of iterators

 * should be used only to detect bugs.</i>

 *

 * <p>This class is a member of the

 * <a href="{@docRoot}/../technotes/guides/collections/index.html">

 * Java Collections Framework</a>.

 *

 * @param <K> the type of keys maintained by this map

 * @param <V> the type of mapped values

 *

 * @author  Doug Lea

 * @author  Josh Bloch

 * @author  Arthur van Hoff

 * @author  Neal Gafter

 * @see     Object#hashCode()

 * @see     Collection

 * @see     Map

 * @see     TreeMap

 * @see     Hashtable

 * @since   1.2

 */

public class HashMap<K,V>

        extends AbstractMap<K,V>

    implements Map<K,V>, Cloneable, Serializable

{

    /**

     * The default initial capacity - MUST be a power of two.

     */

    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**

     * The maximum capacity, used if a higher value is implicitly specified

     * by either of the constructors with arguments.

     * MUST be a power of two <= 1<<30.

     */

    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**

     * The load factor used when none specified in constructor.

     */

    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**

     * An empty table instance to share when the table is not inflated.

     */

    static final Object[] EMPTY_TABLE = {};

    /**

     * The table, resized as necessary. Length MUST Always be a power of two.

     */

    transient Object[] table = EMPTY_TABLE;

    /**

     * The number of key-value mappings contained in this map.

     */

    transient int size;

    /**

     * The next size value at which to resize (capacity * load factor).

     * @serial

     */

    // If table == EMPTY_TABLE then this is the initial capacity at which the

    // table will be created when inflated.

    int threshold;

    /**

     * The load factor for the hash table.

     *

     * @serial

     */

    final float loadFactor;

    /**

     * The number of times this HashMap has been structurally modified

     * Structural modifications are those that change the number of mappings in

     * the HashMap or otherwise modify its internal structure (e.g.,

     * rehash).  This field is used to make iterators on Collection-views of

     * the HashMap fail-fast.  (See ConcurrentModificationException).

     */

    transient int modCount;

    /**

     * Holds values which can't be initialized until after VM is booted.

     */

    private static class Holder {

        static final sun.misc.Unsafe UNSAFE;

        /**

         * Offset of "final" hashSeed field we must set in

         * readObject() method.

         */

        static final long HASHSEED_OFFSET;

        static final boolean USE_HASHSEED;

        static {

            String hashSeedProp = java.security.AccessController.doPrivileged(

                    new sun.security.action.GetPropertyAction(

                        "jdk.map.useRandomSeed"));

            boolean localBool = (null != hashSeedProp)

                    ? Boolean.parseBoolean(hashSeedProp) : false;

            USE_HASHSEED = localBool;

            if (USE_HASHSEED) {

                try {

                    UNSAFE = sun.misc.Unsafe.getUnsafe();

                    HASHSEED_OFFSET = UNSAFE.objectFieldOffset(

                        HashMap.class.getDeclaredField("hashSeed"));

                } catch (NoSuchFieldException | SecurityException e) {

                    throw new InternalError("Failed to record hashSeed offset", e);

                }

            } else {

                UNSAFE = null;

                HASHSEED_OFFSET = 0;

            }

        }

    }

    /*

     * A randomizing value associated with this instance that is applied to

     * hash code of keys to make hash collisions harder to find.

     *

     * Non-final so it can be set lazily, but be sure not to set more than once.

     */

    transient final int hashSeed;

    /*

     * TreeBin/TreeNode code from CHM doesn't handle the null key.  Store the

     * null key entry here.

     */

    transient Entry<K,V> nullKeyEntry = null;

    /*

     * In order to improve performance under high hash-collision conditions,

     * HashMap will switch to storing a bin's entries in a balanced tree

     * (TreeBin) instead of a linked-list once the number of entries in the bin

     * passes a certain threshold (TreeBin.TREE_THRESHOLD), if at least one of

     * the keys in the bin implements Comparable.  This technique is borrowed

     * from ConcurrentHashMap.

     */

    /*

     * Code based on CHMv8

     *

     * Node type for TreeBin

     */

    final static class TreeNode<K,V> {

        TreeNode parent;  // red-black tree links

        TreeNode left;

        TreeNode right;

        TreeNode prev;    // needed to unlink next upon deletion

        boolean red;

        final HashMap.Entry<K,V> entry;

        TreeNode(HashMap.Entry<K,V> entry, Object next, TreeNode parent) {

            this.entry = entry;

            this.entry.next = next;

            this.parent = parent;

        }

    }

    /**

     * Returns a Class for the given object of the form "class C

     * implements Comparable<C>", if one exists, else null.  See the TreeBin

     * docs, below, for explanation.

     */

    static Class<?> comparableClassFor(Object x) {

        Class<?> c, s, cmpc; Type[] ts, as; Type t; ParameterizedType p;

        if ((c = x.getClass()) == String.class) // bypass checks

            return c;

        if ((cmpc = Comparable.class).isAssignableFrom(c)) {

            while (cmpc.isAssignableFrom(s = c.getSuperclass()))

                c = s; // find topmost comparable class

            if ((ts  = c.getGenericInterfaces()) != null) {

                for (int i = 0; i < ts.length; ++i) {

                    if (((t = ts[i]) instanceof ParameterizedType) &&

                        ((p = (ParameterizedType)t).getRawType() == cmpc) &&

                        (as = p.getActualTypeArguments()) != null &&

                        as.length == 1 && as[0] == c) // type arg is c

                        return c;

                }

            }

        }

        return null;

    }

    /*

     * Code based on CHMv8

     *

     * A specialized form of red-black tree for use in bins

     * whose size exceeds a threshold.

     *

     * TreeBins use a special form of comparison for search and

     * related operations (which is the main reason we cannot use

     * existing collections such as TreeMaps). TreeBins contain

     * Comparable elements, but may contain others, as well as

     * elements that are Comparable but not necessarily Comparable<T>

     * for the same T, so we cannot invoke compareTo among them. To

     * handle this, the tree is ordered primarily by hash value, then

     * by Comparable.compareTo order if applicable.  On lookup at a

     * node, if elements are not comparable or compare as 0 then both

     * left and right children may need to be searched in the case of

     * tied hash values. (This corresponds to the full list search

     * that would be necessary if all elements were non-Comparable and

     * had tied hashes.)  The red-black balancing code is updated from

     * pre-jdk-collections

     * (http://gee.cs.oswego.edu/dl/classes/collections/RBCell.java)

     * based in turn on Cormen, Leiserson, and Rivest "Introduction to

     * Algorithms" (CLR).

     */

    final class TreeBin {

        /*

         * The bin count threshold for using a tree rather than list for a bin. The

         * value reflects the approximate break-even point for using tree-based

         * operations.

         */

        static final int TREE_THRESHOLD = 16;

        TreeNode<K,V> root;  // root of tree

        TreeNode<K,V> first; // head of next-pointer list

        /*

         * Split a TreeBin into lo and hi parts and install in given table.

         *

         * Existing Entrys are re-used, which maintains the before/after links for

         * LinkedHashMap.Entry.

         *

         * No check for Comparable, though this is the same as CHM.

         */

        final void splitTreeBin(Object[] newTable, int i, TreeBin loTree, TreeBin hiTree) {

            TreeBin oldTree = this;

            int bit = newTable.length >>> 1;

            int loCount = 0, hiCount = 0;

            TreeNode<K,V> e = oldTree.first;

            TreeNode<K,V> next;

            // This method is called when the table has just increased capacity,

            // so indexFor() is now taking one additional bit of hash into

            // account ("bit").  Entries in this TreeBin now belong in one of

            // two bins, "i" or "i+bit", depending on if the new top bit of the

            // hash is set.  The trees for the two bins are loTree and hiTree.

            // If either tree ends up containing fewer than TREE_THRESHOLD

            // entries, it is converted back to a linked list.

            while (e != null) {

                // Save entry.next - it will get overwritten in putTreeNode()

                next = (TreeNode<K,V>)e.entry.next;

                int h = e.entry.hash;

                K k = (K) e.entry.key;

                V v = e.entry.value;

                if ((h & bit) == 0) {

                    ++loCount;

                    // Re-using e.entry

                    loTree.putTreeNode(h, k, v, e.entry);

                } else {

                    ++hiCount;

                    hiTree.putTreeNode(h, k, v, e.entry);

                }

                // Iterate using the saved 'next'

                e = next;

            }

            if (loCount < TREE_THRESHOLD) { // too small, convert back to list

                HashMap.Entry loEntry = null;

                TreeNode<K,V> p = loTree.first;

                while (p != null) {

                    @SuppressWarnings("unchecked")

                    TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;

                    p.entry.next = loEntry;

                    loEntry = p.entry;

                    p = savedNext;

                }

                // assert newTable[i] == null;

                newTable[i] = loEntry;

            } else {

                // assert newTable[i] == null;

                newTable[i] = loTree;

            }

            if (hiCount < TREE_THRESHOLD) { // too small, convert back to list

                HashMap.Entry hiEntry = null;

                TreeNode<K,V> p = hiTree.first;

                while (p != null) {

                    @SuppressWarnings("unchecked")

                    TreeNode<K,V> savedNext = (TreeNode<K,V>) p.entry.next;

                    p.entry.next = hiEntry;

                    hiEntry = p.entry;

                    p = savedNext;

                }

                // assert newTable[i + bit] == null;

                newTable[i + bit] = hiEntry;

            } else {

                // assert newTable[i + bit] == null;

                newTable[i + bit] = hiTree;

            }

        }

        /*

         * Popuplate the TreeBin with entries from the linked list e

         *

         * Assumes 'this' is a new/empty TreeBin

         *

         * Note: no check for Comparable

         * Note: I believe this changes iteration order

         */

        @SuppressWarnings("unchecked")

        void populate(HashMap.Entry e) {

            // assert root == null;

            // assert first == null;

            HashMap.Entry next;

            while (e != null) {

                // Save entry.next - it will get overwritten in putTreeNode()

                next = (HashMap.Entry)e.next;

                // Re-using Entry e will maintain before/after in LinkedHM

                putTreeNode(e.hash, (K)e.key, (V)e.value, e);

                // Iterate using the saved 'next'

                e = next;

            }

        }

        /**

         * Copied from CHMv8

         * From CLR

         */

        private void rotateLeft(TreeNode p) {

            if (p != null) {

                TreeNode r = p.right, pp, rl;

                if ((rl = p.right = r.left) != null) {

                    rl.parent = p;

                }

                if ((pp = r.parent = p.parent) == null) {

                    root = r;

                } else if (pp.left == p) {

                    pp.left = r;

                } else {

                    pp.right = r;

                }

                r.left = p;

                p.parent = r;

            }

        }

        /**

         * Copied from CHMv8

         * From CLR

         */

        private void rotateRight(TreeNode p) {

            if (p != null) {

                TreeNode l = p.left, pp, lr;

                if ((lr = p.left = l.right) != null) {

                    lr.parent = p;

                }

                if ((pp = l.parent = p.parent) == null) {

                    root = l;

                } else if (pp.right == p) {

                    pp.right = l;

                } else {

                    pp.left = l;

                }

                l.right = p;

                p.parent = l;

            }

        }

        /**

         * Returns the TreeNode (or null if not found) for the given

         * key.  A front-end for recursive version.

         */

        final TreeNode getTreeNode(int h, K k) {

            return getTreeNode(h, k, root, comparableClassFor(k));

        }

        /**

         * Returns the TreeNode (or null if not found) for the given key

         * starting at given root.

         */

        @SuppressWarnings("unchecked")

        final TreeNode getTreeNode (int h, K k, TreeNode p, Class<?> cc) {

            // assert k != null;

            while (p != null) {

                int dir, ph;  Object pk;

                if ((ph = p.entry.hash) != h)

                    dir = (h < ph) ? -1 : 1;

                else if ((pk = p.entry.key) == k || k.equals(pk))

                    return p;

                else if (cc == null || comparableClassFor(pk) != cc ||

                         (dir = ((Comparable<Object>)k).compareTo(pk)) == 0) {

                    // assert pk != null;

                    TreeNode r, pl, pr; // check both sides

                    if ((pr = p.right) != null &&

                        (r = getTreeNode(h, k, pr, cc)) != null)

                        return r;

                    else if ((pl = p.left) != null)

                        dir = -1;

                    else // nothing there

                        break;