I've had the issue using maps with primitive keys. I solved it by isolating the performance critical functionality and not using the Collections framework there, instead writing my own data structure for it (with heavy influence from the hashmap one).

This tends to be my general philosophy, by the way. Reuse code to get something working fast, isolate what really causes bad performances, then solve only those problems by going under the hood. If the performance issues remain, cheat by pretending it doesn't exist, by making sure we're never in a worst case scenario and handling the worst case scenario differently.

In my "IntHashMap" case, the worst case scenario was gathering the keySet. I made sure that I'd only call it when I really really needed it. The rest was "fast enough" once I had removed the underlying Integer Object on the key.