src/share/classes/java/util/HashMap.java

Print this page

        

@@ -24,10 +24,12 @@
  */
 
 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;
 
 /**

@@ -148,16 +150,16 @@
     static final float DEFAULT_LOAD_FACTOR = 0.75f;
 
     /**
      * An empty table instance to share when the table is not inflated.
      */
-    static final Entry<?,?>[] EMPTY_TABLE = {};
+    static final Object[] EMPTY_TABLE = {};
 
     /**
      * The table, resized as necessary. Length MUST Always be a power of two.
      */
-    transient Entry<?,?>[] table = EMPTY_TABLE;
+    transient Object[] table = EMPTY_TABLE;
 
     /**
      * The number of key-value mappings contained in this map.
      */
     transient int size;

@@ -184,10 +186,13 @@
      * 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;

@@ -196,26 +201,613 @@
          * 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;
+
+            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.
      */
-    transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+        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 && h >= pr.entry.hash &&
+                        (r = getTreeNode(h, k, pr, cc)) != null)
+                        return r;
+                    else if ((pl = p.left) != null && h <= pl.entry.hash)
+                        dir = -1;
+                    else // nothing there
+                        break;
+                }
+                p = (dir > 0) ? p.right : p.left;
+            }
+            return null;
+        }
+
+        /*
+         * Finds or adds a node.
+         *
+         * 'entry' should be used to recycle an existing Entry (e.g. in the case
+         * of converting a linked-list bin to a TreeBin).
+         * If entry is null, a new Entry will be created for the new TreeNode
+         * 
+         * @return the TreeNode containing the mapping, or null if a new
+         * TreeNode was added
+         */
+        @SuppressWarnings("unchecked")
+        TreeNode putTreeNode(int h, K k, V v, HashMap.Entry<K,V> entry) {
+            // assert k != null;
+            //if (entry != null) {
+                // assert h == entry.hash;
+                // assert k == entry.key;
+                // assert v == entry.value;
+            // }        
+            Class<?> cc = comparableClassFor(k);
+            TreeNode pp = root, p = null;
+            int dir = 0;
+            while (pp != null) { // find existing node or leaf to insert at
+                int ph;  Object pk;
+                p = pp;
+                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) {
+                    TreeNode r, pr;
+                    if ((pr = p.right) != null && h >= pr.entry.hash &&
+                        (r = getTreeNode(h, k, pr, cc)) != null)
+                        return r;
+                    else // continue left
+                        dir = -1;
+                }
+                pp = (dir > 0) ? p.right : p.left;
+            }
+
+            // Didn't find the mapping in the tree, so add it
+            TreeNode f = first;
+            TreeNode x;
+            if (entry != null) {
+                x = new TreeNode(entry, f, p);
+            } else {
+                x = new TreeNode(newEntry(h, k, v, null), f, p);
+            }
+            first = x;
+
+            if (p == null) {
+                root = x;
+            } else { // attach and rebalance; adapted from CLR
+                TreeNode xp, xpp;
+                if (f != null) {
+                    f.prev = x;
+                }
+                if (dir <= 0) {
+                    p.left = x;
+                } else {
+                    p.right = x;
+                }
+                x.red = true;
+                while (x != null && (xp = x.parent) != null && xp.red
+                        && (xpp = xp.parent) != null) {
+                    TreeNode xppl = xpp.left;
+                    if (xp == xppl) {
+                        TreeNode y = xpp.right;
+                        if (y != null && y.red) {
+                            y.red = false;
+                            xp.red = false;
+                            xpp.red = true;
+                            x = xpp;
+                        } else {
+                            if (x == xp.right) {
+                                rotateLeft(x = xp);
+                                xpp = (xp = x.parent) == null ? null : xp.parent;
+                            }
+                            if (xp != null) {
+                                xp.red = false;
+                                if (xpp != null) {
+                                    xpp.red = true;
+                                    rotateRight(xpp);
+                                }
+                            }
+                        }
+                    } else {
+                        TreeNode y = xppl;
+                        if (y != null && y.red) {
+                            y.red = false;
+                            xp.red = false;
+                            xpp.red = true;
+                            x = xpp;
+                        } else {
+                            if (x == xp.left) {
+                                rotateRight(x = xp);
+                                xpp = (xp = x.parent) == null ? null : xp.parent;
+                            }
+                            if (xp != null) {
+                                xp.red = false;
+                                if (xpp != null) {
+                                    xpp.red = true;
+                                    rotateLeft(xpp);
+                                }
+                            }
+                        }
+                    }
+                }
+                TreeNode r = root;
+                if (r != null && r.red) {
+                    r.red = false;
+                }
+            }
+            return null;
+        }
+
+        /*
+         * From CHMv8
+         * 
+         * Removes the given node, that must be present before this
+         * call.  This is messier than typical red-black deletion code
+         * because we cannot swap the contents of an interior node
+         * with a leaf successor that is pinned by "next" pointers
+         * that are accessible independently of lock. So instead we
+         * swap the tree linkages.
+         */
+        final void deleteTreeNode(TreeNode p) {
+            TreeNode next = (TreeNode) p.entry.next; // unlink traversal pointers
+            TreeNode pred = p.prev;
+            if (pred == null) {
+                first = next;
+            } else {
+                pred.entry.next = next;
+            }
+            if (next != null) {
+                next.prev = pred;
+            }
+            TreeNode replacement;
+            TreeNode pl = p.left;
+            TreeNode pr = p.right;
+            if (pl != null && pr != null) {
+                TreeNode s = pr, sl;
+                while ((sl = s.left) != null) // find successor
+                {
+                    s = sl;
+                }
+                boolean c = s.red;
+                s.red = p.red;
+                p.red = c; // swap colors
+                TreeNode sr = s.right;
+                TreeNode pp = p.parent;
+                if (s == pr) { // p was s's direct parent
+                    p.parent = s;
+                    s.right = p;
+                } else {
+                    TreeNode sp = s.parent;
+                    if ((p.parent = sp) != null) {
+                        if (s == sp.left) {
+                            sp.left = p;
+                        } else {
+                            sp.right = p;
+                        }
+                    }
+                    if ((s.right = pr) != null) {
+                        pr.parent = s;
+                    }
+                }
+                p.left = null;
+                if ((p.right = sr) != null) {
+                    sr.parent = p;
+                }
+                if ((s.left = pl) != null) {
+                    pl.parent = s;
+                }
+                if ((s.parent = pp) == null) {
+                    root = s;
+                } else if (p == pp.left) {
+                    pp.left = s;
+                } else {
+                    pp.right = s;
+                }
+                replacement = sr;
+            } else {
+                replacement = (pl != null) ? pl : pr;
+            }
+            TreeNode pp = p.parent;
+            if (replacement == null) {
+                if (pp == null) {
+                    root = null;
+                    return;
+                }
+                replacement = p;
+            } else {
+                replacement.parent = pp;
+                if (pp == null) {
+                    root = replacement;
+                } else if (p == pp.left) {
+                    pp.left = replacement;
+                } else {
+                    pp.right = replacement;
+                }
+                p.left = p.right = p.parent = null;
+            }
+            if (!p.red) { // rebalance, from CLR
+                TreeNode x = replacement;
+                while (x != null) {
+                    TreeNode xp, xpl;
+                    if (x.red || (xp = x.parent) == null) {
+                        x.red = false;
+                        break;
+                    }
+                    if (x == (xpl = xp.left)) {
+                        TreeNode sib = xp.right;
+                        if (sib != null && sib.red) {
+                            sib.red = false;
+                            xp.red = true;
+                            rotateLeft(xp);
+                            sib = (xp = x.parent) == null ? null : xp.right;
+                        }
+                        if (sib == null) {
+                            x = xp;
+                        } else {
+                            TreeNode sl = sib.left, sr = sib.right;
+                            if ((sr == null || !sr.red)
+                                    && (sl == null || !sl.red)) {
+                                sib.red = true;
+                                x = xp;
+                            } else {
+                                if (sr == null || !sr.red) {
+                                    if (sl != null) {
+                                        sl.red = false;
+                                    }
+                                    sib.red = true;
+                                    rotateRight(sib);
+                                    sib = (xp = x.parent) == null ?
+                                        null : xp.right;
+                                }
+                                if (sib != null) {
+                                    sib.red = (xp == null) ? false : xp.red;
+                                    if ((sr = sib.right) != null) {
+                                        sr.red = false;
+                                    }
+                                }
+                                if (xp != null) {
+                                    xp.red = false;
+                                    rotateLeft(xp);
+                                }
+                                x = root;
+                            }
+                        }
+                    } else { // symmetric
+                        TreeNode sib = xpl;
+                        if (sib != null && sib.red) {
+                            sib.red = false;
+                            xp.red = true;
+                            rotateRight(xp);
+                            sib = (xp = x.parent) == null ? null : xp.left;
+                        }
+                        if (sib == null) {
+                            x = xp;
+                        } else {
+                            TreeNode sl = sib.left, sr = sib.right;
+                            if ((sl == null || !sl.red)
+                                    && (sr == null || !sr.red)) {
+                                sib.red = true;
+                                x = xp;
+                            } else {
+                                if (sl == null || !sl.red) {
+                                    if (sr != null) {
+                                        sr.red = false;
+                                    }
+                                    sib.red = true;
+                                    rotateLeft(sib);
+                                    sib = (xp = x.parent) == null ?
+                                        null : xp.left;
+                                }
+                                if (sib != null) {
+                                    sib.red = (xp == null) ? false : xp.red;
+                                    if ((sl = sib.left) != null) {
+                                        sl.red = false;
+                                    }
+                                }
+                                if (xp != null) {
+                                    xp.red = false;
+                                    rotateRight(xp);
+                                }
+                                x = root;
+                            }
+                        }
+                    }
+                }
+            }
+            if (p == replacement && (pp = p.parent) != null) {
+                if (p == pp.left) // detach pointers
+                {
+                    pp.left = null;
+                } else if (p == pp.right) {
+                    pp.right = null;
+                }
+                p.parent = null;
+            }
+        }
+    }
 
     /**
      * Constructs an empty <tt>HashMap</tt> with the specified initial
      * capacity and load factor.
      *

@@ -231,13 +823,13 @@
         if (initialCapacity > MAXIMUM_CAPACITY)
             initialCapacity = MAXIMUM_CAPACITY;
         if (loadFactor <= 0 || Float.isNaN(loadFactor))
             throw new IllegalArgumentException("Illegal load factor: " +
                                                loadFactor);
-
         this.loadFactor = loadFactor;
         threshold = initialCapacity;
+        hashSeed = initHashSeed();
         init();
     }
 
     /**
      * Constructs an empty <tt>HashMap</tt> with the specified initial

@@ -271,10 +863,11 @@
         this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                       DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
         inflateTable(threshold);
 
         putAllForCreate(m);
+        // assert size == m.size();
     }
 
     private static int roundUpToPowerOf2(int number) {
         // assert number >= 0 : "number must be non-negative";
         int rounded = number >= MAXIMUM_CAPACITY

@@ -292,11 +885,11 @@
     private void inflateTable(int toSize) {
         // Find a power of 2 >= toSize
         int capacity = roundUpToPowerOf2(toSize);
 
         threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
-        table = new Entry[capacity];
+        table = new Object[capacity];
     }
 
     // internal utilities
 
     /**

@@ -308,21 +901,28 @@
      */
     void init() {
     }
 
     /**
+     * Return an initial value for the hashSeed, or 0 if the random seed is not
+     * enabled.
+     */
+    final int initHashSeed() {
+        if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
+            return sun.misc.Hashing.randomHashSeed(this);
+        }
+        return 0;
+    }
+
+    /**
      * Retrieve object hash code and applies a supplemental hash function to the
      * result hash, which defends against poor quality hash functions.  This is
      * critical because HashMap uses power-of-two length hash tables, that
      * otherwise encounter collisions for hashCodes that do not differ
      * in lower bits.
      */
     final int hash(Object k) {
-        if (k instanceof String) {
-            return ((String) k).hash32();
-        }
-
         int  h = hashSeed ^ k.hashCode();
 
         // This function ensures that hashCodes that differ only by
         // constant multiples at each bit position have a bounded
         // number of collisions (approximately 8 at default load factor).

@@ -407,23 +1007,39 @@
     @SuppressWarnings("unchecked")
     final Entry<K,V> getEntry(Object key) {
         if (isEmpty()) {
             return null;
         }
+        if (key == null) {
+            return nullKeyEntry;
+        }
+        int hash = hash(key);
+        int bin = indexFor(hash, table.length);
 
-        int hash = (key == null) ? 0 : hash(key);
-        for (Entry<?,?> e = table[indexFor(hash, table.length)];
-             e != null;
-             e = e.next) {
+        if (table[bin] instanceof Entry) {
+            Entry<K,V> e = (Entry<K,V>) table[bin];
+            for (; e != null; e = (Entry<K,V>)e.next) {
             Object k;
             if (e.hash == hash &&
-                ((k = e.key) == key || (key != null && key.equals(k))))
-                return (Entry<K,V>)e;
+                    ((k = e.key) == key || key.equals(k))) {
+                    return e;
+                }
+            }
+        } else if (table[bin] != null) {
+            TreeBin e = (TreeBin)table[bin];
+            TreeNode p = e.getTreeNode(hash, (K)key);
+            if (p != null) {
+                // assert p.entry.hash == hash && p.entry.key.equals(key);
+                return (Entry<K,V>)p.entry;
+            } else {
+                return null;
+            }
         }
         return null;
     }
 
+
     /**
      * Associates the specified value with the specified key in this map.
      * If the map previously contained a mapping for the key, the old
      * value is replaced.
      *

@@ -432,80 +1048,141 @@
      * @return the previous value associated with <tt>key</tt>, or
      *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
      *         (A <tt>null</tt> return can also indicate that the map
      *         previously associated <tt>null</tt> with <tt>key</tt>.)
      */
+    @SuppressWarnings("unchecked")    
     public V put(K key, V value) {
         if (table == EMPTY_TABLE) {
             inflateTable(threshold);
         }
         if (key == null)
             return putForNullKey(value);
         int hash = hash(key);
         int i = indexFor(hash, table.length);
-        @SuppressWarnings("unchecked")
-        Entry<K,V> e = (Entry<K,V>)table[i];
-        for(; e != null; e = e.next) {
+        boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin? 
+
+        if (table[i] instanceof Entry) {
+            // Bin contains ordinary Entries.  Search for key in the linked list
+            // of entries, counting the number of entries.  Only check for
+            // TreeBin conversion if the list size is >= TREE_THRESHOLD.
+            // (The conversion still may not happen if the table gets resized.)
+            int listSize = 0;
+            Entry<K,V> e = (Entry<K,V>) table[i];
+            for (; e != null; e = (Entry<K,V>)e.next) {
             Object k;
             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
+                listSize++;
+            }
+            // Didn't find, so fall through and call addEntry() to add the 
+            // Entry and check for TreeBin conversion.
+            checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+        } else if (table[i] != null) {
+            TreeBin e = (TreeBin)table[i];
+            TreeNode p = e.putTreeNode(hash, key, value, null);
+            if (p == null) { // putTreeNode() added a new node
+                modCount++;
+                size++;
+                if (size >= threshold) {
+                    resize(2 * table.length);
+                }
+                return null;
+            } else { // putTreeNode() found an existing node
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                V oldVal = pEntry.value;
+                pEntry.value = value;
+                pEntry.recordAccess(this);
+                return oldVal;
+            }
         }
-
         modCount++;
-        addEntry(hash, key, value, i);
+        addEntry(hash, key, value, i, checkIfNeedTree);
         return null;
     }
 
     /**
      * Offloaded version of put for null keys
      */
     private V putForNullKey(V value) {
-        @SuppressWarnings("unchecked")
-        Entry<K,V> e = (Entry<K,V>)table[0];
-        for(; e != null; e = e.next) {
-            if (e.key == null) {
-                V oldValue = e.value;
-                e.value = value;
-                e.recordAccess(this);
+        if (nullKeyEntry != null) {
+            V oldValue = nullKeyEntry.value;
+            nullKeyEntry.value = value;
+            nullKeyEntry.recordAccess(this);
                 return oldValue;
             }
-        }
         modCount++;
-        addEntry(0, null, value, 0);
+        size++; // newEntry() skips size++
+        nullKeyEntry = newEntry(0, null, value, null);        
         return null;
     }
 
+    private void putForCreateNullKey(V value) {
+        // Look for preexisting entry for key.  This will never happen for
+        // clone or deserialize.  It will only happen for construction if the
+        // input Map is a sorted map whose ordering is inconsistent w/ equals.        
+        if (nullKeyEntry != null) {
+            nullKeyEntry.value = value;            
+        } else {
+            nullKeyEntry = newEntry(0, null, value, null);
+            size++;
+        }        
+    }
+
+
     /**
      * This method is used instead of put by constructors and
      * pseudoconstructors (clone, readObject).  It does not resize the table,
-     * check for comodification, etc.  It calls createEntry rather than
-     * addEntry.
+     * check for comodification, etc, though it will convert bins to TreeBins
+     * as needed.  It calls createEntry rather than addEntry.
      */
+    @SuppressWarnings("unchecked")    
     private void putForCreate(K key, V value) {
-        int hash = null == key ? 0 : hash(key);
+        if (null == key) {
+            putForCreateNullKey(value);
+            return;
+        }
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+        boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?
 
         /**
          * Look for preexisting entry for key.  This will never happen for
          * clone or deserialize.  It will only happen for construction if the
          * input Map is a sorted map whose ordering is inconsistent w/ equals.
          */
-        for (@SuppressWarnings("unchecked")
-             Entry<?,V> e = (Entry<?,V>)table[i]; e != null; e = e.next) {
+        if (table[i] instanceof Entry) {
+            int listSize = 0;
+            Entry<K,V> e = (Entry<K,V>) table[i];
+            for (; e != null; e = (Entry<K,V>)e.next) {
             Object k;
-            if (e.hash == hash &&
-                ((k = e.key) == key || (key != null && key.equals(k)))) {
+                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                 e.value = value;
                 return;
             }
+                listSize++;
+            }
+            // Didn't find, fall through to createEntry().
+            // Check for conversion to TreeBin done via createEntry().
+            checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+        } else if (table[i] != null) {
+            TreeBin e = (TreeBin)table[i];
+            TreeNode p = e.putTreeNode(hash, key, value, null);
+            if (p != null) {
+                p.entry.setValue(value); // Found an existing node, set value
+            } else {
+                size++; // Added a new TreeNode, so update size
+            }
+            // don't need modCount++/check for resize - just return
+            return;
         }
 
-        createEntry(hash, key, value, i);
+        createEntry(hash, key, value, i, checkIfNeedTree);
     }
 
     private void putAllForCreate(Map<? extends K, ? extends V> m) {
         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
             putForCreate(e.getKey(), e.getValue());

@@ -524,39 +1201,51 @@
      *        must be greater than current capacity unless current
      *        capacity is MAXIMUM_CAPACITY (in which case value
      *        is irrelevant).
      */
     void resize(int newCapacity) {
-        Entry<?,?>[] oldTable = table;
+        Object[] oldTable = table;
         int oldCapacity = oldTable.length;
         if (oldCapacity == MAXIMUM_CAPACITY) {
             threshold = Integer.MAX_VALUE;
             return;
         }
 
-        Entry<?,?>[] newTable = new Entry<?,?>[newCapacity];
+        Object[] newTable = new Object[newCapacity];
         transfer(newTable);
         table = newTable;
         threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
     }
 
     /**
      * Transfers all entries from current table to newTable.
+     * 
+     * Assumes newTable is larger than table
      */
     @SuppressWarnings("unchecked")
-    void transfer(Entry<?,?>[] newTable) {
-        Entry<?,?>[] src = table;
+    void transfer(Object[] newTable) {       
+        Object[] src = table;
+        // assert newTable.length > src.length : "newTable.length(" +
+        //   newTable.length + ") expected to be > src.length("+src.length+")";
         int newCapacity = newTable.length;
-        for (int j = 0; j < src.length; j++ ) {
+        for (int j = 0; j < src.length; j++) {
+             if (src[j] instanceof Entry) {
+                // Assume: since wasn't TreeBin before, won't need TreeBin now
             Entry<K,V> e = (Entry<K,V>) src[j];
-            while(null != e) {
-                Entry<K,V> next = e.next;
+                while (null != e) {
+                    Entry<K,V> next = (Entry<K,V>)e.next;
                 int i = indexFor(e.hash, newCapacity);
                 e.next = (Entry<K,V>) newTable[i];
                 newTable[i] = e;
                 e = next;
             }
+            } else if (src[j] != null) {
+                TreeBin e = (TreeBin) src[j];
+                TreeBin loTree = new TreeBin();
+                TreeBin hiTree = new TreeBin();
+                e.splitTreeBin(newTable, j, loTree, hiTree);
+            }
         }
         Arrays.fill(table, null);
     }
 
     /**

@@ -583,19 +1272,12 @@
          * condition could result in a map with twice the appropriate capacity,
          * if the keys to be added overlap with the keys already in this map.
          * By using the conservative calculation, we subject ourself
          * to at most one extra resize.
          */
-        if (numKeysToBeAdded > threshold) {
-            int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
-            if (targetCapacity > MAXIMUM_CAPACITY)
-                targetCapacity = MAXIMUM_CAPACITY;
-            int newCapacity = table.length;
-            while (newCapacity < targetCapacity)
-                newCapacity <<= 1;
-            if (newCapacity > table.length)
-                resize(newCapacity);
+        if (numKeysToBeAdded > threshold && table.length < MAXIMUM_CAPACITY) {
+            resize(table.length * 2); 
         }
 
         for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
             put(e.getKey(), e.getValue());
     }

@@ -619,44 +1301,87 @@
     @Override
     public V putIfAbsent(K key, V value) {
         if (table == EMPTY_TABLE) {
             inflateTable(threshold);
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            if (nullKeyEntry == null || nullKeyEntry.value == null) {
+                putForNullKey(value);
+                return null;
+            } else {
+                return nullKeyEntry.value;
+            }
+        }
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
-        @SuppressWarnings("unchecked")
-        Entry<K,V> e = (Entry<K,V>)table[i];
-        for(; e != null; e = e.next) {
+        boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?        
+        
+        if (table[i] instanceof Entry) {
+            int listSize = 0;
+            Entry<K,V> e = (Entry<K,V>) table[i];
+            for (; e != null; e = (Entry<K,V>)e.next) {
             if (e.hash == hash && Objects.equals(e.key, key)) {
-                if(e.value != null) {
+                    if (e.value != null) {
                     return e.value;
                 }
                 e.value = value;
-                modCount++;
                 e.recordAccess(this);
                 return null;
             }
+                listSize++;
         }
-
+            // Didn't find, so fall through and call addEntry() to add the 
+            // Entry and check for TreeBin conversion.
+            checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+        } else if (table[i] != null) {
+            TreeBin e = (TreeBin)table[i];
+            TreeNode p = e.putTreeNode(hash, key, value, null);
+            if (p == null) { // not found, putTreeNode() added a new node
         modCount++;
-        addEntry(hash, key, value, i);
+                size++;
+                if (size >= threshold) {
+                    resize(2 * table.length);
+                }
+                return null;
+            } else { // putTreeNode() found an existing node
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                V oldVal = pEntry.value;
+                if (oldVal == null) { // only replace if maps to null
+                    pEntry.value = value;
+                    pEntry.recordAccess(this);
+                }
+                return oldVal;
+            }
+        }
+        modCount++;
+        addEntry(hash, key, value, i, checkIfNeedTree);
         return null;
     }
 
     @Override
     public boolean remove(Object key, Object value) {
         if (isEmpty()) {
             return false;
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            if (nullKeyEntry != null &&
+                 Objects.equals(nullKeyEntry.value, value)) {
+                removeNullKey();
+                return true;
+            }            
+            return false;
+        }        
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+
+        if (table[i] instanceof Entry) {
         @SuppressWarnings("unchecked")
-        Entry<K,V> prev = (Entry<K,V>)table[i];
+            Entry<K,V> prev = (Entry<K,V>) table[i];
         Entry<K,V> e = prev;
-
         while (e != null) {
-            Entry<K,V> next = e.next;
+                @SuppressWarnings("unchecked")            
+                Entry<K,V> next = (Entry<K,V>) e.next;
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 if (!Objects.equals(e.value, value)) {
                     return false;
                 }
                 modCount++;

@@ -669,100 +1394,230 @@
                 return true;
             }
             prev = e;
             e = next;
         }
-
+        } else if (table[i] != null) {
+            TreeBin tb = ((TreeBin) table[i]);
+            TreeNode p = tb.getTreeNode(hash, (K)key);
+            if (p != null) {
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                // assert pEntry.key.equals(key);
+                if (Objects.equals(pEntry.value, value)) {
+                    modCount++;
+                    size--;
+                    tb.deleteTreeNode(p);
+                    pEntry.recordRemoval(this);
+                    if (tb.root == null || tb.first == null) {
+                        // assert tb.root == null && tb.first == null :
+                        //         "TreeBin.first and root should both be null";
+                        // TreeBin is now empty, we should blank this bin
+                        table[i] = null;
+                    }
+                    return true;
+                }
+            }
+        }
         return false;
     }
 
     @Override
     public boolean replace(K key, V oldValue, V newValue) {
         if (isEmpty()) {
             return false;
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            if (nullKeyEntry != null &&
+                 Objects.equals(nullKeyEntry.value, oldValue)) {
+                putForNullKey(newValue);
+                return true;
+            }            
+            return false;
+        }        
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+
+        if (table[i] instanceof Entry) {
         @SuppressWarnings("unchecked")
-        Entry<K,V> e = (Entry<K,V>)table[i];
-        for (; e != null; e = e.next) {
+            Entry<K,V> e = (Entry<K,V>) table[i];
+            for (; e != null; e = (Entry<K,V>)e.next) {
             if (e.hash == hash && Objects.equals(e.key, key) && Objects.equals(e.value, oldValue)) {
                 e.value = newValue;
                 e.recordAccess(this);
                 return true;
             }
         }
-
+            return false;
+        } else if (table[i] != null) {
+            TreeBin tb = ((TreeBin) table[i]);
+            TreeNode p = tb.getTreeNode(hash, key);
+            if (p != null) {
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                // assert pEntry.key.equals(key);
+                if (Objects.equals(pEntry.value, oldValue)) {
+                    pEntry.value = newValue;
+                    pEntry.recordAccess(this);
+                    return true;
+                }
+            }
+        }
         return false;
     }
 
     @Override
     public V replace(K key, V value) {
         if (isEmpty()) {
             return null;
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            if (nullKeyEntry != null) {
+                return putForNullKey(value);
+            }            
+            return null;
+        }        
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+        if (table[i] instanceof Entry) {
         @SuppressWarnings("unchecked")
         Entry<K,V> e = (Entry<K,V>)table[i];
-        for (; e != null; e = e.next) {
+            for (; e != null; e = (Entry<K,V>)e.next) {
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }
-
-        return null;
+
+            return null;
+        } else if (table[i] != null) {
+            TreeBin tb = ((TreeBin) table[i]);
+            TreeNode p = tb.getTreeNode(hash, key);
+            if (p != null) {
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                // assert pEntry.key.equals(key);
+                V oldValue = pEntry.value;
+                pEntry.value = value;
+                pEntry.recordAccess(this);
+                return oldValue;
+            }
+        }
+        return null;
+    }
+
+    @Override
+    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+        if (table == EMPTY_TABLE) {
+            inflateTable(threshold);
+        }
+        if (key == null) {
+            if (nullKeyEntry == null || nullKeyEntry.value == null) {
+                V newValue = mappingFunction.apply(key);
+                if (newValue != null) {
+                    putForNullKey(newValue);
+                }
+                return newValue;
+            }            
+            return nullKeyEntry.value;
+        }        
+        int hash = hash(key);
+        int i = indexFor(hash, table.length);
+        boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?        
+
+        if (table[i] instanceof Entry) {
+            int listSize = 0;
+            @SuppressWarnings("unchecked")            
+            Entry<K,V> e = (Entry<K,V>)table[i];
+            for (; e != null; e = (Entry<K,V>)e.next) {
+                if (e.hash == hash && Objects.equals(e.key, key)) {
+                    V oldValue = e.value;
+                    if (oldValue == null) {
+                        V newValue = mappingFunction.apply(key);
+                        if (newValue != null) {
+                            e.value = newValue;
+                            e.recordAccess(this);
+                        }
+                        return newValue;
+                    }
+                    return oldValue;
+                }
+                listSize++;
+            }
+            // Didn't find, fall through to call the mapping function
+            checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;
+        } else if (table[i] != null) {
+            TreeBin e = (TreeBin)table[i];            
+            V value = mappingFunction.apply(key);
+            if (value == null) { // Return the existing value, if any
+                TreeNode p = e.getTreeNode(hash, key);
+                if (p != null) {
+                    return (V) p.entry.value;
+                }
+                return null;
+            } else { // Put the new value into the Tree, if absent
+                TreeNode p = e.putTreeNode(hash, key, value, null);
+                if (p == null) { // not found, new node was added
+                    modCount++;
+                    size++;
+                    if (size >= threshold) {
+                        resize(2 * table.length);
+                    }
+                    return value;
+                } else { // putTreeNode() found an existing node
+                    Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                    V oldVal = pEntry.value;
+                    if (oldVal == null) { // only replace if maps to null
+                        pEntry.value = value;
+                        pEntry.recordAccess(this);
+                        return value;
     }
-
-    @Override
-    public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
-        if (table == EMPTY_TABLE) {
-            inflateTable(threshold);
+                    return oldVal;
         }
-        int hash = (key == null) ? 0 : hash(key);
-        int i = indexFor(hash, table.length);
-        @SuppressWarnings("unchecked")
-        Entry<K,V> e = (Entry<K,V>)table[i];
-        for (; e != null; e = e.next) {
-            if (e.hash == hash && Objects.equals(e.key, key)) {
-                V oldValue = e.value;
-                return oldValue == null ? (e.value = mappingFunction.apply(key)) : oldValue;
             }
         }
-
         V newValue = mappingFunction.apply(key);
-        if (newValue != null) {
+        if (newValue != null) { // add Entry and check for TreeBin conversion
             modCount++;
-            addEntry(hash, key, newValue, i);
+            addEntry(hash, key, newValue, i, checkIfNeedTree);
         }
 
         return newValue;
     }
 
     @Override
     public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
         if (isEmpty()) {
             return null;
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            V oldValue;
+            if (nullKeyEntry != null && (oldValue = nullKeyEntry.value) != null) {                
+                V newValue = remappingFunction.apply(key, oldValue);
+                if (newValue != null ) {
+                    putForNullKey(newValue);
+                    return newValue;                    
+                } else {
+                    removeNullKey();
+                }
+            }
+            return null;
+        }
+        int hash = hash(key);        
         int i = indexFor(hash, table.length);
+        if (table[i] instanceof Entry) {
         @SuppressWarnings("unchecked")
         Entry<K,V> prev = (Entry<K,V>)table[i];
         Entry<K,V> e = prev;
-
         while (e != null) {
-            Entry<K,V> next = e.next;
+                Entry<K,V> next = (Entry<K,V>)e.next;
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 V oldValue = e.value;
                 if (oldValue == null)
                     break;
                 V newValue = remappingFunction.apply(key, oldValue);
-                modCount++;
                 if (newValue == null) {
+                        modCount++;                        
                     size--;
                     if (prev == e)
                         table[i] = next;
                     else
                         prev.next = next;

@@ -774,33 +1629,76 @@
                 return newValue;
             }
             prev = e;
             e = next;
         }
-
+        } else if (table[i] != null) {
+            TreeBin tb = (TreeBin)table[i];
+            TreeNode p = tb.getTreeNode(hash, key);
+            if (p != null) {
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                // assert pEntry.key.equals(key);
+                V oldValue = pEntry.value;
+                if (oldValue != null) {
+                    V newValue = remappingFunction.apply(key, oldValue);
+                    if (newValue == null) { // remove mapping
+                        modCount++;                        
+                        size--;
+                        tb.deleteTreeNode(p);
+                        pEntry.recordRemoval(this);
+                        if (tb.root == null || tb.first == null) {
+                            // assert tb.root == null && tb.first == null :
+                            //     "TreeBin.first and root should both be null";
+                            // TreeBin is now empty, we should blank this bin
+                            table[i] = null;
+                        }
+                    } else {
+                        pEntry.value = newValue;
+                        pEntry.recordAccess(this);
+                    }
+                    return newValue;
+                }
+            }
+        }
         return null;
     }
 
     @Override
     public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
         if (table == EMPTY_TABLE) {
             inflateTable(threshold);
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
+            V newValue = remappingFunction.apply(key, oldValue);
+            if (newValue != oldValue) {
+                if (newValue == null) {                    
+                    removeNullKey();            
+                } else {
+                    putForNullKey(newValue);
+                }
+            }            
+            return newValue;
+        }
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+        boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin?        
+        
+        if (table[i] instanceof Entry) {
+            int listSize = 0;            
         @SuppressWarnings("unchecked")
         Entry<K,V> prev = (Entry<K,V>)table[i];
         Entry<K,V> e = prev;
 
         while (e != null) {
-            Entry<K,V> next = e.next;
+                Entry<K,V> next = (Entry<K,V>)e.next;
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 V oldValue = e.value;
                 V newValue = remappingFunction.apply(key, oldValue);
                 if (newValue != oldValue) {
-                    modCount++;
                     if (newValue == null) {
+                            modCount++;                            
                         size--;
                         if (prev == e)
                             table[i] = next;
                         else
                             prev.next = next;

@@ -812,39 +1710,92 @@
                 }
                 return newValue;
             }
             prev = e;
             e = next;
+                listSize++;                
+            }
+            checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;            
+        } else if (table[i] != null) {
+            TreeBin tb = (TreeBin)table[i];
+            TreeNode p = tb.getTreeNode(hash, key);
+            V oldValue = p == null ? null : (V)p.entry.value;
+            V newValue = remappingFunction.apply(key, oldValue);
+            if (newValue != oldValue) {
+                if (newValue == null) {
+                    Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                    modCount++;
+                    size--;
+                    tb.deleteTreeNode(p);
+                    pEntry.recordRemoval(this);
+                    if (tb.root == null || tb.first == null) {
+                        // assert tb.root == null && tb.first == null :
+                        //         "TreeBin.first and root should both be null";
+                        // TreeBin is now empty, we should blank this bin
+                        table[i] = null;
+                    }
+                } else {
+                    if (p != null) { // just update the value
+                        Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                        pEntry.value = newValue;
+                        pEntry.recordAccess(this);
+                    } else { // need to put new node
+                        p = tb.putTreeNode(hash, key, newValue, null);
+                        // assert p == null; // should have added a new node
+                        modCount++;
+                        size++;
+                        if (size >= threshold) {
+                            resize(2 * table.length);
+                        }
+                    }
+                }
+            }
+            return newValue;
         }
 
         V newValue = remappingFunction.apply(key, null);
         if (newValue != null) {
             modCount++;
-            addEntry(hash, key, newValue, i);
+            addEntry(hash, key, newValue, i, checkIfNeedTree);
         }
 
         return newValue;
     }
 
     @Override
     public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
         if (table == EMPTY_TABLE) {
             inflateTable(threshold);
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            V oldValue = nullKeyEntry == null ? null : nullKeyEntry.value;
+            V newValue = oldValue == null ? value : remappingFunction.apply(oldValue, value);
+            if (newValue != null) {
+                putForNullKey(newValue);                
+            } else if (nullKeyEntry != null) {
+                removeNullKey();
+            }
+            return newValue;
+        }        
+        int hash = hash(key);        
         int i = indexFor(hash, table.length);
+        boolean checkIfNeedTree = false; // Might we convert bin to a TreeBin? 
+        
+        if (table[i] instanceof Entry) {
+            int listSize = 0;            
         @SuppressWarnings("unchecked")
         Entry<K,V> prev = (Entry<K,V>)table[i];
         Entry<K,V> e = prev;
 
         while (e != null) {
-            Entry<K,V> next = e.next;
+                Entry<K,V> next = (Entry<K,V>)e.next;
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 V oldValue = e.value;
-                V newValue = remappingFunction.apply(oldValue, value);
-                modCount++;
+                    V newValue = (oldValue == null) ? value :
+                                 remappingFunction.apply(oldValue, value);
                 if (newValue == null) {
+                        modCount++;
                     size--;
                     if (prev == e)
                         table[i] = next;
                     else
                         prev.next = next;

@@ -855,42 +1806,94 @@
                 }
                 return newValue;
             }
             prev = e;
             e = next;
+                listSize++;                
         }
+            // Didn't find, so fall through and (maybe) call addEntry() to add
+            // the Entry and check for TreeBin conversion.
+            checkIfNeedTree = listSize >= TreeBin.TREE_THRESHOLD;            
+        } else if (table[i] != null) {
+            TreeBin tb = (TreeBin)table[i];
+            TreeNode p = tb.getTreeNode(hash, key);
+            V oldValue = p == null ? null : (V)p.entry.value;
+            V newValue = (oldValue == null) ? value :
+                         remappingFunction.apply(oldValue, value);
+            if (newValue == null) {
+                if (p != null) {
+                    Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                    modCount++;
+                    size--;
+                    tb.deleteTreeNode(p);
+                    pEntry.recordRemoval(this);
 
+                    if (tb.root == null || tb.first == null) {
+                        // assert tb.root == null && tb.first == null :
+                        //         "TreeBin.first and root should both be null";
+                        // TreeBin is now empty, we should blank this bin
+                        table[i] = null;
+                    }
+                }
+                return null;
+            } else if (newValue != oldValue) {
+                if (p != null) { // just update the value
+                    Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                    pEntry.value = newValue;
+                    pEntry.recordAccess(this);                        
+                } else { // need to put new node
+                    p = tb.putTreeNode(hash, key, newValue, null);
+                    // assert p == null; // should have added a new node
+                    modCount++;
+                    size++;
+                    if (size >= threshold) {
+                        resize(2 * table.length);
+                    }
+                }                
+            }
+            return newValue;
+        }
         if (value != null) {
             modCount++;
-            addEntry(hash, key, value, i);
+            addEntry(hash, key, value, i, checkIfNeedTree);
         }
-
         return value;
     }
 
     // end of optimized implementations of default methods in Map
 
     /**
      * Removes and returns the entry associated with the specified key
      * in the HashMap.  Returns null if the HashMap contains no mapping
      * for this key.
+     *
+     * We don't bother converting TreeBins back to Entry lists if the bin falls
+     * back below TREE_THRESHOLD, but we do clear bins when removing the last
+     * TreeNode in a TreeBin.
      */
     final Entry<K,V> removeEntryForKey(Object key) {
         if (isEmpty()) {
             return null;
         }
-        int hash = (key == null) ? 0 : hash(key);
+        if (key == null) {
+            if (nullKeyEntry != null) {
+                return removeNullKey();
+            }            
+            return null;
+        }
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+
+        if (table[i] instanceof Entry) {
         @SuppressWarnings("unchecked")
             Entry<K,V> prev = (Entry<K,V>)table[i];
         Entry<K,V> e = prev;
 
         while (e != null) {
-            Entry<K,V> next = e.next;
-            Object k;
-            if (e.hash == hash &&
-                ((k = e.key) == key || (key != null && key.equals(k)))) {
+                @SuppressWarnings("unchecked")            
+                Entry<K,V> next = (Entry<K,V>) e.next;
+                if (e.hash == hash && Objects.equals(e.key, key)) {
                 modCount++;
                 size--;
                 if (prev == e)
                     table[i] = next;
                 else

@@ -899,12 +1902,30 @@
                 return e;
             }
             prev = e;
             e = next;
         }
-
-        return e;
+        } else if (table[i] != null) {
+            TreeBin tb = ((TreeBin) table[i]);
+            TreeNode p = tb.getTreeNode(hash, (K)key);
+            if (p != null) {
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;
+                // assert pEntry.key.equals(key);
+                modCount++;
+                size--;
+                tb.deleteTreeNode(p);
+                pEntry.recordRemoval(this);
+                if (tb.root == null || tb.first == null) {
+                    // assert tb.root == null && tb.first == null :
+                    //             "TreeBin.first and root should both be null";
+                    // TreeBin is now empty, we should blank this bin
+                    table[i] = null;
+                }
+                return pEntry;
+            }
+        }
+        return null;
     }
 
     /**
      * Special version of remove for EntrySet using {@code Map.Entry.equals()}
      * for matching.

@@ -913,18 +1934,29 @@
         if (isEmpty() || !(o instanceof Map.Entry))
             return null;
 
         Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
         Object key = entry.getKey();
-        int hash = (key == null) ? 0 : hash(key);
+        
+        if (key == null) {
+            if (entry.equals(nullKeyEntry)) {
+                return removeNullKey();
+            }
+            return null;
+        }        
+        
+        int hash = hash(key);
         int i = indexFor(hash, table.length);
+
+        if (table[i] instanceof Entry) {
         @SuppressWarnings("unchecked")
             Entry<K,V> prev = (Entry<K,V>)table[i];
         Entry<K,V> e = prev;
 
         while (e != null) {
-            Entry<K,V> next = e.next;
+                @SuppressWarnings("unchecked")
+                Entry<K,V> next = (Entry<K,V>)e.next;
             if (e.hash == hash && e.equals(entry)) {
                 modCount++;
                 size--;
                 if (prev == e)
                     table[i] = next;

@@ -934,20 +1966,58 @@
                 return e;
             }
             prev = e;
             e = next;
         }
+        } else if (table[i] != null) {
+            TreeBin tb = ((TreeBin) table[i]);
+            TreeNode p = tb.getTreeNode(hash, (K)key);
+            if (p != null && p.entry.equals(entry)) {
+                @SuppressWarnings("unchecked")
+                Entry<K,V> pEntry = (Entry<K,V>)p.entry;                
+                // assert pEntry.key.equals(key);
+                modCount++;
+                size--;
+                tb.deleteTreeNode(p);
+                pEntry.recordRemoval(this);
+                if (tb.root == null || tb.first == null) {
+                    // assert tb.root == null && tb.first == null :
+                    //             "TreeBin.first and root should both be null";
+                    // TreeBin is now empty, we should blank this bin
+                    table[i] = null;
+                }
+                return pEntry;
+            }
+        }
+        return null;
+    }
 
-        return e;
+    /*
+     * Remove the mapping for the null key, and update internal accounting
+     * (size, modcount, recordRemoval, etc).
+     * 
+     * Assumes nullKeyEntry is non-null.
+     */
+    private Entry<K,V> removeNullKey() {
+        // assert nullKeyEntry != null;
+        Entry<K,V> retVal = nullKeyEntry;
+        modCount++;
+        size--;
+        retVal.recordRemoval(this);                            
+        nullKeyEntry = null;
+        return retVal;        
     }
 
     /**
      * Removes all of the mappings from this map.
      * The map will be empty after this call returns.
      */
     public void clear() {
         modCount++;
+        if (nullKeyEntry != null) {
+            nullKeyEntry = null;
+        }                        
         Arrays.fill(table, null);
         size = 0;
     }
 
     /**

@@ -957,31 +2027,62 @@
      * @param value value whose presence in this map is to be tested
      * @return <tt>true</tt> if this map maps one or more keys to the
      *         specified value
      */
     public boolean containsValue(Object value) {
-        if (value == null)
+        if (value == null) {
             return containsNullValue();
-
-        Entry<?,?>[] tab = table;
-        for (int i = 0; i < tab.length; i++)
-            for (Entry<?,?> e = tab[i]; e != null; e = e.next)
-                if (value.equals(e.value))
+        }        
+        Object[] tab = table;
+        for (int i = 0; i < tab.length; i++) {
+            if (tab[i] instanceof Entry) {
+                Entry<?,?> e = (Entry<?,?>)tab[i];
+                for (; e != null; e = (Entry<?,?>)e.next) {
+                    if (value.equals(e.value)) {
+                        return true;
+                    }
+                }                
+            } else if (tab[i] != null) {
+                TreeBin e = (TreeBin)tab[i];
+                TreeNode p = e.first;
+                for (; p != null; p = (TreeNode) p.entry.next) {
+                    if (value == p.entry.value || value.equals(p.entry.value)) {
                     return true;
-        return false;
+                    }
+                }
+            }
+        }
+        // Didn't find value in table - could be in nullKeyEntry
+        return (nullKeyEntry != null && (value == nullKeyEntry.value ||
+                                         value.equals(nullKeyEntry.value)));
     }
 
     /**
      * Special-case code for containsValue with null argument
      */
     private boolean containsNullValue() {
-        Entry<?,?>[] tab = table;
-        for (int i = 0; i < tab.length; i++)
-            for (Entry<?,?> e = tab[i]; e != null; e = e.next)
-                if (e.value == null)
+        Object[] tab = table;
+        for (int i = 0; i < tab.length; i++) {
+            if (tab[i] instanceof Entry) {
+                Entry<K,V> e = (Entry<K,V>)tab[i];                
+                for (; e != null; e = (Entry<K,V>)e.next) {
+                    if (e.value == null) {
+                        return true;
+                    }
+                }            
+            } else if (tab[i] != null) {
+                TreeBin e = (TreeBin)tab[i];
+                TreeNode p = e.first;
+                for (; p != null; p = (TreeNode) p.entry.next) {
+                    if (p.entry.value == null) {
                     return true;
-        return false;
+                    }
+                }
+            }
+        }
+        // Didn't find value in table - could be in nullKeyEntry
+        return (nullKeyEntry != null && nullKeyEntry.value == null);
     }
 
     /**
      * Returns a shallow copy of this <tt>HashMap</tt> instance: the keys and
      * values themselves are not cloned.

@@ -1005,26 +2106,27 @@
                 table.length));
         }
         result.entrySet = null;
         result.modCount = 0;
         result.size = 0;
+        result.nullKeyEntry = null;
         result.init();
         result.putAllForCreate(this);
 
         return result;
     }
 
     static class Entry<K,V> implements Map.Entry<K,V> {
         final K key;
         V value;
-        Entry<K,V> next;
+        Object next; // an Entry, or a TreeNode
         final int hash;
 
         /**
          * Creates new entry.
          */
-        Entry(int h, K k, V v, Entry<K,V> n) {
+        Entry(int h, K k, V v, Object n) {
             value = v;
             next = n;
             key = k;
             hash = h;
         }

@@ -1066,12 +2168,11 @@
             return getKey() + "=" + getValue();
         }
 
         /**
          * This method is invoked whenever the value in an entry is
-         * overwritten by an invocation of put(k,v) for a key k that's already
-         * in the HashMap.
+         * overwritten for a key that's already in the HashMap.
          */
         void recordAccess(HashMap<K,V> m) {
         }
 
         /**

@@ -1080,88 +2181,165 @@
          */
         void recordRemoval(HashMap<K,V> m) {
         }
     }
 
+    void addEntry(int hash, K key, V value, int bucketIndex) {
+        addEntry(hash, key, value, bucketIndex, true);
+    }
+    
     /**
      * Adds a new entry with the specified key, value and hash code to
      * the specified bucket.  It is the responsibility of this
-     * method to resize the table if appropriate.
+     * method to resize the table if appropriate.  The new entry is then 
+     * created by calling createEntry().
      *
      * Subclass overrides this to alter the behavior of put method.
+     *
+     * If checkIfNeedTree is false, it is known that this bucket will not need
+     * to be converted to a TreeBin, so don't bothering checking.
+     * 
+     * Assumes key is not null.
      */
-    void addEntry(int hash, K key, V value, int bucketIndex) {
+    void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
+        // assert key != null;
         if ((size >= threshold) && (null != table[bucketIndex])) {
             resize(2 * table.length);
-            hash = (null != key) ? hash(key) : 0;
+            hash = hash(key);
             bucketIndex = indexFor(hash, table.length);
         }
-
-        createEntry(hash, key, value, bucketIndex);
+        createEntry(hash, key, value, bucketIndex, checkIfNeedTree);
     }
 
     /**
-     * Like addEntry except that this version is used when creating entries
+     * Called by addEntry(), and also used when creating entries
      * as part of Map construction or "pseudo-construction" (cloning,
-     * deserialization).  This version needn't worry about resizing the table.
+     * deserialization).  This version does not check for resizing of the table.
+     *
+     * This method is responsible for converting a bucket to a TreeBin once
+     * TREE_THRESHOLD is reached. However if checkIfNeedTree is false, it is known
+     * that this bucket will not need to be converted to a TreeBin, so don't
+     * bother checking.  The new entry is constructed by calling newEntry().
      *
-     * Subclass overrides this to alter the behavior of HashMap(Map),
-     * clone, and readObject.
+     * Assumes key is not null.
+     *
+     * Note: buckets already converted to a TreeBin don't call this method, but
+     * instead call TreeBin.putTreeNode() to create new entries.
      */
-    void createEntry(int hash, K key, V value, int bucketIndex) {
+    void createEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) {
+        // assert key != null;
         @SuppressWarnings("unchecked")
             Entry<K,V> e = (Entry<K,V>)table[bucketIndex];
-        table[bucketIndex] = new Entry<>(hash, key, value, e);
+        table[bucketIndex] = newEntry(hash, key, value, e);         
         size++;
+
+        if (checkIfNeedTree) {
+            int listSize = 0;
+            for (e = (Entry<K,V>) table[bucketIndex]; e != null; e = (Entry<K,V>)e.next) {
+                listSize++;
+                if (listSize >= TreeBin.TREE_THRESHOLD) { // Convert to TreeBin
+                    if (comparableClassFor(key) != null) {
+                        TreeBin t = new TreeBin();
+                        t.populate((Entry)table[bucketIndex]);
+                        table[bucketIndex] = t;
+                    }
+                    break;
     }
+            }
+        }
+    }
+   
+    /*
+     * Factory method to create a new Entry object.
+     */
+    Entry<K,V> newEntry(int hash, K key, V value, Object next) {
+        return new HashMap.Entry<>(hash, key, value, next);
+    }
+
 
     private abstract class HashIterator<E> implements Iterator<E> {
-        Entry<?,?> next;        // next entry to return
+        Object next;            // next entry to return, an Entry or a TreeNode
         int expectedModCount;   // For fast-fail
         int index;              // current slot
-        Entry<?,?> current;     // current entry
+        Object current;         // current entry, an Entry or a TreeNode
 
         HashIterator() {
             expectedModCount = modCount;
             if (size > 0) { // advance to first entry
-                Entry<?,?>[] t = table;
-                while (index < t.length && (next = t[index++]) == null)
-                    ;
+                if (nullKeyEntry != null) {
+                    // assert nullKeyEntry.next == null;
+                    // This works with nextEntry(): nullKeyEntry isa Entry, and
+                    // e.next will be null, so we'll hit the findNextBin() call.                    
+                    next = nullKeyEntry;
+                } else {                
+                    findNextBin();
+                }
             }
         }
 
         public final boolean hasNext() {
             return next != null;
         }
 
         @SuppressWarnings("unchecked")
         final Entry<K,V> nextEntry() {
-            if (modCount != expectedModCount)
+            if (modCount != expectedModCount) {
                 throw new ConcurrentModificationException();
-            Entry<?,?> e = next;
+            }
+            Object e = next;
+            Entry<K,V> retVal;
+            
             if (e == null)
                 throw new NoSuchElementException();
 
-            if ((next = e.next) == null) {
-                Entry<?,?>[] t = table;
-                while (index < t.length && (next = t[index++]) == null)
-                    ;
+            if (e instanceof Entry) {
+                retVal = (Entry<K,V>)e;
+                next = ((Entry<K,V>)e).next;                
+            } else { // TreeBin
+                retVal = (Entry<K,V>)((TreeNode)e).entry;
+                next = retVal.next;                
+            }
+            
+            if (next == null) { // Move to next bin
+                findNextBin();
             }
             current = e;
-            return (Entry<K,V>)e;
+            return retVal;
         }
 
         public void remove() {
             if (current == null)
                 throw new IllegalStateException();
             if (modCount != expectedModCount)
                 throw new ConcurrentModificationException();
-            Object k = current.key;
+            K k;
+            
+            if (current instanceof Entry) {
+                k = ((Entry<K,V>)current).key;
+            } else {
+                k = ((Entry<K,V>)((TreeNode)current).entry).key;
+                
+            }                        
             current = null;
             HashMap.this.removeEntryForKey(k);
             expectedModCount = modCount;
         }
+
+        /*
+         * Set 'next' to the first entry of the next non-empty bin in the table
+         */
+        private void findNextBin() {
+            // assert next == null;
+            Object[] t = table;
+            
+            while (index < t.length && (next = t[index++]) == null)
+                ;
+            if (next instanceof HashMap.TreeBin) { // Point to the first TreeNode
+                next = ((TreeBin) next).first;
+                // assert next != null; // There should be no empty TreeBins
+            }
+        }
     }
 
     private final class ValueIterator extends HashIterator<V> {
         public V next() {
             return nextEntry().value;

@@ -1387,12 +2565,14 @@
             throw new InvalidObjectException("Illegal load factor: " +
                                                loadFactor);
         }
 
         // set other fields that need values
+        if (Holder.USE_HASHSEED) {
         Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
                 sun.misc.Hashing.randomHashSeed(this));
+        }
         table = EMPTY_TABLE;
 
         // Read in number of buckets
         s.readInt(); // ignored.
 

@@ -1434,24 +2614,31 @@
     /**
      * Standin until HM overhaul; based loosely on Weak and Identity HM.
      */
     static class HashMapSpliterator<K,V> {
         final HashMap<K,V> map;
-        HashMap.Entry<K,V> current; // current node
+        Object current;             // current node, can be Entry or TreeNode
         int index;                  // current index, modified on advance/split
         int fence;                  // one past last index
         int est;                    // size estimate
         int expectedModCount;       // for comodification checks
+        boolean acceptedNull;       // Have we accepted the null key?
+                                    // Without this, we can't distinguish
+                                    // between being at the very beginning (and
+                                    // needing to accept null), or being at the
+                                    // end of the list in bin 0.  In both cases,
+                                    // current == null && index == 0.
 
         HashMapSpliterator(HashMap<K,V> m, int origin,
                                int fence, int est,
                                int expectedModCount) {
             this.map = m;
             this.index = origin;
             this.fence = fence;
             this.est = est;
             this.expectedModCount = expectedModCount;
+            this.acceptedNull = false;
         }
 
         final int getFence() { // initialize fence and size on first use
             int hi;
             if ((hi = fence) < 0) {

@@ -1477,36 +2664,58 @@
             super(m, origin, fence, est, expectedModCount);
         }
 
         public KeySpliterator<K,V> trySplit() {
             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
-            return (lo >= mid || current != null) ? null :
-                new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
-                                        expectedModCount);
+            if (lo >= mid || current != null) {
+                return null;
+            } else {
+                KeySpliterator<K,V> retVal = new KeySpliterator<K,V>(map, lo,
+                                     index = mid, est >>>= 1, expectedModCount);
+                // Only 'this' Spliterator chould check for null.
+                retVal.acceptedNull = true;
+                return retVal;
+            }
         }
 
         @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super K> action) {
             int i, hi, mc;
             if (action == null)
                 throw new NullPointerException();
             HashMap<K,V> m = map;
-            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+            Object[] tab = m.table;
             if ((hi = fence) < 0) {
                 mc = expectedModCount = m.modCount;
                 hi = fence = tab.length;
             }
             else
                 mc = expectedModCount;
+
+            if (!acceptedNull) {                
+                acceptedNull = true;
+                if (m.nullKeyEntry != null) {
+                    action.accept(m.nullKeyEntry.key);
+                }
+            }
             if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
-                HashMap.Entry<K,V> p = current;
+                Object p = current;
                 do {
-                    if (p == null)
+                    if (p == null) {
                         p = tab[i++];
-                    else {
-                        action.accept(p.getKey());
-                        p = p.next;
+                        if (p instanceof HashMap.TreeBin) {
+                            p = ((HashMap.TreeBin)p).first;
+                        }
+                    } else {
+                        HashMap.Entry<K,V> entry;
+                        if (p instanceof HashMap.Entry) {
+                            entry = (HashMap.Entry<K,V>)p;
+                        } else {
+                            entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
+                        }
+                        action.accept(entry.key);
+                        p = entry.next;                        
                     }
                 } while (p != null || i < hi);
                 if (m.modCount != mc)
                     throw new ConcurrentModificationException();
             }

@@ -1515,18 +2724,38 @@
         @SuppressWarnings("unchecked")
         public boolean tryAdvance(Consumer<? super K> action) {
             int hi;
             if (action == null)
                 throw new NullPointerException();
-            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
-            if (tab.length >= (hi = getFence()) && index >= 0) {
+            Object[] tab = map.table;
+            hi = getFence();
+
+            if (!acceptedNull) {                
+                acceptedNull = true;
+                if (map.nullKeyEntry != null) {
+                    action.accept(map.nullKeyEntry.key);
+                    if (map.modCount != expectedModCount)
+                        throw new ConcurrentModificationException();                    
+                    return true;
+                }
+            }
+            if (tab.length >= hi && index >= 0) {
                 while (current != null || index < hi) {
-                    if (current == null)
+                    if (current == null) {
                         current = tab[index++];
-                    else {
-                        K k = current.getKey();
-                        current = current.next;
+                        if (current instanceof HashMap.TreeBin) {
+                            current = ((HashMap.TreeBin)current).first;
+                        }
+                    } else {
+                        HashMap.Entry<K,V> entry;
+                        if (current instanceof HashMap.Entry) {
+                            entry = (HashMap.Entry<K,V>)current;                            
+                        } else {
+                            entry = (HashMap.Entry<K,V>)((TreeNode)current).entry;
+                        }
+                        K k = entry.key;
+                        current = entry.next;
                         action.accept(k);
                         if (map.modCount != expectedModCount)
                             throw new ConcurrentModificationException();
                         return true;
                     }

@@ -1549,36 +2778,58 @@
             super(m, origin, fence, est, expectedModCount);
         }
 
         public ValueSpliterator<K,V> trySplit() {
             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
-            return (lo >= mid || current != null) ? null :
-                new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
-                                          expectedModCount);
+            if (lo >= mid || current != null) {
+                return null;
+            } else {
+                ValueSpliterator<K,V> retVal = new ValueSpliterator<K,V>(map,
+                                 lo, index = mid, est >>>= 1, expectedModCount);
+                // Only 'this' Spliterator chould check for null.
+                retVal.acceptedNull = true;
+                return retVal;
+            }
         }
 
         @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super V> action) {
             int i, hi, mc;
             if (action == null)
                 throw new NullPointerException();
             HashMap<K,V> m = map;
-            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+            Object[] tab = m.table;
             if ((hi = fence) < 0) {
                 mc = expectedModCount = m.modCount;
                 hi = fence = tab.length;
             }
             else
                 mc = expectedModCount;
+            
+            if (!acceptedNull) {                
+                acceptedNull = true;
+                if (m.nullKeyEntry != null) {
+                    action.accept(m.nullKeyEntry.value);
+                }
+            }
             if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
-                HashMap.Entry<K,V> p = current;
+                Object p = current;
                 do {
-                    if (p == null)
+                    if (p == null) {
                         p = tab[i++];
-                    else {
-                        action.accept(p.getValue());
-                        p = p.next;
+                        if (p instanceof HashMap.TreeBin) {
+                            p = ((HashMap.TreeBin)p).first;
+                        }                        
+                    } else {
+                        HashMap.Entry<K,V> entry;
+                        if (p instanceof HashMap.Entry) {
+                            entry = (HashMap.Entry<K,V>)p;
+                        } else {
+                            entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
+                        }
+                        action.accept(entry.value);
+                        p = entry.next;
                     }
                 } while (p != null || i < hi);
                 if (m.modCount != mc)
                     throw new ConcurrentModificationException();
             }

@@ -1587,18 +2838,38 @@
         @SuppressWarnings("unchecked")
         public boolean tryAdvance(Consumer<? super V> action) {
             int hi;
             if (action == null)
                 throw new NullPointerException();
-            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
-            if (tab.length >= (hi = getFence()) && index >= 0) {
+            Object[] tab = map.table;
+            hi = getFence();
+            
+            if (!acceptedNull) {                
+                acceptedNull = true;
+                if (map.nullKeyEntry != null) {
+                    action.accept(map.nullKeyEntry.value);
+                    if (map.modCount != expectedModCount)
+                        throw new ConcurrentModificationException();                    
+                    return true;
+                }
+            }                        
+            if (tab.length >= hi && index >= 0) {
                 while (current != null || index < hi) {
-                    if (current == null)
+                    if (current == null) {
                         current = tab[index++];
-                    else {
-                        V v = current.getValue();
-                        current = current.next;
+                        if (current instanceof HashMap.TreeBin) {
+                            current = ((HashMap.TreeBin)current).first;
+                        }
+                    } else {
+                        HashMap.Entry<K,V> entry;
+                        if (current instanceof HashMap.Entry) {
+                            entry = (Entry<K,V>)current;                            
+                        } else {
+                            entry = (Entry<K,V>)((TreeNode)current).entry;
+                        }
+                        V v = entry.value;
+                        current = entry.next;
                         action.accept(v);
                         if (map.modCount != expectedModCount)
                             throw new ConcurrentModificationException();
                         return true;
                     }

@@ -1620,36 +2891,59 @@
             super(m, origin, fence, est, expectedModCount);
         }
 
         public EntrySpliterator<K,V> trySplit() {
             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
-            return (lo >= mid || current != null) ? null :
-                new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
-                                          expectedModCount);
+            if (lo >= mid || current != null) {
+                return null;
+            } else {
+                EntrySpliterator<K,V> retVal = new EntrySpliterator<K,V>(map,
+                                 lo, index = mid, est >>>= 1, expectedModCount);
+                // Only 'this' Spliterator chould check for null.
+                retVal.acceptedNull = true;
+                return retVal;
+            }
         }
 
         @SuppressWarnings("unchecked")
         public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
             int i, hi, mc;
             if (action == null)
                 throw new NullPointerException();
             HashMap<K,V> m = map;
-            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+            Object[] tab = m.table;
             if ((hi = fence) < 0) {
                 mc = expectedModCount = m.modCount;
                 hi = fence = tab.length;
             }
             else
                 mc = expectedModCount;
+            
+            if (!acceptedNull) {                
+                acceptedNull = true;
+                if (m.nullKeyEntry != null) {
+                    action.accept(m.nullKeyEntry);
+                }
+            }
             if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
-                HashMap.Entry<K,V> p = current;
+                Object p = current;
                 do {
-                    if (p == null)
+                    if (p == null) {
                         p = tab[i++];
-                    else {
-                        action.accept(p);
-                        p = p.next;
+                        if (p instanceof HashMap.TreeBin) {
+                            p = ((HashMap.TreeBin)p).first;
+                        }                        
+                    } else {
+                        HashMap.Entry<K,V> entry;
+                        if (p instanceof HashMap.Entry) {
+                            entry = (HashMap.Entry<K,V>)p;
+                        } else {
+                            entry = (HashMap.Entry<K,V>)((TreeNode)p).entry;
+                        }
+                        action.accept(entry);
+                        p = entry.next;                           
+                        
                     }
                 } while (p != null || i < hi);
                 if (m.modCount != mc)
                     throw new ConcurrentModificationException();
             }

@@ -1658,18 +2952,37 @@
         @SuppressWarnings("unchecked")
         public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
             int hi;
             if (action == null)
                 throw new NullPointerException();
-            HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
-            if (tab.length >= (hi = getFence()) && index >= 0) {
+            Object[] tab = map.table;
+            hi = getFence();
+            
+            if (!acceptedNull) {                
+                acceptedNull = true;
+                if (map.nullKeyEntry != null) {
+                    action.accept(map.nullKeyEntry);
+                    if (map.modCount != expectedModCount)
+                        throw new ConcurrentModificationException();                    
+                    return true;
+                }
+            }
+            if (tab.length >= hi && index >= 0) {
                 while (current != null || index < hi) {
-                    if (current == null)
+                    if (current == null) {
                         current = tab[index++];
-                    else {
-                        HashMap.Entry<K,V> e = current;
-                        current = current.next;
+                        if (current instanceof HashMap.TreeBin) {
+                            current = ((HashMap.TreeBin)current).first;
+                        }                        
+                    } else {
+                        HashMap.Entry<K,V> e;
+                        if (current instanceof HashMap.Entry) {
+                            e = (Entry<K,V>)current;                            
+                        } else {
+                            e = (Entry<K,V>)((TreeNode)current).entry;
+                        }                        
+                        current = e.next;                        
                         action.accept(e);
                         if (map.modCount != expectedModCount)
                             throw new ConcurrentModificationException();
                         return true;
                     }