6

The API documentation for Android's SparseIntArray opens with:

SparseIntArrays map integers to integers.

I'm curious, then, why it doesn't implement Map<Integer, Integer>.

It seems to me that all that would've been required is a couple of different method names, a few trivial extra methods, and a bit of code to prohibit null keys and values... certainly nothing that an EnumMap doesn't handle with grace. Am I overlooking something?

This isn't intended to be a swipe at the designers of the Android API. Normally when I wonder things like this, there turns out to be a good reason, and I learn something about the language or platform.

Community
  • 1
  • 1
Michael Scheper
  • 6,514
  • 7
  • 63
  • 76
  • http://grepcode.com/file/repository.grepcode.com/java/ext/com.google.android/android/4.4.2_r1/android/util/SparseIntArray.java/. Check this if it helps – Raghunandan Feb 28 '14 at 05:35
  • I would assume it is because implementing the Map interface would result in heavy functions (boxing the keys, creating the sets of values and of keys,...) while the functions define in SparseIntArray are designed for efficiency. Having both would be counter-productive. – njzk2 Dec 22 '15 at 16:49
  • keep in mind that all those methods are mandatory in map: http://developer.android.com/reference/java/util/Map.html (also, if you call it a map for higher abstraction, you can't use the SparseIntArray specific functions. And iterating using `size` and `keyAt` is designed to be more efficient that the `entrySet` from `Map`, while being a little less convenient) – njzk2 Dec 22 '15 at 16:51

3 Answers3

3

JavaDoc for SparseIntArray also says

SparseIntArrays map integers to integers. Unlike a normal array of integers, there can be gaps in the indices. It is intended to be more memory efficient than using a HashMap to map Integers to Integers, both because it avoids auto-boxing keys and values and its data structure doesn't rely on an extra entry object for each mapping.

We can derive following reasons for the choice of SparseIntArray over Map< Integer,Integer > :

  • Since we wanted to have mapping between primitive ints, it will be good to avoid autoboxing.
  • In Map, having an object as key/value comes with heaviness of hash calculation, resolving of hash collision, linking of multiple entries in a single bucket etc. These won't be necessary as we are dealing with primitive key/value pairs. Note that SparseIntArray comes with performance warning. Since values are stored in binary search tree array data structure, insertions and deletions will be costly operations. Hence, its a good choice for small set of data.

As a side point, I would say JavaDoc should be more specific by saying

"SparseIntArrays map primitive integers to integers."

rather than saying

"SparseIntArrays map integers to integers."

Omkar Shetkar
  • 3,488
  • 5
  • 35
  • 50
  • 2
    Sorry; I don't see how this answers the question. AFAIK, the Map interface doesn't define how an implementation works under the bonnet, nor how efficient it is—I believe that's the whole point. – Michael Scheper Sep 16 '14 at 19:09
  • I probably misinterpreted your question. It is more of interface and design choice for SparseIntArray. Will keep you posted once got any clue. – Omkar Shetkar Sep 17 '14 at 02:51
  • Yep. The question is why they made that choice. – Michael Scheper Sep 17 '14 at 20:47
  • 1
    As stated in the doc above, it avoids auto-boxing and works directly with primitive integers (not `Integer` wrappers). See: http://docs.oracle.com/javase/tutorial/java/data/autoboxing.html – Kevin Coppock Sep 17 '14 at 20:55
  • @kcoppock: Good point! If you write that as an answer, I'll accept it. – Michael Scheper Dec 14 '15 at 00:32
  • @michaelscheper looks like it's noted in Omkar's answer already (just past the bolded region) – Kevin Coppock Dec 14 '15 at 01:39
  • Well, if that really was @Omkar's point, I'll leave it to him to edit his answer to make it more clear. He emphasised a different part of the citation, and didn't mention primitive `int`s at all. – Michael Scheper Dec 14 '15 at 01:47
  • 1
    @MichaelScheper Edited my answer after some more analysis of SparseIntArray. :) – Omkar Shetkar Dec 22 '15 at 16:49
  • _In Map, having an object as key/value comes with heaviness of hash calculation_: Actually, if `SparseIntArray` implemented the `Map` interface, `hashCode()` could simply return the key—an O(1) operation, thus the opposite of 'heavy' by definition. – Michael Scheper Dec 22 '15 at 19:28
  • @MichaelScheper, yes. that's true. My second point is more of API implementation specific. In ideal case, hash code can map to particular index in the array. Since it is not feasible(due to limited memory), it would be better to find an index for the given key with no possibility of hash collision. In this respect SparseIntArray does well by having data stored in binary search array data structure. – Omkar Shetkar Dec 23 '15 at 02:56
  • -1 since the first point of the anser does not appear to answer any part of the question and I find the boxing hint (which would be the main answer) is rather unsatisfying. – IARI Jan 25 '17 at 17:38
1

  • Implementing Map is very heavy. You need methods like entrySet and keySet which is not convenient in SparseIntArray.

  • Map keys are Objects, so you need constant boxing/unboxing.

  • SparseIntArray suggests a different way of enumerating through a Map, using its specific keyAt and valueAt, which are very fast.

If SparseIntArray implemented Map<Integer, Integer> you would be tempted to write:

Map<Integer, Integer> intMap = new SparseIntArray();

But then you'd be stuck with only what enumeration capability Map provides.

njzk2
  • 38,969
  • 7
  • 69
  • 107
  • 1st point: I disagree. `entrySet` and `keySet` wouldn't be hard to implement, would run in _n_ time, and have no performance penalty if they were unused. 2nd point: Yep, I think that's the real answer, but Omkar beat you to it. :-) 3rd point: This doesn't answer the question _why_. It is indeed what prompted the question—nonstandard API is a pain. – Michael Scheper Dec 22 '15 at 19:23
0

If it implemented Map<Integer,Integer>, it would have to deal with Integer objects as input and output values instead of primitive int values, so the whole point of this class which is to avoid boxing would be lost.

BladeCoder
  • 12,779
  • 3
  • 59
  • 51