Mapping Objects to Integers in Java - use Array or Map?

Question

I have Objects which need to be mapped to Integers (or primitive ints).

So for example

Object[] objects = new Object[X];
objects[2]=o1;
objects[34]=o2;
objects[126]=o3;
...

So I have a range from 0 to X for the keys but only need a few (lets say 20) mapping pairs. (The mapping is only done once and will not change)

Would it be (performance and memory-usage vise) a better idea to use a Map (and if which implementation would suite best) instead of the "large" array which is mostly unused.

The needed range might actually scale up later during development - so if it is only important for very large X that would still be interesting for me. (Currently X is 256 - so rather small)

To sum it up: I want to efficiently map Numbers to Objects in Java.

Answer 1

Use a Map.

The performance difference should be negligible. Assuming that when you say "performance", you are referring to lookup (as you said the mapping is only done once and will not change), performance will be better using a direct Array lookup. With an array, your expected lookup will be O(1). If you have a map and are using the Integer as a Key, your lookup should be O(1) expected case and O(n) worst case. Given the small number of pairs you mentioned (20), the performance difference will not be significant.

However, the memory usage for the Map will be significantly better, since the Array will be sparsely-populated.

UPDATE

Thank you for everyone who provided comments and feedback and helping me learn. @JohnnyO was correct in stating that Array lookup is O(1), I corrected my post based on his feedback. I had been thinking ArrayList.

Answer 2

whether you use the fastest possibility (array) or a HashMap depends on your application. Do you have millions of calculations (array accesses) per second? Yes then take the array, and spend the 1k of memory.
Oherwise take the Map.
But there is a third solution if x is big: This solution is nearly as fast as the map (maybe faster), but uses less space:
Use a sorted array of int as index into an object array:

int[] idx ={2, 34, 126}
Object[] objs = {o1, o2, o3};

Idx must be sorted ascending. now get object for key 34:

int pos= Arrays.binsearch(34, idx); // params might be wrong, please correct
Object o = objs[pos];

But this i would use this only for a high number of objects with minimal storage space requirementm where objects do not change on runtime.