3

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.

Moritz
  • 43
  • 7

7 Answers7

3

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.

Philip Tenn
  • 6,003
  • 8
  • 48
  • 85
  • Array lookup would be O(1) if he stored the data by index. The waste is in memory footprint of a mostly empty array. – JohnnyO Jan 23 '13 at 01:26
  • @JohnnyO so Array and Map would have the same lookup but Map should be preferred because of memory usage? And which Map will handle Integers best? HashMap? – Moritz Jan 23 '13 at 01:32
  • @JohnnyO I agree on the waste of the memory footprint for the sparsely-populated Array. – Philip Tenn Jan 23 '13 at 01:33
  • @JohnnyO You are correct on the Array lookup performance, thank you. – Philip Tenn Jan 23 '13 at 01:37
  • @PhilipTenn you should remove "performance will be better using a map" – Moritz Jan 23 '13 at 01:41
  • @Moritz no they do not have the same lookup. there is nothing faster than a direct array lookup. The Big O Notation is in most cases practically misleading, because O(1) is short for c*O(1), and c can be 1000 in one case and e.g 5 for another case. – AlexWien Jan 23 '13 at 01:43
  • @AlexWien thats what I meant - the array has better performance than the map - so he needs to adjust that – Moritz Jan 23 '13 at 01:46
  • @PhilipTenn that depends on the app, whether or not the speed factor can be ignored. in most cases you can ignore it. – AlexWien Jan 23 '13 at 02:14
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.

AlexWien
  • 28,470
  • 6
  • 53
  • 83
  • This is what the sparse array in android does ... I will have a further look at that 2mrw – Moritz Jan 23 '13 at 02:17
  • you can do that yourself, use an arraylist to dynamically build up initially the index, then sort, and create the fixed idx[] array. ready. – AlexWien Jan 23 '13 at 02:19
1

I would use a Map because this is really what it's made for. And beyond that, using a Map will likely make your code much easier to update and manage in the future. As for which implementation you should use, it seems to me that a HashMap would suffice, although if you want to keep your integer keys in order you might want to also consider a TreeMap.

arshajii
  • 127,459
  • 24
  • 238
  • 287
1

The array is obviously going to give you the fastest access, but if you have gaps like that, you're going to waste a fair amount of space.

If you're looking for a flexible data structure that associates a key (such as an integer) with a value, where there may be gaps in the range, and you may increase it later, I can't think of anything more appropriate than a Map. If you know exactly how many elements you plan to insert, you might want to investigate the constructor parameters to implementations such as HashMap, which let you tune the size of the underlying storage toward less space vs less collisions.

The other upshot of a Map is you get a much richer API should you need to do other collection-oriented tasks with it.

Chuck Adams
  • 777
  • 6
  • 18
1

As you say a map is a good way of doing exactly that. I usually use a hash map as it is exceptionally fast. Not as fast as an array though. If you have only one key per value you may even want to use a HashSet as it will ensure only one value is used per key.

The android API has something called a SparseIntArray that is supposed to have better performance, but I haven't seen it in the standard java API.

If performance is really important you may find the trove library has a appropriate sparse array or map. It only tends to be faster when you're using primitives (which in your case you are)

user1855149
  • 93
  • 5
1

What you actually want is a SparseArray. It is a the compromise between a normal map and the an array.

If you are developing for Android, one is available for you (see link below). Otherwise, you can probably find an available implementation.

http://developer.android.com/reference/android/util/SparseArray.html

JohnnyO
  • 3,018
  • 18
  • 30
  • someone found a good implementation? (I am not developing for android) – Moritz Jan 23 '13 at 01:50
  • The source code from the Android version is Apache licensed and easy to find (Google: SparseArray source code), it could be easily adapted to your needs – JohnnyO Jan 23 '13 at 04:10
0

I would recommend a map for one reason: variable length. It will probably become rather tedious to keep track of how may objects you need to map. Using a HashMap or similar implementation will guarantee that you always have sufficient capacity in your mapping object. Other than that, it simply makes more sense to use a Map because that is what is designed to do, making your code more readable to others. I suppose a raw array would take less memory, but realistically the overhead for a map will not be very significant for the scales your talking about.

ApproachingDarknessFish
  • 14,133
  • 7
  • 40
  • 79