I find this part somewhat convoluted. Maybe try my PrimitiveKeyOpenHashMap? You would use slightly more space because of the hashmap overhead, but the code would be much simpler (ie no need to require with the monotonicity in map id). https://github.com/apache/incubator-spark/pull/70/files#diff-3