Repository: netty/netty
Issue: Bug in the new IntObjectHashMap.java
Labels: defect

"Should never happen" condition has happened :) This may be difficult to reproduce, I noticed two events like this spaced by ~5 minutes on a server processing 20Kqps. 

22:59:04.632 [epollEventLoopGroup-3-3] WARN  io.netty.channel.AbstractChannel - Failed to close a channel.
java.io.IOException: Error closing file descriptor
    at io.netty.channel.epoll.Native.close(Native Method) ~[netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.epoll.AbstractEpollChannel.doClose(AbstractEpollChannel.java:66) ~[netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe.closeForcibly(AbstractChannel.java:580) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.bootstrap.ServerBootstrap$ServerBootstrapAcceptor.forceClose(ServerBootstrap.java:266) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.bootstrap.ServerBootstrap$ServerBootstrapAcceptor.access$100(ServerBootstrap.java:213) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.bootstrap.ServerBootstrap$ServerBootstrapAcceptor$1.operationComplete(ServerBootstrap.java:256) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.bootstrap.ServerBootstrap$ServerBootstrapAcceptor$1.operationComplete(ServerBootstrap.java:252) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.DefaultPromise.notifyListener0(DefaultPromise.java:679) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.DefaultPromise.notifyListeners(DefaultPromise.java:565) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.DefaultPromise.tryFailure(DefaultPromise.java:425) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe.safeSetFailure(AbstractChannel.java:732) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe.register0(AbstractChannel.java:451) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe.access$100(AbstractChannel.java:375) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe$1.run(AbstractChannel.java:419) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.SingleThreadEventExecutor.runAllTasks(SingleThreadEventExecutor.java:370) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.epoll.EpollEventLoop.run(EpollEventLoop.java:268) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.SingleThreadEventExecutor$2.run(SingleThreadEventExecutor.java:116) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.DefaultThreadFactory$DefaultRunnableDecorator.run(DefaultThreadFactory.java:137) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at java.lang.Thread.run(Thread.java:744) [na:1.7.0_55]
22:59:04.633 [epollEventLoopGroup-3-3] WARN  io.netty.bootstrap.ServerBootstrap - Failed to register an accepted channel: [id: 0x73af18bb, /74.125.183.1:42353 :> /10.203.57.186:8080]
java.lang.AssertionError: Unable to insert
    at io.netty.util.collection.IntObjectHashMap.put(IntObjectHashMap.java:149) ~[netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.epoll.EpollEventLoop.add(EpollEventLoop.java:132) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.epoll.AbstractEpollChannel.doRegister(AbstractEpollChannel.java:156) ~[netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe.register0(AbstractChannel.java:440) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe.access$100(AbstractChannel.java:375) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.AbstractChannel$AbstractUnsafe$1.run(AbstractChannel.java:419) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.SingleThreadEventExecutor.runAllTasks(SingleThreadEventExecutor.java:370) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.channel.epoll.EpollEventLoop.run(EpollEventLoop.java:268) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.SingleThreadEventExecutor$2.run(SingleThreadEventExecutor.java:116) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at io.netty.util.concurrent.DefaultThreadFactory$DefaultRunnableDecorator.run(DefaultThreadFactory.java:137) [netty-all-4.0.21.Final.jar:4.0.21.Final]
    at java.lang.Thread.run(Thread.java:744) [na:1.7.0_55]


Issue comments:
opinali@ thanks for the find!  Do you think you could change the code to capture the state of the map when the assertion occurs?

@nmittler shouldn't be hard; let me try this.

well, it's being harder than expected... I have added code to dump the map state, but after redeploy, couldn't reproduce the error anymore. I hope it's not some of those obscure javac or JIT bugs where any perturbation to the application code makes the symptoms go away.

Well, I will keep this debug code in my test deployments for some time, I usually have a test server running 24x7 anyway. Will post if I get lucky to capture the bug again.

Ok, testing failed so I'm reviewing the code. This part of insertAt() looks fishy:

```
    } else if (available == 0) {
        // Open addressing requires that we have at least 1 slot available. Need to refresh
        // the arrays to clear any removed elements.
        rehash(capacity());
    }
```

Shouldn't that be rehash(capacity() + 1) at least? This will rehash the hashmap to the same size it already has, violating the rule of keeping at least one slot available. And if you violate that, the next call to put() won't find any AVAILABLE/REMOVED slot, and because the capacity check/rehash is only performed by insertAt(), put() doesn't call that unless there's some available slot, so this will produce exactly the assertion I saw.

@opinali sounds fishy for sure.  Shouldn't we also double it and not just use +1 ?

Something like:

``` java
rehash(capacity() <<1);
```

@nmittler @opinali wdyt ?

Yes I see no reason to not double (or use whatever same growing factor used by the size>maxSize case). The code could be simplified to:

```
    if (size > maxSize || available == 0) {
        rehash(capacity() * 2);
    }
```

@opinali yep sounds good!  I would make the capacity odd, however (add 1).  Would you mind making a pull request?

Actually I take that back, the +1 will be done automatically, so rehash(capacity() \* 2) should be sufficient.

@nmittler could you submit a patch with a unit case?

> Am 16.07.2014 um 21:35 schrieb Nathan Mittler notifications@github.com:
> 
> Actually I take that back, the +1 will be done automatically, so rehash(capacity() \* 2) should be sufficient.
> 
> —
> Reply to this email directly or view it on GitHub.

size*1.5+1 is usually a better space/speed deal unless the algorithm
requires power-of-2 sizes which is not the case here. Wouldn't hurt also to
guard against overflow when size approaches MAX_VALUE... not likely to ever
happen for the channel map but maybe you want to use this for something
else later.
On Jul 16, 2014 3:57 PM, "Norman Maurer" notifications@github.com wrote:

> @nmittler could you submit a patch with a unit case?
> 
> > Am 16.07.2014 um 21:35 schrieb Nathan Mittler notifications@github.com:
> > 
> > Actually I take that back, the +1 will be done automatically, so
> > rehash(capacity() \* 2) should be sufficient.
> > 
> > —
> > Reply to this email directly or view it on GitHub.
> 
> —
> Reply to this email directly or view it on GitHub
> https://github.com/netty/netty/issues/2659#issuecomment-49218191.

@opinali I'm starting to think the original code was correct.  maxSize is the size at which we have to grow (defaults to 0.5 \* capacity). If we add a bunch of entries and then delete them, the number of AVAILABLE slots could eventually become 0 since they have been marked as REMOVED. In this case, we rehash with the current capacity to clear out the REMOVED nodes and make them AVAILABLE again.  We shouldn't need to grow in this case.

I suspect that the problem you're running into is related to the choice of capacity.  This choice is important for reducing collisions in open addressing and to this point I've just been ensuring that it's odd.  Using prime numbers for capacity, however, is the typical approach and I think we should migrate to this before making any other changes.

Sound reasonable?

Hmm yeah

> Am 17.07.2014 um 19:34 schrieb Nathan Mittler notifications@github.com:
> 
> @opinali I'm starting to think the original code was correct. maxSize is the size at which we have to grow (defaults to 0.5 \* capacity). If we add a bunch of entries and then delete them, the number of AVAILABLE slots could eventually become 0 since they have been marked as REMOVED. In this case, we rehash with the current capacity to clear out the REMOVED nodes and make them AVAILABLE again. We shouldn't need to grow in this case.
> 
> I suspect that the problem you're running into is related to the choice of capacity. This choice is important for reducing collisions in open addressing and to this point I've just been ensuring that it's odd. Using prime numbers for capacity, however, is the typical approach and I think we should migrate to this before making any other changes.
> 
> Sound reasonable?
> 
> —
> Reply to this email directly or view it on GitHub.

@normanmaurer do you have any concerns?

@nmittler nope... go ahead

Here's a easy test that triggers the bug. (Forcing certain values including loadFactor=1.0 just to make it quicker to catch in step-by-step debugging; it's trivial to reproduce with any loadFactor.)

public class IntObjectHashMapTest {
  @Test
  public void test() {
    IntObjectHashMap<String> map = new IntObjectHashMap<>(5 \* 2, 1.0f);
    for (int i = 0; i < 5; ++i) {
      map.put(i \* 5 /\* hash collision */, "");
    }
  }
}

@nmittler was right, the problem is elsewhere. The probing logic in put() is incorrect; see:
capacity=10, key=20 => increment=5
index will be: 0, 5, 10 wraps to 0 which stops the loop.
Only slots 0 and 5 are ever visited by the loop, then it fails.
This logic will never work in all cases, unless the capacity size is guaranteed to always be a prime number (there's a comment about that; but it's probably a bad idea because, for large N, finding the next prime >N is very inefficient --- best choice is BigInteger.nextProbablePrime() but this is overkill so you need to reimplement that algorithm for ints and that will still be outrageously slow for this purpose).
I understand that the intention is to scatter spills across the whole array to avoid generate performance for specific buckets, but there's always some scenario where this will happen. You could just use increment=1 and let bucket distribution depend uniquely from element hashes.

@opinali btw we love contributions ;) So feel free to submit a PR with fix + text-case.

@opinali The way Trove (and likely other libraries) deal with this is to use a lookup table for the next prime.  Basically they take advantage of the fact that they always expand by a factor of 2 to allow them to reduce the table size.  When they expand, they do a binary search to get the first value in the table that's >= the requested capacity.  This should be trivial to implement and the adjustCapacity() method was already separated out so that we could add the logic there.

Good idea the lookup table. For my emergency needs I've implemented the ++index with wrapping to zero; tested it and works perfectly. It seems the table size stabilizes at 11264 with my test load. Maybe a good option if you think this issue must be fixed quickly in a maintenance release. 

The rehash function could be optimized, right now it just loops invoking put() but it could have a much simpler loop without special cases like REMOVED entries and checks for capacity etc. Rehashing cost can be a problem for huge hashmaps, remarkably for high-scale & latency-sensitive code; once again it's not a priority for the current usage of this map, just another thing we might improve easily.

I'm always suspicious of each new attempt to optimize open hashing, I immediately remember Peter Brass's book where he strongly discourages this technique and and the production of any new papers about the subject. :) But admittedly, in a system like the JVM where linked nodes are too expensive for primitive-value keys like ints, the open hashing (being the only way to resolve conflicts without boxing) should beat its disadvantages. Gonna check this later, I hope to have some time in the next few days to play with this and send a good patch.

@opinali @nmittler I think we can do an easy fix fast and then think about how to improve it. WDYT ?

Oops, I was too eager with the last comment (deleted), had a test bug. So I'm working on a patch, but also worried with indexOf(). This method works correctly (after applying the same probing fix), but here the problem is that it degenerates to linear scan of potentially the whole array if we have too many REMOVED entries. I guess this is already know, there's a TODO for implementing re-compaction which is necessary to avoid that problem. This is critical because the problem is not some edge case, e.g. doesn't affect only maps that have too much conflicts for a specific key: any map that's completely filled up, and then completely drained (but only with individual removes, never clear()), will have all states set to REMOVED, and once this happens, if you add any two keys that conflict and remove the first and try to find the second, this will always cost O(capacity). Anyway, probably punting on this for now. I could add a simple check to remove—if the map becomes empty, then fill states with AVAILABLE—but this would backfire if the map repeatedly transitions between few elements and empty.

@opinali @normanmaurer I know we're concerned about external dependencies in Netty but I'm concerned that we're reinventing the wheel here.  Other projects already have working implementations that have been through more rigorous testing.  Should we start shopping?

@nmittler @normanmaurer +1 to shop versus build it. Hacking fundamental data structures is fun, but it's an endless rabbit hole. For my emergency needs I need the patched IntObjectHashMap so I'm working on it even if next Netty will drop it, will send the patch anyway, in case the shopping option is not easy due to compatible licenses or other reason.

@nmittler @opinali the problem is that Trove is LGPL so we can only add is as optional dependency and this makes it also impossible to just fork their impl :( 

@nmittler @opinali I did not check in detail but I found this impl to be ASL2:

https://github.com/android/platform_frameworks_base/blob/master/core/java/android/util/SparseArray.java
https://github.com/libgdx/libgdx/blob/master/gdx/src/com/badlogic/gdx/utils/IntMap.java

So maybe we could just fork SparseArray ?

+1 for SparseArray

@nmittler so maybe just fork this into internal package and deprecate the collection package with classes. @nmittler @opinali sounds good ?

@normanmaurer That sounds good to me.  I'll see if I have time this weekend to work on it.

@opinali beside this we could also just use HashMap in EpollEventLoop for now as I think it should be good enough at the end. WDYT?

> Am 18.07.2014 um 21:35 schrieb Nathan Mittler notifications@github.com:
> 
> @normanmaurer That sounds good to me. I'll see if I have time this weekend to work on it.
> 
> —
> Reply to this email directly or view it on GitHub.

@normanmaurer @nmittler SparseArray seems to be the better of these two options, but according to its docs only good for really small maps, up to "hundreds" of elements. My test goes up to 10K elements, and I could go higher than that with a big instance with 10Gbit connection. But I have no idea how critical is the performance of this map for Netty (I suppose it's at least significant enough to have motivated the recent introduction of IntObjectHashMap?). Another important factor in the shop-vs-build decision is that, if we have to fork and maybe do any adaptation in the "shopped" code, and tracking changes to the source project and merging new stuff etc., that's what was already done with IntObjectHashMap so we might just as well keep it (once fixed). If we don't have the option of black-box reuse (just depend on someone else's jar file and not mess with its impl), having to cherry-pick and fork some code, then we should fully own that code.

I've got carried away and made significant improvements on this code already, including limited recompaction and new tests. Sending patch later today or tomorrow... but let's keep options open anyway.

True enough... So maybe let us just fix ours :)

> Am 19.07.2014 um 16:45 schrieb Osvaldo Pinali Doederlein notifications@github.com:
> 
> @normanmaurer @nmittler SparseArray seems to be the better of these two options, but according to its docs only good for really small maps, up to "hundreds" of elements. My test goes up to 10K elements, and I could go higher than that with a big instance with 10Gbit connection. But I have no idea how critical is the performance of this map for Netty (I suppose it's at least significant enough to have motivated the recent introduction of IntObjectHashMap?). Another important factor in the shop-vs-build decision is that, if we have to fork and maybe do any adaptation in the "shopped" code, and tracking changes to the source project and merging new stuff etc., that's what was already done with IntObjectHashMap so we might just as well keep it (once fixed). If we don't have the option of black-box reuse (just depend on someone else's jar file and not mess w ith its impl), having to cherry-pick and fork some code, then we should fully own that code.
> 
> I've got carried away and made significant improvements on this code already, including limited recompaction and new tests. Sending patch later today or tomorrow... but let's keep options open anyway.
> 
> —
> Reply to this email directly or view it on GitHub.

@opinali agreed - I recall looking at SparseArray but I think I went down a different path for that reason.  Ping me once you get the patch together ... thanks for the contrib!

@nmittler @normanmaurer Pull request sent!

Nice ! Will review today

> Am 20.07.2014 um 00:24 schrieb Osvaldo Pinali Doederlein notifications@github.com:
> 
> @nmittler @normanmaurer Pull request sent!
> 
> —
> Reply to this email directly or view it on GitHub.

Fix was pushed


Pull request review comments:
Please use for (;;) as we use for(;;) for this kind of stuff everywhere in netty. Just for the sake of consistency

IllegalStateException ?

I think if we do v.equals(values[i]) we can eliminate the null check

return false if null is given as value

same as above

Please replace  with for (;;)

Store oldVals[i] in local variable so we not need to double access the array in case it is not null

for (;;)

Store oldKeys[i] local variable so we can use it again without the need to access the array again

for (;;)

Maybe use some better initialCapacit for the builder ?

Store source.values[i] in local variable so we can re-use it if not null and not need again to lookup the array.

Maybe keep the AVAILABLE just to make it easier to understand ?

Store keys[i] in local variable so we not need to access the array again

I prefer that too, done

This would be incorrect here, as we now use values, not keys, to know which fields are available... and for reference types 'null' has a natural "unused" meaning by default, so I think a constant AVAILABLE=null would only obfuscate things.

done

The map still supports null :) there's a trick here, will add as documentation.

