Is it okay to make Integer-keyed Maps in Java?

Question

Just like in title. Is it okay to make something like this:

HashMap<Integer, Object> foo = new HashMap<>();

Or maybe there's better container that allow adding values at any index? When saying "better" I mean "having better performance", and then "having less RAM usage".

ArrayList<Object> bar = new ArrayList<>();
bar.add(10_000, new Object());

A want to do something like in this code above, but this of course doesn't work with ArrayList. The list that I want to make is sparse; the indexes are spread - that's why I was thinking about HashMap and not ArrayList.

Regards.

Answer 1

Your questions is very generic, and from details you have specified it seems both HashMap and ArrayList fit your requirement and you are only bothered about performance. Performance has various aspects:

1. If your data is contiguous or less spread[i.e integers are more or less in sequence] then i would go for ArrayList as cost of insertion is less as compared to HashMap.
2. If your data has lots of spread or if you are going to perform lots of deleteion also along with insertion then i would go for HashMap.

So it depends on your requirement.

EDIT: If data has lots of spread then HashMap is the way to go. If you use Array or ArrayList then your memory consumption will become high due to lots of gaps in between storage of data. HashMap cost of insertion is higher than Array but then as you are concerened about RAM , you should go with HashMap.

Answer 2

What you are doing (in effect) is to use HashMap to represent a sparse array.

This can be a reasonable implementation choice, but its efficacy depends on what you are trying to achieve, and on the properties of the array.

If the array is sparse enough, then you will save memory by using a HashMap instead of a simple array. However compared to a non-sparse array, a HashMap uses roughly an order of magnitude more memory than an array. On top of that, the get and put operations on a HashMap are roughly an order of magnitude slower than indexing a simple array.

Also, depending on the size and sparseness of the array, there are representations that use significantly less space than a HashMap (e.g. the Android sparse array classes) at the cost of get/put performance that doesn't scale as well.