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

Print this page

        

@@ -128,10 +128,19 @@
 public class HashMap<K,V>
     extends AbstractMap<K,V>
     implements Map<K,V>, Cloneable, Serializable
 {
 
+    /*
+     * 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.
+     */
+
     /**
      * The default initial capacity - MUST be a power of two.
      */
     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
 

@@ -148,16 +157,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,38 +193,39 @@
      * rehash).  This field is used to make iterators on Collection-views of
      * the HashMap fail-fast.  (See ConcurrentModificationException).
      */
     transient int modCount;
 
-    private static class Holder {
          /**
-         *
+    * Holds values which can't be initialized until after VM is booted.
          */
-        static final sun.misc.Unsafe UNSAFE;
-
-        /**
-         * Offset of "final" hashSeed field we must set in
-         * readObject() method.
-         */
-        static final long HASHSEED_OFFSET;
+    private static class Holder {
+        static final boolean USE_HASHSEED;
 
         static {
-            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);
-            }
+            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;
         }
     }
 
-    /**
+    /*
      * 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 int hashSeed = 0;
+
+    /*
+     * TreeBin/TreeNode code from CHM doesn't handle the null key.  Store the
+     * null key entry here.
      */
-    transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);
+    transient Entry<K,V> nullKeyEntry = null;
 
     /**
      * Constructs an empty <tt>HashMap</tt> with the specified initial
      * capacity and load factor.
      *

@@ -231,13 +241,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;
+        initHashSeed();
         init();
     }
 
     /**
      * Constructs an empty <tt>HashMap</tt> with the specified initial

@@ -271,10 +281,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 +303,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 +319,28 @@
      */
     void init() {
     }
 
     /**
+     * Initialize the hashing mask value.
+     */
+    final void initHashSeed() {
+        if (sun.misc.VM.isBooted() && Holder.USE_HASHSEED) {
+            // Do not set hashSeed more than once!
+            // assert hashSeed == 0;
+            hashSeed = sun.misc.Hashing.randomHashSeed(this);
+        }        
+    }    
+    
+    /**
      * 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,22 +425,38 @@
     @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, 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 +466,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 +619,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(this);
+                TreeBin hiTree = new TreeBin(this);
+                e.splitTreeBin(newTable, j, loTree, hiTree);
+            }
         }
         Arrays.fill(table, null);
     }
 
     /**

@@ -619,44 +726,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++;
+                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);
+        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 +819,230 @@
                 return true;
             }
             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);
+                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;
+        } 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);
         }
-        int hash = (key == null) ? 0 : hash(key);
+        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 = e.next) {
+            for (; e != null; e = (Entry<K,V>)e.next) {
             if (e.hash == hash && Objects.equals(e.key, key)) {
                 V oldValue = e.value;
-                return oldValue == null ? (e.value = mappingFunction.apply(key)) : oldValue;
+                    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;
+                    }
+                    return oldVal;
+                }
             }
         }
-
         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 +1054,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 +1135,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 +1231,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 +1327,30 @@
                 return e;
             }
             prev = e;
             e = next;
         }
-
-        return e;
+        } 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);
+                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 +1359,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 +1391,58 @@
                 return e;
             }
             prev = e;
             e = next;
         }
+        } else if (table[i] != null) {
+            TreeBin tb = ((TreeBin) table[i]);
+            TreeNode p = tb.getTreeNode(hash, 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 +1452,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;
-        return false;
+                    }
+                }                
+            } 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;
+                    }
+                }
+            }
+        }
+        // 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;
-        return false;
+                    }
+                }            
+            } 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;
+                    }
+                }
+            }
+        }
+        // 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 +1531,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 +1593,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 +1606,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().
+     *
+     * Assumes key is not null.
      *
-     * Subclass overrides this to alter the behavior of HashMap(Map),
-     * clone, and readObject.
+     * 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 (TreeBin.comparableClassFor(key) != null) {
+                        TreeBin t = new TreeBin(this);
+                        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 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 +1990,10 @@
             throw new InvalidObjectException("Illegal load factor: " +
                                                loadFactor);
         }
 
         // set other fields that need values
-        Holder.UNSAFE.putIntVolatile(this, Holder.HASHSEED_OFFSET,
-                sun.misc.Hashing.randomHashSeed(this));
         table = EMPTY_TABLE;
 
         // Read in number of buckets
         s.readInt(); // ignored.
 

@@ -1413,10 +2014,11 @@
             inflateTable(capacity);
         } else {
             threshold = capacity;
         }
 
+        initHashSeed();
         init();  // Give subclass a chance to do its thing.
 
         // Read the keys and values, and put the mappings in the HashMap
         for (int i=0; i<mappings; i++) {
             @SuppressWarnings("unchecked")

@@ -1434,24 +2036,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 +2086,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 TreeBin) {
+                            p = ((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 +2146,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 TreeBin) {
+                            current = ((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 +2200,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 TreeBin) {
+                            p = ((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 +2260,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 TreeBin) {
+                            current = ((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 +2313,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 TreeBin) {
+                            p = ((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 +2374,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 TreeBin) {
+                            current = ((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;
                     }