Replace LongObjectHashMap with a more efficient implementation

After further testing it appears that while the original LongHashtable
has issues with object creation churn and is severly slower than even
java.util.HashMap in general case benchmarks it is in fact very efficient
for our use case.

With this in mind I wrote a replacement LongObjectHashMap modeled after
LongHashtable. Unlike the original implementation this one does not use
Entry objects for storage so does not have the same object creation churn.
It also uses a 2D array instead of a 3D one and does not use a cache as
benchmarking shows this is more efficient. The "bucket size" was chosen
based on benchmarking performance of the HashMap with contents that would
be plausible for a 200+ player server. This means it uses a little extra
memory for smaller servers but almost always uses less than the normal
java.util.HashMap.

To make up for the original LongHashtable being a poor choice for generic
datasets I added a mixer to the new implementation based on code from
MurmurHash. While this has no noticable effect positive or negative with
our normal use of chunk coordinates it makes the HashMap perform just as
well with nearly any kind of dataset.

After these changes ChunkProviderServer.isChunkLoaded() goes from using
20% CPU time while sampling to not even showing up after 45 minutes of
sampling due to the CPU usage being too low to be noticed.

4 files changed, 290 insertions, 401 deletions

diff --git a/src/main/java/net/minecraft/server/ChunkProviderServer.java b/src/main/java/net/minecraft/server/ChunkProviderServer.java
index 72701d16..a9d0567d 100644
--- a/src/main/java/net/minecraft/server/ChunkProviderServer.java
+++ b/src/main/java/net/minecraft/server/ChunkProviderServer.java
@@ -11,6 +11,7 @@ import java.util.Set;
 import java.util.Random;
 
 import org.bukkit.Server;
+import org.bukkit.craftbukkit.util.LongHash;
 import org.bukkit.craftbukkit.util.LongHashSet;
 import org.bukkit.craftbukkit.util.LongObjectHashMap;
 import org.bukkit.event.world.ChunkUnloadEvent;
