Is there a HashMap implementation in Java that produces no garbage?

Yes. Take a look e.g. at Goldman Sachs collections.

They have a complete reimplementation of the JDK's collection framework (and much more) with an emphasis on low memory footprint. For example, their HashMap doesn't create the Entry objects until they really need to. Look at the documentation here.

There's also Javolution, a smaller library with a slightly different purpose - mainly for close-to-realtime and time-predictable classes, this also implies low garbage.

If you want to store primitives (which avoids the creation of their wrappers), look at one of these:

• Trove - the "standard" collections for primitives
• Goldman Sachs collections, again
• HPPC - lower level access, often slightly faster than Trove, but enables you to shoot yourself into the foot more easily
• Koloboke - a Trove fork made by people from OpenHFT. Insanely fast, evolving fast. As of now (September 2014), only Maps and Sets are supported.

EDIT 2020:

Also see https://github.com/TimeAndSpaceIO/SmoothieMap.

We have also written a collection of data structures called CoralBits that provides high-performance with zero garbage creation. It re-uses iterators and pools map entry objects. For maps that use primitives as keys, we wrote IntMap and LongMap. For a general purpose map we wrote PooledHashMap which implements java.util.Map so you can swap in your code for zero garbage.

Trove and Javolution are other alternatives but we have found that Javolution creates garbage in some situations.

CoralBits also provides a MemorySampler instrumentation class that you can use to find out where garbage is being created in your code. In the case of a java.util.HashMap the culprit is:

java.util.HashMap.createEntry(HashMap.java:901)

You can take a look in this article written by me that gives an example of how to use MemorySampler to detect garbage in your applications.

Disclaimer: I am one of the developers of CoralBits.