Which implementation of Map<K,V> should I use if my map needs to be small more than fast?

There is no standard small implementation of Map in Java. HashMap is one of the best and most flexible Map implementations around, and is hard to beat. However, in the very small requirement area -- where heap usage and speed of construction is paramount -- it is possible to do better.

I have implemented SmallCollections on GitHub to demonstrate how this might be done. I would love some comments on whether I have succeeded. It is by no means certain that I have.

Although the answers offered here were sometimes helpful, they tended, in general, to misunderstand the point. In any case, answering my own question was, in the end, much more useful to me than being given one.

The question here has served its purpose, and that is why I have 'answered it myself'.

I think this is premature optimization. Are you having memory problems? Performance problems from creating too many maps? If not I think HashMap is fine.

Besides, looking at the API, I'm not seeing anything simpler than a HashMap.

If you are having issue, you could roll your own Map implementation, that has very simple internals. But I doubt you would do better than default Map implementations, plus you have the overhead of making sure your new class works. In this case there might be a problem with your design.

A HashMap is possibly the most light weight and simple collection.

Sometimes the more efficient solution is to use a POJO. e.g. if your keys are field names and/or your values are primitives.