Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

I habitually use HashMap in my programs, since I know it is usually the most efficient (if properly used) and can cope with large maps easily. I know about EnumMap which is very useful for enumeration keys, but often I am generating a small map which will never get very big, is likely to be discarded pretty soon, and has no concurrency issues.

Is HashMap<K,V> too complicated for these small, local and temporary uses? Is there another, simple, implementation which I can use in these cases?

I think I'm looking for a Map implementation which is analogous to ArrayList for List. Does it exist?


Added later after responses:

Here is a scenario where a slow but very simple implementation might be better -- when I have many, many of these Maps. Suppose, for example, I have a million or so of these tiny little maps, each with a handful (often less than three) of entries. I have a low reference rate -- perhaps I don't actually reference them before they are discarded most of the time. Is it still the case that HashMap is the best choice for them?

Resource utilisation is more than just speed -- I would like something that doesn't fragment the heap a lot and make GCs take a long time, for example.

It may be that HashMap is the right answer, but this is not a case of premature optimisation (or at least it may not be).


Added much later after some thought:

I decided to hand-code my own SmallMap. It is easy to make one with AbstractMap. I have also added a couple of constructors so that a SmallMap can be constructed from an existing Map.

Along the way I had to decide how to represent Entrys and to implement SmallSet for the entrySet method.

I learned a lot by coding (and unit-testing this) and want to share this, in case anyone else wants one. It is on github here.

like image 859
Steve Powell Avatar asked Jan 12 '12 13:01

Steve Powell


People also ask

Which mapping is easy to implement?

It is easy to make one with AbstractMap . I have also added a couple of constructors so that a SmallMap can be constructed from an existing Map .

What type of Map should I use Java?

General-Purpose Map Implementations If you need SortedMap operations or key-ordered Collection -view iteration, use TreeMap ; if you want maximum speed and don't care about iteration order, use HashMap ; if you want near- HashMap performance and insertion-order iteration, use LinkedHashMap .

How do you increment the value of a Map?

We can also use AtomicInteger class and call getAndIncrement() or incrementAndGet() method to increment the value, as shown below. Another alternative could be to use MutableInt class which provides increment() method. AtomicInteger atomic = new AtomicInteger(map. containsKey(key) ?


1 Answers

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'.

like image 160
Steve Powell Avatar answered Oct 12 '22 06:10

Steve Powell