This is a very low-level optimization: nulls are expected to be very common (at least 50% of all slots even in a "full" map with the default load factor 0.5), so I fast-path this case before making any invocation, will be faster even if the equals call is inlined (which I don't expect to happen, in the general case it's a megamorphic call since you can put any ind of object in the map).

Ah right... Maybe add a comment to make it clear why the null check is done. Just to be sure we not refactor it later

> Am 20.07.2014 um 17:21 schrieb Osvaldo Pinali Doederlein notifications@github.com:
> 
> In common/src/main/java/io/netty/util/collection/IntObjectHashMap.java:
> 
> > @@ -212,10 +183,9 @@ public boolean containsKey(int key) {
> > 
> > ```
> >  @Override
> >  public boolean containsValue(V value) {
> > ```
> > -        int i = -1;
> > -        while ((i = nextEntryIndex(i + 1)) >= 0) {
> > -            V next = values[i];
> > -            if (value == next || value != null && value.equals(next)) {
> > -        V v = setValue(value);
> > -        for (int i = 0; i < values.length; ++i) {
> > -            if (values[i] != null && values[i].equals(v)) {
> >   This is a very low-level optimization: nulls are expected to be very common (at least 50% of all slots even in a "full" map with the default load factor 0.5), so I fast-path this case before making any invocation, will be faster even if the equals call is inlined (which I don't expect to happen, in the general case it's a megamorphic call since you can put any ind of object in the map).
> 
> —
> Reply to this email directly or view it on GitHub.

going for a faster loop... the standard formula of multiply-and-accummulate-with-prime is a good default, but here the array can be big and this needs to be as fast as possible including potential unrolling/SIMD optimization.

seems different to me; both sides can either be null or non-null (occupied vs. non-occupied)

done

done

done

done

done

forgot that one... done

True :)

> Am 20.07.2014 um 17:34 schrieb Osvaldo Pinali Doederlein notifications@github.com:
> 
> In common/src/main/java/io/netty/util/collection/IntObjectHashMap.java:
> 
> > ```
> >          if (value == null) {
> > ```
> > -                if (otherValue != null || !other.containsKey(entry.key())) {
> >   seems different to me; both sides can either be null or non-null (occupied vs. non-occupied)
> 
> —
> Reply to this email directly or view it on GitHub.

Ok

Thanks

Seems like this is a left-over... Remove it

Remove merge stuff

Fix up

Fix up

Fix up

Fix up

argh, github rookie here. will fix these.

If you have any issues let me know

> Am 20.07.2014 um 17:55 schrieb Osvaldo Pinali Doederlein notifications@github.com:
> 
> In common/src/main/java/io/netty/util/collection/IntObjectHashMap.java:
> 
> > @@ -212,10 +197,13 @@ public boolean containsKey(int key) {
> > 
> > ```
> >  @Override
> >  public boolean containsValue(V value) {
> > ```
> > -        int i = -1;
> > -        while ((i = nextEntryIndex(i + 1)) >= 0) {
> > -            V next = values[i];
> > -            if (value == next || value != null && value.equals(next)) {
> > -        V v = setValue(value);
> > -        for (int i = 0; i < values.length; ++i) {
> >   +<<<<<<< HEAD
> > -            // The map supports null values; this will be matched as NULL_VALUE.equals(NULL_VALUE).
> >   +=======
> >   +>>>>>>> 5813e35a5182578fe7c7fa646012dd4b7d72a2e8
> >   argh, github rookie here. will fix these.
> 
> —
> Reply to this email directly or view it on GitHub.

nit: the names of these methods are a little unclear.  Maybe something like valueToReturn() and valueToStore()? Not crazy about these either ... maybe you can come up with something better?

Maybe wrap() and unwrap()? Or mask() and unmask(), or toInternal() and toExternal()

+1 for toInternal/toExternal

@nmittler @opinali: Shouldn't this be:

``` java
if (otherValue != null || other.containsKey(key)) {
```

With this code merged into master the http2 tests fails because of the failed equals tests.

Aww, I was running only the netty-comon tests because the full test suite failed for me since first checkout. The bug here is more subtle, I'm forgetting to handle the null vs. NULL_VALUE stuff. Fixing now..

Ah ok... let me know one you fixed it

Fixed already, working on improved tests for this now... in fact the code was handling NULL_VALUE, but incorrectly. Also, the original code has a bug in hashCode(); if you examine it, the hashCode function depends on the internal order of entries: values=[1,2] and values=[2,1] will produce different hashes. This difference of ordering is possible when the maps had different hashing conflicts, e.g. the natural placement would be [1,2] but insertion history was something like [-,-] =(put 8)=> [8,-] =(put 1)=> [8,1] =(remove 8)=> [-,1] =(put 2)=> [2,1]. And even when you hit this scenario, which may be very hard in artificial unit tests not designed to build hashtables in a messy way, your test may still succeed if it uses only equals() but not hashCode() (rare real-world code will use hashtables as values inside other hashtable). The new hashCode() function already avoids this bug, but I'm adding a commente there and also tests to watch for this...

@normanmaurer fixed and pushed. Also reported an issue for my full-build problem (this is on Goobuntu Trusty, and I don't normally compile native code so maybe something else missing in my env.) But I have ran most tests, everything before that failure works including http2.


Patch that resolved the issue:
diff --git a/common/src/main/java/io/netty/util/collection/IntObjectHashMap.java b/common/src/main/java/io/netty/util/collection/IntObjectHashMap.java
index da5dc9e834d..34480188d61 100644
--- a/common/src/main/java/io/netty/util/collection/IntObjectHashMap.java
+++ b/common/src/main/java/io/netty/util/collection/IntObjectHashMap.java
@@ -21,40 +21,36 @@
 import java.util.NoSuchElementException;
 
 /**
- * A hash map implementation of {@link IntObjectMap} that uses open addressing for keys. To minimize
- * the memory footprint, this class uses open addressing rather than chaining. Collisions are
- * resolved using double hashing.
+ * A hash map implementation of {@link IntObjectMap} that uses open addressing for keys.
+ * To minimize the memory footprint, this class uses open addressing rather than chaining.
+ * Collisions are resolved using linear probing. Deletions implement compaction, so cost of
+ * remove can approach O(N) for full maps, which makes a small loadFactor recommended.
  *
  * @param <V> The value type stored in the map.
  */
 public class IntObjectHashMap<V> implements IntObjectMap<V>, Iterable<IntObjectMap.Entry<V>> {
 
-    /** State indicating that a slot is available.*/
-    private static final byte AVAILABLE = 0;
-
-    /** State indicating that a slot is occupied. */
-    private static final byte OCCUPIED = 1;
-
-    /** State indicating that a slot was removed. */
-    private static final byte REMOVED = 2;
-
     /** Default initial capacity. Used if not specified in the constructor */
     private static final int DEFAULT_CAPACITY = 11;
 
     /** Default load factor. Used if not specified in the constructor */
     private static final float DEFAULT_LOAD_FACTOR = 0.5f;
 
+    /**
+     * Placeholder for null values, so we can use the actual null to mean available.
+     * (Better than using a placeholder for available: less references for GC processing.)
+     */
+    private static final Object NULL_VALUE = new Object();
+
     /** The maximum number of elements allowed without allocating more space. */
     private int maxSize;
 
     /** The load factor for the map. Used to calculate {@link #maxSize}. */
     private final float loadFactor;
 
-    private byte[] states;
     private int[] keys;
     private V[] values;
     private int size;
-    private int available;
 
     public IntObjectHashMap() {
         this(DEFAULT_CAPACITY, DEFAULT_LOAD_FACTOR);
@@ -68,93 +64,71 @@ public IntObjectHashMap(int initialCapacity, float loadFactor) {
         if (initialCapacity < 1) {
             throw new IllegalArgumentException("initialCapacity must be >= 1");
         }
-        if (loadFactor <= 0.0f) {
-            throw new IllegalArgumentException("loadFactor must be > 0");
+        if (loadFactor <= 0.0f || loadFactor > 1.0f) {
+            // Cannot exceed 1 because we can never store more than capacity elements;
+            // using a bigger loadFactor would trigger rehashing before the desired load is reached.
+            throw new IllegalArgumentException("loadFactor must be > 0 and <= 1");
         }
 
         this.loadFactor = loadFactor;
 
         // Adjust the initial capacity if necessary.
-        initialCapacity = adjustCapacity(initialCapacity);
+        int capacity = adjustCapacity(initialCapacity);
 
         // Allocate the arrays.
-        states = new byte[initialCapacity];
-        keys = new int[initialCapacity];
-        @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
-        V[] temp = (V[]) new Object[initialCapacity];
+        keys = new int[capacity];
+        @SuppressWarnings({ "unchecked", })
+        V[] temp = (V[]) new Object[capacity];
         values = temp;
 
         // Initialize the maximum size value.
-        maxSize = calcMaxSize(initialCapacity);
+        maxSize = calcMaxSize(capacity);
+    }
 
-        // Initialize the available element count
-        available = initialCapacity - size;
+    private static <T> T toExternal(T value) {
+        return value == NULL_VALUE ? null : value;
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T> T toInternal(T value) {
+        return value == null ? (T) NULL_VALUE : value;
     }
 
     @Override
     public V get(int key) {
         int index = indexOf(key);
-        return index < 0 ? null : values[index];
+        return index == -1 ? null : toExternal(values[index]);
     }
 
     @Override
     public V put(int key, V value) {
-        int hash = hash(key);
-        int capacity = capacity();
-        int index = hash % capacity;
-        int increment = 1 + hash % (capacity - 2);
-        final int startIndex = index;
-        int firstRemovedIndex = -1;
-        do {
-            switch (states[index]) {
-                case AVAILABLE:
-                    // We only stop probing at a AVAILABLE node, since the value may still exist
-                    // beyond
-                    // a REMOVED node.
-                    if (firstRemovedIndex != -1) {
-                        // We encountered a REMOVED node prior. Store the entry there so that
-                        // retrieval
-                        // will be faster.
-                        insertAt(firstRemovedIndex, key, value);
-                        return null;
-                    }
-
-                    // No REMOVED node, just store the entry here.
-                    insertAt(index, key, value);
-                    return null;
-                case OCCUPIED:
-                    if (keys[index] == key) {
-                        V previousValue = values[index];
-                        insertAt(index, key, value);
-                        return previousValue;
-                    }
-                    break;
-                case REMOVED:
-                    // Check for first removed index.
-                    if (firstRemovedIndex == -1) {
-                        firstRemovedIndex = index;
-                    }
-                    break;
-                default:
-                    throw new AssertionError("Invalid state: " + states[index]);
+        int startIndex = hashIndex(key);
+        int index = startIndex;
+
+        for (;;) {
+            if (values[index] == null) {
+                // Found empty slot, use it.
+                keys[index] = key;
+                values[index] = toInternal(value);
+                growSize();
+                return null;
+            } else if (keys[index] == key) {
+                // Found existing entry with this key, just replace the value.
+                V previousValue = values[index];
+                values[index] = toInternal(value);
+                return toExternal(previousValue);
             }
 
-            // REMOVED or OCCUPIED but wrong key, keep probing ...
-            index += increment;
-            if (index >= capacity) {
-                // Handle wrap-around by decrement rather than mod.
-                index -= capacity;
+            // Conflict, keep probing ...
+            if ((index = probeNext(index)) == startIndex) {
+                // Can only happen if the map was full at MAX_ARRAY_SIZE and couldn't grow.
+                throw new IllegalStateException("Unable to insert");
             }
-        } while (index != startIndex);
-
-        if (firstRemovedIndex == -1) {
-            // Should never happen.
-            throw new AssertionError("Unable to insert");
         }
+    }
 
-        // Never found a AVAILABLE slot, just use the first REMOVED.
-        insertAt(firstRemovedIndex, key, value);
-        return null;
+    private int probeNext(int index) {
+        return index == values.length - 1 ? 0 : index + 1;
     }
 
     @Override
@@ -162,9 +136,11 @@ public void putAll(IntObjectMap<V> sourceMap) {
         if (sourceMap instanceof IntObjectHashMap) {
             // Optimization - iterate through the arrays.
             IntObjectHashMap<V> source = (IntObjectHashMap<V>) sourceMap;
-            int i = -1;
-            while ((i = source.nextEntryIndex(i + 1)) >= 0) {
-                put(source.keys[i], source.values[i]);
+            for (int i = 0; i < source.values.length; ++i) {
+                V sourceValue = source.values[i];
+                if (sourceValue != null) {
+                    put(source.keys[i], sourceValue);
+                }
             }
             return;
         }
@@ -178,13 +154,13 @@ public void putAll(IntObjectMap<V> sourceMap) {
     @Override
     public V remove(int key) {
         int index = indexOf(key);
-        if (index < 0) {
+        if (index == -1) {
             return null;
         }
 
         V prev = values[index];
         removeAt(index);
-        return prev;
+        return toExternal(prev);
     }
 
     @Override
@@ -199,10 +175,9 @@ public boolean isEmpty() {
 
     @Override
     public void clear() {
-        Arrays.fill(states, AVAILABLE);
+        Arrays.fill(keys, 0);
         Arrays.fill(values, null);
         size = 0;
-        available = capacity();
     }
 
     @Override
@@ -212,10 +187,10 @@ public boolean containsKey(int key) {
 
     @Override
     public boolean containsValue(V value) {
-        int i = -1;
-        while ((i = nextEntryIndex(i + 1)) >= 0) {
-            V next = values[i];
-            if (value == next || value != null && value.equals(next)) {
+        V v = toInternal(value);
+        for (int i = 0; i < values.length; ++i) {
+            // The map supports null values; this will be matched as NULL_VALUE.equals(NULL_VALUE).
+            if (values[i] != null && values[i].equals(v)) {
                 return true;
             }
         }
@@ -235,7 +210,12 @@ public Iterator<Entry<V>> iterator() {
     @Override
     public int[] keys() {
         int[] outKeys = new int[size()];
-        copyEntries(keys, outKeys);
+        int targetIx = 0;
+        for (int i = 0; i < values.length; ++i) {
+            if (values[i] != null) {
+                outKeys[targetIx++] = keys[i];
+            }
+        }
         return outKeys;
     }
 
@@ -243,58 +223,63 @@ public int[] keys() {
     public V[] values(Class<V> clazz) {
         @SuppressWarnings("unchecked")
         V[] outValues = (V[]) Array.newInstance(clazz, size());
-        copyEntries(values, outValues);
+        int targetIx = 0;
+        for (int i = 0; i < values.length; ++i) {
+            if (values[i] != null) {
+                outValues[targetIx++] = values[i];
+            }
+        }
         return outValues;
     }
 
     @Override
     public int hashCode() {
-        final int prime = 31;
-        int result = 1;
-        for (Entry<V> entry : entries()) {
-            V value = entry.value();
-            int hash = value == null ? 0 : value.hashCode();
-            result = prime * result + hash;
+        // Hashcode is based on all non-zero, valid keys. We have to scan the whole keys
+        // array, which may have different lengths for two maps of same size(), so the
+        // capacity cannot be used as input for hashing but the size can.
+        int hash = size;
+        for (int i = 0; i < keys.length; ++i) {
+            // 0 can be a valid key or unused slot, but won't impact the hashcode in either case.
+            // This way we can use a cheap loop without conditionals, or hard-to-unroll operations,
+            // or the devastatingly bad memory locality of visiting value objects.
+            // Also, it's important to use a hash function that does not depend on the ordering
+            // of terms, only their values; since the map is an unordered collection and
+            // entries can end up in different positions in different maps that have the same
+            // elements, but with different history of puts/removes, due to conflicts.
+            hash = hash ^ keys[i];
         }
-        return result;
+        return hash;
     }
 
     @Override
     public boolean equals(Object obj) {
-        if (this == obj || obj == null || getClass() != obj.getClass()) {
+        if (this == obj) {
             return true;
+        } else if (!(obj instanceof IntObjectMap)) {
+            return false;
         }
         @SuppressWarnings("rawtypes")
-        IntObjectHashMap other = (IntObjectHashMap) obj;
-        if (size != other.size) {
+        IntObjectMap other = (IntObjectMap) obj;
+        if (size != other.size()) {
             return false;
         }
-        for (Entry<V> entry : entries()) {
-            V value = entry.value();
-            Object otherValue = other.get(entry.key());
-            if (value == null) {
-                if (otherValue != null || !other.containsKey(entry.key())) {
+        for (int i = 0; i < values.length; ++i) {
+            V value = values[i];
+            if (value != null) {
+                int key = keys[i];
+                Object otherValue = other.get(key);
+                if (value == NULL_VALUE) {
+                    if (otherValue != null) {
+                      return false;
+                    }
+                } else if (!value.equals(otherValue)) {
                     return false;
                 }
-            } else if (!value.equals(otherValue)) {
-                return false;
             }
         }
         return true;
     }
 
-    /**
-     * Copies the occupied entries from the source to the target array.
-     */
-    private void copyEntries(Object sourceArray, Object targetArray) {
-        int sourceIx = -1;
-        int targetIx = 0;
-        while ((sourceIx = nextEntryIndex(sourceIx + 1)) >= 0) {
-            Object obj = Array.get(sourceArray, sourceIx);
-            Array.set(targetArray, targetIx++, obj);
-        }
-    }
-
     /**
      * Locates the index for the given key. This method probes using double hashing.
      *
@@ -302,117 +287,94 @@ private void copyEntries(Object sourceArray, Object targetArray) {
      * @return the index where the key was found, or {@code -1} if no entry is found for that key.
      */
     private int indexOf(int key) {
-        int hash = hash(key);
-        int capacity = capacity();
-        int increment = 1 + hash % (capacity - 2);
-        int index = hash % capacity;
-        int startIndex = index;
-        do {
-            switch(states[index]) {
-                case AVAILABLE:
-                    // It's available, so no chance that this value exists anywhere in the map.
-                    return -1;
-                case OCCUPIED:
-                    if (key == keys[index]) {
-                        // Found it!
-                        return index;
-                    }
-                    break;
-                default:
-                    break;
+        int startIndex = hashIndex(key);
+        int index = startIndex;
+
+        for (;;) {
+            if (values[index] == null) {
+                // It's available, so no chance that this value exists anywhere in the map.
+                return -1;
+            } else if (key == keys[index]) {
+                return index;
             }
 
-            // REMOVED or OCCUPIED but wrong key, keep probing ...
-            index += increment;
-            if (index >= capacity) {
-                // Handle wrap-around by decrement rather than mod.
-                index -= capacity;
+            // Conflict, keep probing ...
+            if ((index = probeNext(index)) == startIndex) {
+                return -1;
             }
-        } while (index != startIndex);
-
-        // Got back to the beginning. Not found.
-        return -1;
-    }
-
-    /**
-     * Determines the current capacity (i.e. size of the arrays).
-     */
-    private int capacity() {
-        return keys.length;
+        }
     }
 
     /**
-     * Creates a hash value for the given key.
+     * Returns the hashed index for the given key.
      */
-    private static int hash(int key) {
-        // Just make sure the integer is positive.
-        return key & Integer.MAX_VALUE;
+    private int hashIndex(int key) {
+        return key % keys.length;
     }
 
     /**
-     * Performs an insert of the key/value at the given index position. If necessary, performs a
-     * rehash of the map.
-     *
-     * @param index the index at which to insert the key/value
-     * @param key the entry key
-     * @param value the entry value
+     * Grows the map size after an insertion. If necessary, performs a rehash of the map.
      */
-    private void insertAt(int index, int key, V value) {
-        byte state = states[index];
-        if (state != OCCUPIED) {
-            // Added a new mapping, increment the size.
-            size++;
-
-            if (state == AVAILABLE) {
-                // Consumed a OCCUPIED slot, decrement the number of available slots.
-                available--;
-            }
-        }
-
-        keys[index] = key;
-        values[index] = value;
-        states[index] = OCCUPIED;
+    private void growSize() {
+        size++;
 
         if (size > maxSize) {
-            // Need to grow the arrays.
-            rehash(adjustCapacity(capacity() * 2));
-        } else if (available == 0) {
+            // Need to grow the arrays. We take care to detect integer overflow,
+            // also limit array size to ArrayList.MAX_ARRAY_SIZE.
+            rehash(adjustCapacity((int) Math.min(keys.length * 2.0, Integer.MAX_VALUE - 8)));
+        } else if (size == keys.length) {
             // Open addressing requires that we have at least 1 slot available. Need to refresh
             // the arrays to clear any removed elements.
-            rehash(capacity());
+            rehash(keys.length);
         }
     }
 
     /**
      * Adjusts the given capacity value to ensure that it's odd. Even capacities can break probing.
-     * TODO: would be better to ensure it's prime as well.
      */
     private static int adjustCapacity(int capacity) {
         return capacity | 1;
     }
 
     /**
-     * Marks the entry at the given index position as {@link #REMOVED} and sets the value to
-     * {@code null}.
-     * <p>
-     * TODO: consider performing re-compaction.
+     * Removes entry at the given index position. Also performs opportunistic, incremental rehashing
+     * if necessary to not break conflict chains.
      *
      * @param index the index position of the element to remove.
      */
     private void removeAt(int index) {
-        if (states[index] == OCCUPIED) {
-            size--;
-        }
-        states[index] = REMOVED;
+        --size;
+        // Clearing the key is not strictly necessary (for GC like in a regular collection),
+        // but recommended for security. The memory location is still fresh in the cache anyway.
+        keys[index] = 0;
         values[index] = null;
+
+        // In the interval from index to the next available entry, the arrays may have entries
+        // that are displaced from their base position due to prior conflicts. Iterate these
+        // entries and move them back if possible, optimizing future lookups.
+        // Knuth Section 6.4 Algorithm R, also used by the JDK's IdentityHashMap.
+
+        int nextFree = index;
+        for (int i = probeNext(index); values[i] != null; i = probeNext(i)) {
+            int bucket = hashIndex(keys[i]);
+            if ((i < bucket && (bucket <= nextFree || nextFree <= i))
+                    || (bucket <= nextFree && nextFree <= i)) {
+                // Move the displaced entry "back" to the first available position.
+                keys[nextFree] = keys[i];
+                values[nextFree] = values[i];
+                // Put the first entry after the displaced entry
+                keys[i] = 0;
+                values[i] = null;
+                nextFree = i;
+            }
+        }
     }
 
     /**
      * Calculates the maximum size allowed before rehashing.
      */
     private int calcMaxSize(int capacity) {
-        // Clip the upper bound so that there will always be at least one
-        // available slot.
+        // Clip the upper bound so that there will always be at least one available slot.
         int upperBound = capacity - 1;
         return Math.min(upperBound, (int) (capacity * loadFactor));
     }
@@ -423,61 +385,62 @@ private int calcMaxSize(int capacity) {
      * @param newCapacity the new capacity for the map.
      */
     private void rehash(int newCapacity) {
-        int oldCapacity = capacity();
         int[] oldKeys = keys;
         V[] oldVals = values;
-        byte[] oldStates = states;
 
-        // New states array is automatically initialized to AVAILABLE (i.e. 0 == AVAILABLE).
-        states = new byte[newCapacity];
         keys = new int[newCapacity];
-        @SuppressWarnings({ "unchecked", "SuspiciousArrayCast" })
+        @SuppressWarnings({ "unchecked" })
         V[] temp = (V[]) new Object[newCapacity];
         values = temp;
 
-        size = 0;
-        available = newCapacity;
         maxSize = calcMaxSize(newCapacity);
 
-        // Insert the new states.
-        for (int i = 0; i < oldCapacity; ++i) {
-            if (oldStates[i] == OCCUPIED) {
-                put(oldKeys[i], oldVals[i]);
-            }
-        }
-    }
+        // Insert to the new arrays.
+        for (int i = 0; i < oldVals.length; ++i) {
+            V oldVal = oldVals[i];
+            if (oldVal != null) {
+                // Inlined put(), but much simpler: we don't need to worry about
+                // duplicated keys, growing/rehashing, or failing to insert.
+                int oldKey = oldKeys[i];
+                int startIndex = hashIndex(oldKey);
+                int index = startIndex;
+
+                for (;;) {
+                    if (values[index] == null) {
+                        keys[index] = oldKey;
+                        values[index] = toInternal(oldVal);
+                        break;
+                    }
 
-    /**
-     * Returns the next index of the next entry in the map.
-     *
-     * @param index the index at which to begin the search.
-     * @return the index of the next entry, or {@code -1} if not found.
-     */
-    private int nextEntryIndex(int index) {
-        int capacity = capacity();
-        for (; index < capacity; ++index) {
-            if (states[index] == OCCUPIED) {
-                return index;
+                    // Conflict, keep probing. Can wrap around, but never reaches startIndex again.
+                    index = probeNext(index);
+                }
             }
         }
-        return -1;
     }
 
     /**
      * Iterator for traversing the entries in this map.
      */
-    private final class IteratorImpl implements Iterator<Entry<V>> {
-        int prevIndex;
-        int nextIndex;
-
-        IteratorImpl() {
-            prevIndex = -1;
-            nextIndex = nextEntryIndex(0);
+    private final class IteratorImpl implements Iterator<Entry<V>>, Entry<V> {
+        private int prevIndex = -1;
+        private int nextIndex = -1;
+        private int entryIndex = -1;
+
+        private void scanNext() {
+            for (;;) {
+                if (++nextIndex == values.length || values[nextIndex] != null) {
+                    break;
+                }
+            }
         }
 
         @Override
         public boolean hasNext() {
-            return nextIndex >= 0;
+            if (nextIndex == -1) {
+                scanNext();
+            }
+            return nextIndex < keys.length;
         }
 
         @Override
@@ -487,43 +450,54 @@ public Entry<V> next() {
             }
 
             prevIndex = nextIndex;
-            nextIndex = nextEntryIndex(nextIndex + 1);
-            return new EntryImpl(prevIndex);
+            scanNext();
+
+            // Always return the same Entry object, just change its index each time.
+            entryIndex = prevIndex;
+            return this;
         }
 
         @Override
         public void remove() {
             if (prevIndex < 0) {
-                throw new IllegalStateException("Next must be called before removing.");
+                throw new IllegalStateException("next must be called before each remove.");
             }
             removeAt(prevIndex);
             prevIndex = -1;
         }
-    }
 
-    /**
-     * {@link Entry} implementation that just references the key/value at the given index position.
-     */
-    private final class EntryImpl implements Entry<V> {
-        final int index;
-
-        EntryImpl(int index) {
-            this.index = index;
-        }
+        // Entry implementation. Since this implementation uses a single Entry, we coalesce that
+        // into the Iterator object (potentially making loop optimization much easier).
 
         @Override
         public int key() {
-            return keys[index];
+            return keys[entryIndex];
         }
 
         @Override
         public V value() {
-            return values[index];
+            return toExternal(values[entryIndex]);
         }
 
         @Override
         public void setValue(V value) {
-            values[index] = value;
+            values[entryIndex] = toInternal(value);
+        }
+    }
+
+    @Override
+    public String toString() {
+        if (size == 0) {
+            return "{}";
+        }
+        StringBuilder sb = new StringBuilder(4 * size);
+        for (int i = 0; i < values.length; ++i) {
+            V value = values[i];
+            if (value != null) {
+                sb.append(sb.length() == 0 ? "{" : ", ");
+                sb.append(keys[i]).append('=').append(value == this ? "(this Map)" : value);
+            }
         }
+        return sb.append('}').toString();
     }
 }


Test patch:
diff --git a/common/src/test/java/io/netty/util/collection/IntObjectHashMapTest.java b/common/src/test/java/io/netty/util/collection/IntObjectHashMapTest.java
index 7f50134ef85..ec291df8748 100644
--- a/common/src/test/java/io/netty/util/collection/IntObjectHashMapTest.java
+++ b/common/src/test/java/io/netty/util/collection/IntObjectHashMapTest.java
@@ -14,14 +14,21 @@
  */
 package io.netty.util.collection;
 
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNull;
+import static org.junit.Assert.assertSame;
+import static org.junit.Assert.assertTrue;
+
 import org.junit.Before;
 import org.junit.Test;
 
+import java.util.Arrays;
+import java.util.HashMap;
 import java.util.HashSet;
+import java.util.Random;
 import java.util.Set;
 
-import static org.junit.Assert.*;
-
 /**
  * Tests for {@link IntObjectHashMap}.
  */
@@ -279,4 +286,121 @@ public void valuesShouldBeReturned() {
         }
         assertEquals(expected, found);
     }
+
+    @Test
+    public void mapShouldSupportHashingConflicts() {
+        for (int mod = 0; mod < 10; ++mod) {
+            for (int sz = 1; sz <= 101; sz += 2) {
+                IntObjectHashMap<String> map = new IntObjectHashMap<String>(sz);
+                for (int i = 0; i < 100; ++i) {
+                    map.put(i * mod, "");
+                }
+            }
+        }
+    }
+
+    @Test
+    public void hashcodeEqualsTest() {
+        IntObjectHashMap<Integer> map1 = new IntObjectHashMap<Integer>();
+        IntObjectHashMap<Integer> map2 = new IntObjectHashMap<Integer>();
+        Random rnd = new Random(0);
+        while (map1.size() < 100) {
+            int key = rnd.nextInt(100);
+            map1.put(key, key);
+            map2.put(key, key);
+        }
+        assertEquals(map1.hashCode(), map2.hashCode());
+        assertTrue(map1.equals(map2));
+        // Remove one "middle" element, maps should now be non-equals.
+        int[] keys = map1.keys();
+        map2.remove(keys[50]);
+        assertFalse(map1.equals(map2));
+        // Put it back; will likely be in a different position, but maps will be equal again.
+        map2.put(keys[50], map1.keys()[50]);
+        assertTrue(map1.equals(map2));
+        assertEquals(map1.hashCode(), map2.hashCode());
+        // Make map2 have one extra element, will be non-equal.
+        map2.put(1000, 1000);
+        assertFalse(map1.equals(map2));
+        // Rebuild map2 with elements in a different order, again the maps should be equal.
+        // (These tests with same elements in different order also show that the hashCode
+        // function does not depend on the internal ordering of entries.)
+        map2.clear();
+        Arrays.sort(keys);
+        for (int key : keys) {
+            map2.put(key, key);
+        }
+        assertEquals(map1.hashCode(), map2.hashCode());
+        assertTrue(map1.equals(map2));
+    }
+
+    @Test
+    public void fuzzTest() {
+        // This test is so extremely internals-dependent that I'm not even trying to
+        // minimize that. Any internal changes will not fail the test (so it's not flaky per se)
+        // but will possibly make it less effective (not test interesting scenarios anymore).
+
+        // The RNG algorithm is specified and stable, so this will cause the same exact dataset
+        // to be used in every run and every JVM implementation.
+        Random rnd = new Random(0);
+
+        int baseSize = 1000;
+        // Empirically-determined size to expand the capacity exactly once, and before
+        // the step that creates the long conflict chain. We need to test rehash(),
+        // but also control when rehash happens because it cleans up the REMOVED entries.
+        // This size is also chosen so after the single rehash, the map will be densely
+        // populated, getting close to a second rehash but not triggering it.
+        int startTableSize = 1105;
+        IntObjectHashMap<Integer> map = new IntObjectHashMap<Integer>(startTableSize);
+        // Reference map which implementation we trust to be correct, will mirror all operations.
+        HashMap<Integer, Integer> goodMap = new HashMap<Integer, Integer>();
+
+        // Add initial population.
+        for (int i = 0; i < baseSize / 4; ++i) {
+            int key = rnd.nextInt(baseSize);
+            assertEquals(goodMap.put(key, key), map.put(key, key));
+            // 50% elements are multiple of a divisor of startTableSize => more conflicts.
+            key = rnd.nextInt(baseSize) * 17;
+            assertEquals(goodMap.put(key, key), map.put(key, key));
+        }
+
+        // Now do some mixed adds and removes for further fuzzing
+        // Rehash will happen here, but only once, and the final size will be closer to max.
+        for (int i = 0; i < baseSize * 1000; ++i) {
+            int key = rnd.nextInt(baseSize);
+            if (rnd.nextDouble() >= 0.2) {
+                assertEquals(goodMap.put(key, key), map.put(key, key));
+            } else {
+                assertEquals(goodMap.remove(key), map.remove(key));
+            }
+        }
+
+        // Final batch of fuzzing, only searches and removes.
+        int removeSize = map.size() / 2;
+        while (removeSize > 0) {
+            int key = rnd.nextInt(baseSize);
+            boolean found = goodMap.containsKey(key);
+            assertEquals(found, map.containsKey(key));
+            assertEquals(goodMap.remove(key), map.remove(key));
+            if (found) {
+                --removeSize;
+            }
+        }
+
+        // Now gotta write some code to compare the final maps, as equals() won't work.
+        assertEquals(goodMap.size(), map.size());
+        Integer[] goodKeys = goodMap.keySet().toArray(new Integer[goodMap.size()]);
+        Arrays.sort(goodKeys);
+        int [] keys = map.keys();
+        Arrays.sort(keys);
+        for (int i = 0; i < goodKeys.length; ++i) {
+            assertEquals((int) goodKeys[i], keys[i]);
+        }
+
+        // Finally drain the map.
+        for (int key : map.keys()) {
+            assertEquals(goodMap.remove(key), map.remove(key));
+        }
+        assertTrue(map.isEmpty());
+    }
 }