BasicDBObject preserves insertion order of keys - and really needs to - so keySet() is returned in insertion order, BUT it does not provide this functionality for entrySet() - which I generally use a lot more often than keySet() when iterating through maps.

Digging into the code I see BasicDBObject is a HashMap combined with an OrderedSet was used to maintain insertion key order, but entrySet is not overridden.

I'm guessing the original author was unaware of java.util.LinkedHashMap. I changed BasicDBObject to extend LinkedHashMap, and removed _keys. All unit tests pass. I'm seeing pretty significant speed improvements in some benchmarks I put together to compare implementations. And the code is a little simpler too.

I have attached a modified copy of BasicDBObject for consideration, as well as a copy of DBObjectTest that includes a new test - testEntrySetOrder that asserts that the entrySet and keySet are both maintained in insertion order.