@@ -36,7 +37,7 @@ public class ChunkProviderServer implements IChunkProvider {
     }
 
     public boolean isChunkLoaded(int i, int j) {
-        return this.chunks.containsKey(i, j); // CraftBukkit
+        return this.chunks.containsKey(LongHash.toLong(i, j)); // CraftBukkit
     }
 
     public void queueUnload(int i, int j) {
@@ -50,7 +51,7 @@ public class ChunkProviderServer implements IChunkProvider {
             if (k < -short1 || k > short1 || l < -short1 || l > short1 || !(this.world.keepSpawnInMemory)) { // Added 'this.world.keepSpawnInMemory'
                 this.unloadQueue.add(i, j);
 
-                Chunk c = this.chunks.get(i, j);
+                Chunk c = this.chunks.get(LongHash.toLong(i, j));
                 if (c != null) {
                     c.mustSave = true;
                 }
@@ -60,7 +61,7 @@ public class ChunkProviderServer implements IChunkProvider {
             // CraftBukkit start
             this.unloadQueue.add(i, j);
 
-            Chunk c = this.chunks.get(i, j);
+            Chunk c = this.chunks.get(LongHash.toLong(i, j));
             if (c != null) {
                 c.mustSave = true;
             }
@@ -81,7 +82,7 @@ public class ChunkProviderServer implements IChunkProvider {
     public Chunk getChunkAt(int i, int j) {
         // CraftBukkit start
         this.unloadQueue.remove(i, j);
-        Chunk chunk = (Chunk) this.chunks.get(i, j);
+        Chunk chunk = (Chunk) this.chunks.get(LongHash.toLong(i, j));
         boolean newChunk = false;
         // CraftBukkit end
 
@@ -96,7 +97,7 @@ public class ChunkProviderServer implements IChunkProvider {
                 newChunk = true; // CraftBukkit
             }
 
-            this.chunks.put(i, j, chunk); // CraftBukkit
+            this.chunks.put(LongHash.toLong(i, j), chunk); // CraftBukkit
             if (chunk != null) {
                 chunk.addEntities();
             }
@@ -121,7 +122,7 @@ public class ChunkProviderServer implements IChunkProvider {
 
     public Chunk getOrCreateChunk(int i, int j) {
         // CraftBukkit start
-        Chunk chunk = (Chunk) this.chunks.get(i, j);
+        Chunk chunk = (Chunk) this.chunks.get(LongHash.toLong(i, j));
 
         chunk = chunk == null ? (!this.world.isLoading && !this.forceChunkLoad ? this.emptyChunk : this.getChunkAt(i, j)) : chunk;
         if (chunk == this.emptyChunk) return chunk;
diff --git a/src/main/java/net/minecraft/server/SpawnerCreature.java b/src/main/java/net/minecraft/server/SpawnerCreature.java
index c9870fd1..efde3f71 100644
--- a/src/main/java/net/minecraft/server/SpawnerCreature.java
+++ b/src/main/java/net/minecraft/server/SpawnerCreature.java
@@ -7,14 +7,14 @@ import java.util.List;
 import java.util.Random;
 
 // CraftBukkit start
-import org.bukkit.craftbukkit.util.LongObjectHashMap;
 import org.bukkit.craftbukkit.util.LongHash;
+import org.bukkit.craftbukkit.util.LongObjectHashMap;
 import org.bukkit.event.entity.CreatureSpawnEvent.SpawnReason;
 // CraftBukkit end
 
 public final class SpawnerCreature {
 
-    private static LongObjectHashMap b = new LongObjectHashMap(); // CraftBukkit - HashMap -> LongObjectHashMap
+    private static LongObjectHashMap<Boolean> b = new LongObjectHashMap<Boolean>(); // CraftBukkit - HashMap -> LongObjectHashMap
     protected static final Class[] a = new Class[] { EntitySpider.class, EntityZombie.class, EntitySkeleton.class};
 
     protected static ChunkPosition getRandomPosition(World world, int i, int j) {
@@ -95,7 +95,7 @@ public final class SpawnerCreature {
                         // CraftBukkit start
                         long key = ((Long) iterator.next()).longValue();
 
-                        if (!((Boolean) b.get(key)).booleanValue()) {
+                        if (!b.get(key)) {
                             ChunkPosition chunkposition = getRandomPosition(worldserver, LongHash.msw(key), LongHash.lsw(key));
                             // CraftBukkit end
                             int k1 = chunkposition.x;
diff --git a/src/main/java/org/bukkit/craftbukkit/CraftWorld.java b/src/main/java/org/bukkit/craftbukkit/CraftWorld.java
index eb6695b6..41f0935b 100644
--- a/src/main/java/org/bukkit/craftbukkit/CraftWorld.java
+++ b/src/main/java/org/bukkit/craftbukkit/CraftWorld.java
@@ -45,6 +45,7 @@ import org.bukkit.Sound;
 import org.bukkit.craftbukkit.block.CraftBlock;
 import org.bukkit.craftbukkit.inventory.CraftItemStack;
 import org.bukkit.plugin.messaging.StandardMessenger;
+import org.bukkit.craftbukkit.util.LongHash;
 
 public class CraftWorld implements World {
     private final WorldServer world;
@@ -174,7 +175,7 @@ public class CraftWorld implements World {
         }
 
         world.chunkProviderServer.unloadQueue.remove(x, z);
-        world.chunkProviderServer.chunks.remove(x, z);
+        world.chunkProviderServer.chunks.remove(LongHash.toLong(x, z));
 
         return true;
     }
@@ -230,7 +231,7 @@ public class CraftWorld implements World {
         }
 
         world.chunkProviderServer.unloadQueue.remove(x, z);
-        net.minecraft.server.Chunk chunk = (net.minecraft.server.Chunk) world.chunkProviderServer.chunks.get(x, z);
+        net.minecraft.server.Chunk chunk = (net.minecraft.server.Chunk) world.chunkProviderServer.chunks.get(LongHash.toLong(x, z));
 
         if (chunk == null) {
             chunk = world.chunkProviderServer.loadChunk(x, z);
@@ -243,7 +244,7 @@ public class CraftWorld implements World {
     @SuppressWarnings("unchecked")
     private void chunkLoadPostProcess(net.minecraft.server.Chunk chunk, int x, int z) {
         if (chunk != null) {
-            world.chunkProviderServer.chunks.put(x, z, chunk);
+            world.chunkProviderServer.chunks.put(LongHash.toLong(x, z), chunk);
 
             chunk.addEntities();
 
diff --git a/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java b/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java
index 34cc0a6e..01861ccf 100644
--- a/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java
+++ b/src/main/java/org/bukkit/craftbukkit/util/LongObjectHashMap.java
@@ -1,138 +1,185 @@
-/*
-Based on OpenLongObjectHashMap from colt. Original copyright follows:
-
-Copyright © 1999 CERN - European Organization for Nuclear Research.
-Permission to use, copy, modify, distribute and sell this software and its documentation for any purpose
-is hereby granted without fee, provided that the above copyright notice appear in all copies and
-that both that copyright notice and this permission notice appear in supporting documentation.
-CERN makes no representations about the suitability of this software for any purpose.
-It is provided "as is" without expressed or implied warranty.
-*/
-
 package org.bukkit.craftbukkit.util;
 
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.io.Serializable;
 import java.util.AbstractCollection;
 import java.util.AbstractSet;
 import java.util.Arrays;
 import java.util.Collection;
+import java.util.ConcurrentModificationException;
 import java.util.HashSet;
 import java.util.Iterator;
-import java.util.Map.Entry;
+import java.util.Map;
 import java.util.NoSuchElementException;
 import java.util.Set;
 
-public class LongObjectHashMap<V> implements Cloneable {
-    private long keys[];
-    private V values[];
+import static org.bukkit.craftbukkit.util.Java15Compat.Arrays_copyOf;
 
-    private int freeEntries;
-    private int elements;
+@SuppressWarnings("unchecked")
+public class LongObjectHashMap<V> implements Cloneable, Serializable {
+    static final long serialVersionUID = 2841537710170573815L;
 
-    private int highWaterMark;
-    private int lowWaterMark;
-    private final double minLoadFactor;
-    private final double maxLoadFactor;
+    private static final long EMPTY_KEY = Long.MIN_VALUE;
+    private static final int  BUCKET_SIZE = 4096;
 
-    private final long FREE = 0;
-    private final long REMOVED = Long.MIN_VALUE;
+    private transient long[][] keys;
+    private transient V[][]    values;
+    private transient int      modCount;
+    private transient int      size;
 
-    private static final int defaultCapacity = 277;
-    private static final double defaultMinLoadFactor = 0.2;
-    private static final double defaultMaxLoadFactor = 0.5;
+    public LongObjectHashMap() {
+        initialize();
+    }
 
-    private static final int largestPrime = Integer.MAX_VALUE;
-    private static final int[] primeCapacities = {
-            largestPrime,
+    public LongObjectHashMap(Map<? extends Long, ? extends V> map) {
+        this();
+        putAll(map);
+    }
 
-            5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421, 12853, 25717, 51437, 102877, 205759,
-            411527, 823117, 1646237, 3292489, 6584983, 13169977, 26339969, 52679969, 105359939,
-            210719881, 421439783, 842879579, 1685759167,
+    public int size() {
+        return size;
+    }
 
-            433, 877, 1759, 3527, 7057, 14143, 28289, 56591, 113189, 226379, 452759, 905551, 1811107,
-            3622219, 7244441, 14488931, 28977863, 57955739, 115911563, 231823147, 463646329, 927292699,
-            1854585413,
+    public boolean isEmpty() {
+        return size == 0;
+    }
 
-            953, 1907, 3821, 7643, 15287, 30577, 61169, 122347, 244703, 489407, 978821, 1957651, 3915341,
-            7830701, 15661423, 31322867, 62645741, 125291483, 250582987, 501165979, 1002331963,
-            2004663929,
+    public boolean containsKey(long key) {
+        return get(key) != null;
+    }
 
-            1039, 2081, 4177, 8363, 16729, 33461, 66923, 133853, 267713, 535481, 1070981, 2141977, 4283963,
-            8567929, 17135863, 34271747, 68543509, 137087021, 274174111, 548348231, 1096696463,
+    public boolean containsValue(V value) {
+        for (V val : values()) {
+            if (val == value || val.equals(value)) {
+                return true;
+            }
+        }
 
-            31, 67, 137, 277, 557, 1117, 2237, 4481, 8963, 17929, 35863, 71741, 143483, 286973, 573953,
-            1147921, 2295859, 4591721, 9183457, 18366923, 36733847, 73467739, 146935499, 293871013,
-            587742049, 1175484103,
+        return false;
+    }
 
-            599, 1201, 2411, 4831, 9677, 19373, 38747, 77509, 155027, 310081, 620171, 1240361, 2480729,
-            4961459, 9922933, 19845871, 39691759, 79383533, 158767069, 317534141, 635068283, 1270136683,
+    public V get(long key) {
+        int index = (int) (keyIndex(key) & (BUCKET_SIZE - 1));
+        long[] inner = keys[index];
+        if (inner == null) return null;
+
+        for (int i = 0; i < inner.length; i++) {
+            long innerKey = inner[i];
+            if (innerKey == EMPTY_KEY) {
+                return null;
+            } else if (innerKey == key) {
+                return values[index][i];
+            }
+        }
 
-            311, 631, 1277, 2557, 5119, 10243, 20507, 41017, 82037, 164089, 328213, 656429, 1312867,
-            2625761, 5251529, 10503061, 21006137, 42012281, 84024581, 168049163, 336098327, 672196673,
-            1344393353,
+        return null;
+    }
 
-            3, 7, 17, 37, 79, 163, 331, 673, 1361, 2729, 5471, 10949, 21911, 43853, 87719, 175447, 350899,
-            701819, 1403641, 2807303, 5614657, 11229331, 22458671, 44917381, 89834777, 179669557,
-            359339171, 718678369, 1437356741,
+    public V put(long key, V value) {
+        int index = (int) (keyIndex(key) & (BUCKET_SIZE - 1));
+        long[] innerKeys = keys[index];
+        V[] innerValues = values[index];
+        modCount++;
+
+        if (innerKeys == null) {
+            // need to make a new chain
+            keys[index] = innerKeys = new long[8];
+            Arrays.fill(innerKeys, EMPTY_KEY);
+            values[index] = innerValues = (V[]) new Object[8];
+            innerKeys[0] = key;
+            innerValues[0] = value;
+            size++;
+        } else {
+            int i;
+            for (i = 0; i < innerKeys.length; i++) {
+                // found an empty spot in the chain to put this
+                if (innerKeys[i] == EMPTY_KEY) {
+                    size++;
+                    innerKeys[i] = key;
+                    innerValues[i] = value;
+                    return null;
+                }
 
-            43, 89, 179, 359, 719, 1439, 2879, 5779, 11579, 23159, 46327, 92657, 185323, 370661, 741337,
-            1482707, 2965421, 5930887, 11861791, 23723597, 47447201, 94894427, 189788857, 379577741,
-            759155483, 1518310967,
+                // found an existing entry in the chain with this key, replace it
+                if (innerKeys[i] == key) {
+                    V oldValue = innerValues[i];
+                    innerKeys[i] = key;
+                    innerValues[i] = value;
+                    return oldValue;
+                }
+            }
 
-            379, 761, 1523, 3049, 6101, 12203, 24407, 48817, 97649, 195311, 390647, 781301, 1562611,
-            3125257, 6250537, 12501169, 25002389, 50004791, 100009607, 200019221, 400038451, 800076929,
-            1600153859
-    };
+            // chain is full, resize it and add our new entry
+            keys[index] = innerKeys = Arrays_copyOf(innerKeys, i << 1);
+            Arrays.fill(innerKeys, i, innerKeys.length, EMPTY_KEY);
+            values[index] = innerValues = Arrays_copyOf(innerValues, i << 1);
+            innerKeys[i] = key;
+            innerValues[i] = value;
+            size++;
+        }
 
-    static {
-        java.util.Arrays.sort(primeCapacities);
+        return null;
     }
 
-    public LongObjectHashMap() {
-        this(defaultCapacity);
-    }
+    public V remove(long key) {
+        int index = (int) (keyIndex(key) & (BUCKET_SIZE - 1));
+        long[] inner = keys[index];
+        if (inner == null) {
+            return null;
+        }
 
-    public LongObjectHashMap(int initialCapacity) {
-        this(initialCapacity, defaultMinLoadFactor, defaultMaxLoadFactor);
-    }
+        for (int i = 0; i < inner.length; i++) {
+            // hit the end of the chain, didn't find this entry
+            if (inner[i] == EMPTY_KEY) {
+                break;
+            }
 
-    @SuppressWarnings("unchecked")
-    public LongObjectHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor) {
-        int capacity = initialCapacity;
-        capacity = nextPrime(capacity);
-        if (capacity == 0) capacity = 1;
+            if (inner[i] == key) {
+                V value = values[index][i];
 
-        keys = new long[capacity];
-        values = (V[]) new Object[capacity];
+                for (i++; i < inner.length; i++) {
+                    if (inner[i] == EMPTY_KEY) {
+                        break;
+                    }
 
-        this.minLoadFactor = minLoadFactor;
-        if (maxLoadFactor == largestPrime) {
-            this.maxLoadFactor = 1.0;
-        } else {
-            this.maxLoadFactor = maxLoadFactor;
+                    inner[i - 1] = inner[i];
+                    values[index][i - 1] = values[index][i];
+                }
+
+                inner[i - 1] = EMPTY_KEY;
+                values[index][i - 1] = null;
+                size--;
+                modCount++;
+                return value;
+            }
         }
 
-        elements = 0;
-        freeEntries = capacity;
+        return null;
+    }
 
-        lowWaterMark = 0;
-        highWaterMark = chooseHighWaterMark(capacity, this.maxLoadFactor);
+    public void putAll(Map<? extends Long, ? extends V> map) {
+        for (Map.Entry entry : map.entrySet()) {
+            put((Long) entry.getKey(), (V) entry.getValue());
+        }
     }
 
     public void clear() {
-        Arrays.fill(keys, FREE);
-        Arrays.fill(values, null);
+        if (size == 0) {
+            return;
+        }
 
-        elements = 0;
-        freeEntries = keys.length;
-        trimToSize();
+        modCount++;
+        size = 0;
+        Arrays.fill(keys, null);
+        Arrays.fill(values, null);
     }
 
-    @SuppressWarnings("unchecked")
     public Set<Long> keySet() {
         return new KeySet();
     }
 
-    @SuppressWarnings("unchecked")
     public Collection<V> values() {
         return new ValueCollection();
     }
@@ -141,397 +188,237 @@ public class LongObjectHashMap<V> implements Cloneable {
      * Returns a Set of Entry objects for the HashMap. This is not how the internal
      * implementation is laid out so this constructs the entire Set when called. For
      * this reason it should be avoided if at all possible.
-     * @deprecated
+     *
      * @return Set of Entry objects
+     * @deprecated
      */
     @Deprecated
-    public Set<Entry<Long, V>> entrySet() {
-        HashSet<Entry<Long, V>> set = new HashSet<Entry<Long, V>>();
-
-        for (int i = 0; i < keys.length; i++) {
-            if (keys[i] != FREE && keys[i] != REMOVED) {
-                set.add(new LongObjectEntry(keys[i], values[i]));
-            }
+    public Set<Map.Entry<Long, V>> entrySet() {
+        HashSet<Map.Entry<Long, V>> set = new HashSet<Map.Entry<Long, V>>();
+        for (long key : keySet()) {
+            set.add(new Entry(key, get(key)));
         }
 
         return set;
     }
 
-    public boolean containsKey(int msw, int lsw) {
-        return containsKey(LongHash.toLong(msw, lsw));
-    }
+    public Object clone() throws CloneNotSupportedException {
+        LongObjectHashMap clone = (LongObjectHashMap) super.clone();
+        // Make sure we clear any existing information from the clone
+        clone.clear();
+        // Make sure the clone is properly setup for new entries
+        clone.initialize();
 
-    public boolean containsKey(long key) {
-        return indexOfKey(key) >= 0;
-    }
+        // Iterate through the data normally to do a safe clone
+        for (long key : keySet()) {
+            final V value = get(key);
+            clone.put(key, value);
+        }
 
-    public boolean containsValue(V value) {
-        return indexOfValue(value) >= 0;
+        return clone;
     }
 
-    public int size() {
-        return elements;
+    private void initialize() {
+        keys = new long[BUCKET_SIZE][];
+        values = (V[][]) new Object[BUCKET_SIZE][];
     }
 
-    public boolean isEmpty() {
-        return elements == 0;
+    private long keyIndex(long key) {
+        key ^= key >>> 33;
+        key *= 0xff51afd7ed558ccdL;
+        key ^= key >>> 33;
+        key *= 0xc4ceb9fe1a85ec53L;
+        key ^= key >>> 33;
+        return key;
     }
 
-    public V get(int msw, int lsw) {
-        return get(LongHash.toLong(msw, lsw));
-    }
+    private void writeObject(ObjectOutputStream outputStream) throws IOException {
+        outputStream.defaultWriteObject();
 
-    public V get(long key) {
-        int i = indexOfKey(key);
-        if (i < 0) {
-            return null;
+        for (long key : keySet()) {
+            V value = get(key);
+            outputStream.writeLong(key);
+            outputStream.writeObject(value);
         }
-        return values[i];
-    }
 
-    public V put(int msw, int lsw, V value) {
-        return put(LongHash.toLong(msw, lsw), value);
+        outputStream.writeLong(EMPTY_KEY);
+        outputStream.writeObject(null);
     }
 
-    public V put(long key, V value) {
-        int i = indexOfInsertion(key);
-        if (i < 0) {
-            i = -i - 1;
-            V oldValue = values[i];
-            values[i] = value;
-            return oldValue;
-        }
+    private void readObject(ObjectInputStream inputStream) throws ClassNotFoundException, IOException {
+        inputStream.defaultReadObject();
+        initialize();
 
-        if (elements > highWaterMark) {
-            int newCapacity = chooseGrowCapacity(elements + 1, minLoadFactor, maxLoadFactor);
-            rehash(newCapacity);
-            return put(key, value);
-        }
+        while (true) {
+            long key = inputStream.readLong();
+            V value = (V) inputStream.readObject();
+            if (key == EMPTY_KEY && value == null) {
+                break;
+            }
 
-        if (keys[i] == FREE) {
-            freeEntries--;
+            put(key, value);
         }
+    }
 
-        keys[i] = key;
-        values[i] = value;
-        elements++;
-
-        if (freeEntries < 1) {
-            int newCapacity = chooseGrowCapacity(elements + 1, minLoadFactor, maxLoadFactor);
-            rehash(newCapacity);
-        }
 
-        return null;
-    }
+    private class ValueIterator implements Iterator<V> {
+        private int count;
+        private int index;
+        private int innerIndex;
+        private int expectedModCount;
+        private long lastReturned = EMPTY_KEY;
 
-    public V remove(int msw, int lsw) {
-        return remove(LongHash.toLong(msw, lsw));
-    }
+        long prevKey = EMPTY_KEY;
+        V prevValue;
 
-    public V remove(long key) {
-        int i = indexOfKey(key);
-        if (i < 0) {
-            return null;
+        ValueIterator() {
+            expectedModCount = LongObjectHashMap.this.modCount;
         }
 
-        V oldValue = values[i];
-        keys[i] = REMOVED;
-        values[i] = null;
-        elements--;
-
-        if (elements < lowWaterMark) {
-            int newCapacity = chooseShrinkCapacity(elements, minLoadFactor, maxLoadFactor);
-            rehash(newCapacity);
+        public boolean hasNext() {
+            return count < LongObjectHashMap.this.size;
         }
 
-        return oldValue;
-    }
+        public void remove() {
+            if (LongObjectHashMap.this.modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
 
-    public void ensureCapacity(int minCapacity) {
-        if (keys.length < minCapacity) {
-            int newCapacity = nextPrime(minCapacity);
-            rehash(newCapacity);
-        }
-    }
+            if (lastReturned == EMPTY_KEY) {
+                throw new IllegalStateException();
+            }
 
-    public void trimToSize() {
-        int newCapacity = nextPrime((int) (1 + 1.2 * size()));
-        if (keys.length > newCapacity) {
-            rehash(newCapacity);
+            count--;
+            LongObjectHashMap.this.remove(lastReturned);
+            lastReturned = EMPTY_KEY;
+            expectedModCount = LongObjectHashMap.this.modCount;
         }
-    }
 
-    public Object clone() throws CloneNotSupportedException {
-        LongObjectHashMap copy = (LongObjectHashMap) super.clone();
-        copy.keys = keys.clone();
-        copy.values = values.clone();
-        return copy;
-    }
+        public V next() {
+            if (LongObjectHashMap.this.modCount != expectedModCount) {
+                throw new ConcurrentModificationException();
+            }
 
-    /**
-     * @param key the key to be added to the receiver.
-     * @return the index where the key would need to be inserted, if it is not already contained.
-     *         Returns -index-1 if the key is already contained at slot index.
-     *         Therefore, if the returned index < 0, then it is already contained at slot -index-1.
-     *         If the returned index >= 0, then it is NOT already contained and should be inserted at slot index.
-     */
-    private int indexOfInsertion(long key) {
-        final int length = keys.length;
+            if (!hasNext()) {
+                throw new NoSuchElementException();
+            }
 
-        final int hash = hash(key) & 0x7FFFFFFF;
-        int i = hash % length;
-        int decrement = hash % (length - 2);
-        if (decrement == 0) {
-            decrement = 1;
-        }
+            long[][] keys = LongObjectHashMap.this.keys;
+            count++;
 
-        while ((keys[i] != FREE && keys[i] != REMOVED) && keys[i] != key) {
-            i -= decrement;
-            if (i < 0) {
-                i += length;
+            if (prevKey != EMPTY_KEY) {
+                innerIndex++;
             }
-        }
 
-        if (keys[i] == REMOVED) {
-            int j = i;
-            while (keys[i] != FREE && (keys[i] == REMOVED || keys[i] != key)) {
-                i -= decrement;
-                if (i < 0) {
-                    i += length;
+            for (; index < keys.length; index++) {
+                if (keys[index] != null) {
+                    for (; innerIndex < keys[index].length; innerIndex++) {
+                        long key = keys[index][innerIndex];
+                        V value = values[index][innerIndex];
+                        if (key == EMPTY_KEY) {
+                            break;
+                        }
+
+                        lastReturned = key;
+                        prevKey = key;
+                        prevValue = value;
+                        return prevValue;
+                    }
+                    innerIndex = 0;
                 }
             }
-            if (keys[i] == FREE) {
-                i = j;
-            }
-        }
 
-
-        if (keys[i] != FREE && keys[i] != REMOVED) {
-            // key already contained at slot i.
-            // return a negative number identifying the slot.
-            return -i - 1;
+            throw new NoSuchElementException();
         }
-        // not already contained, should be inserted at slot i.
-        // return a number >= 0 identifying the slot.
-        return i;
     }
 
-    private int indexOfKey(long key) {
-        final int length = keys.length;
-
-        final int hash = hash(key) & 0x7FFFFFFF;
-        int i = hash % length;
-        int decrement = hash % (length - 2);
-        if (decrement == 0) decrement = 1;
-
-        while (keys[i] != FREE && (keys[i] == REMOVED || keys[i] != key)) {
-            i -= decrement;
-            if (i < 0) i += length;
-        }
+    private class KeyIterator implements Iterator<Long> {
+        final ValueIterator iterator;
 
-        if (keys[i] == FREE) {
-            return -1;
+        public KeyIterator() {
+            iterator = new ValueIterator();
         }
 
-        return i;
-    }
-
-    private int indexOfValue(Object value) {
-        for (int i = keys.length; --i >= 0; ) {
-            if ((keys[i] != FREE && keys[i] != REMOVED) && values[i] == value) {
-                return i;
-            }
+        public void remove() {
+            iterator.remove();
         }
 
-        return -1;
-    }
-
-    @SuppressWarnings("unchecked")
-    private void rehash(int newCapacity) {
-        int oldCapacity = keys.length;
-
-        long oldKeys[] = keys;
-        V oldValues[] = values;
-
-        long newKeys[] = new long[newCapacity];
-        V newValues[] = (V[]) new Object[newCapacity];
-
-        lowWaterMark = chooseLowWaterMark(newCapacity, minLoadFactor);
-        highWaterMark = chooseHighWaterMark(newCapacity, maxLoadFactor);
-
-        keys = newKeys;
-        values = newValues;
-        freeEntries = newCapacity - elements;
-
-        for (int i = oldCapacity; i-- > 0; ) {
-            if (oldKeys[i] != FREE && oldKeys[i] != REMOVED) {
-                long element = oldKeys[i];
-                int index = indexOfInsertion(element);
-                newKeys[index] = element;
-                newValues[index] = oldValues[i];
-            }
+        public boolean hasNext() {
+            return iterator.hasNext();
         }
-    }
 
-    private static int nextPrime(int desiredCapacity) {
-        int i = Arrays.binarySearch(primeCapacities, desiredCapacity);
-        if (i < 0) {
-            i = -i - 1;
+        public Long next() {
+            iterator.next();
+            return iterator.prevKey;
         }
-
-        return primeCapacities[i];
-    }
-
-    private int chooseGrowCapacity(int size, double minLoad, double maxLoad) {
-        return nextPrime(Math.max(size + 1, (int) ((4 * size / (3 * minLoad + maxLoad)))));
-    }
-
-    private int chooseShrinkCapacity(int size, double minLoad, double maxLoad) {
-        return nextPrime(Math.max(size + 1, (int) ((4 * size / (minLoad + 3 * maxLoad)))));
-    }
-
-    private int chooseHighWaterMark(int capacity, double maxLoad) {
-        return Math.min(capacity - 2, (int) (capacity * maxLoad));
-    }
-
-    private int chooseLowWaterMark(int capacity, double minLoad) {
-        return (int) (capacity * minLoad);
-    }
-
-    // This method copied from Murmur3, written by Austin Appleby released under Public Domain
-    private int hash(long value) {
-        value ^= value >>> 33;
-        value *= 0xff51afd7ed558ccdL;
-        value ^= value >>> 33;
-        value *= 0xc4ceb9fe1a85ec53L;
-        value ^= value >>> 33;
-        return (int) value;
     }
 
-    private class LongObjectEntry implements Entry<Long, V> {
-        private final long key;
-        private final V value;
 
-        LongObjectEntry(long k, V v) {
-            key = k;
-            value = v;
+    private class KeySet extends AbstractSet<Long> {
+        public void clear() {
+            LongObjectHashMap.this.clear();
         }
 
-        public Long getKey() {
-            return key;
-        }
-
-        public V getValue() {
-            return value;
+        public int size() {
+            return LongObjectHashMap.this.size();
         }
 
-        public V setValue(V v) {
-            // Changes are not reflected in the main HashMap
-            return value;
-        }
-    }
+        public boolean contains(Object key) {
+            return key instanceof Long && LongObjectHashMap.this.containsKey((Long) key);
 
-    private class KeySet extends AbstractSet {
-        public int size() {
-            return elements;
         }
 
-        public boolean contains(long key) {
-            return containsKey(key);
+        public boolean remove(Object key) {
+            return LongObjectHashMap.this.remove((Long) key) != null;
         }
 
-        @SuppressWarnings("unchecked")
         public Iterator<Long> iterator() {
             return new KeyIterator();
         }
     }
 
-    private class KeyIterator implements Iterator {
-        private int ix;
-
-        private KeyIterator() {
-            for (ix = 0; ix < keys.length; ix++) {
-                if (values[ix] != null && keys[ix] != REMOVED) {
-                    break;
-                }
-            }
-        }
-
-        public boolean hasNext() {
-            return ix < keys.length;
-        }
 
-        public void remove() {
-            throw new UnsupportedOperationException("Collection is read-only");
+    private class ValueCollection extends AbstractCollection<V> {
+        public void clear() {
+            LongObjectHashMap.this.clear();
         }
 
-        public Long next() {
-            if (ix >= keys.length) {
-                throw new NoSuchElementException();
-            }
-
-            long key = keys[ix++];
-
-            for (; ix < keys.length; ix++) {
-                if (keys[ix] != FREE && keys[ix] != REMOVED) {
-                    break;
-                }
-            }
-
-            return key;
+        public int size() {
+            return LongObjectHashMap.this.size();
         }
-    }
 
-    private class ValueCollection extends AbstractCollection<V> {
-        public int size() {
-            return elements;
+        public boolean contains(Object value) {
+            return LongObjectHashMap.this.containsValue((V) value);
         }
 
-        @SuppressWarnings("unchecked")
         public Iterator<V> iterator() {
             return new ValueIterator();
         }
-
-        @SuppressWarnings("unchecked")
-        public boolean contains(Object value) {
-            return containsValue((V) value);
-        }
     }
 
-    private class ValueIterator<V> implements Iterator<V> {
-        private int ix;
 
-        private ValueIterator() {
-            for (ix = 0; ix < values.length; ix++) {
-                if (values[ix] != null) {
-                    break;
-                }
-            }
-        }
+    private class Entry implements Map.Entry<Long, V> {
+        private final Long key;
+        private V value;
 
-        public boolean hasNext() {
-            return ix < values.length;
+        Entry(long k, V v) {
+            key = k;
+            value = v;
         }
 
-        public void remove() {
-            throw new UnsupportedOperationException("Collection is read-only");
+        public Long getKey() {
+            return key;
         }
 
-        @SuppressWarnings("unchecked")
-        public V next() {
-            if (ix >= values.length) {
-                throw new NoSuchElementException();
-            }
-
-            V value = (V) values[ix++];
-
-            for (; ix < values.length; ix++) {
-                if (values[ix] != null) {
-                    break;
-                }
-            }
-
+        public V getValue() {
             return value;
         }
+
+        public V setValue(V v) {
+            V old = value;
+            value = v;
+            put(key, v);
+            return old;
+        }
     }
 }