SparseArray, check if key exists

Question

I was implementing a Bitmap cache using a HashMap<Integer, Bitmap> and received the following warning in Eclipse:

Use new SparseArray(...) instead for better performance.

I've never heard of that class before, but inspecting it it doesn't seem to have a containsKey() method which I was calling on retrieval of a Bitmap from the cache to check if it exists in the cache, and if it doesn't, then add it.

Any ideas on the best way to check if the key already exists?

I guess I could change the code to use this overload and check for null?

Bitmap bitmap = cache.get(key, null); 

Answer 1

You could use:

Bitmap bitmap = cache.get(key, null); 

But understand that this is the same as get(key):

Bitmap bitmap = cache.get(key); 

The best way to use get(key, default) is to provide a generic default case, something to is a valid substitute when the key is not found.

But there is no good reason not to use if(get(key) != null) as a quick replacement for contains().

Answer 2

Hence your value can be null in various situations, I'd suggest to useindexOfKey(int key) Here is the indexOfKey(int key) reference.

Then just simply check for negative return value

if(mySparseArray.indexOfKey(int) < 0) {
   //Item does not exist. Do something relevant 
}

Answer 3

Quoting from documentation.

SparseArrays map integers to Objects. Unlike a normal array of Objects, there can be gaps in the indices. It is intended to be more efficient than using a HashMap to map Integers to Objects.

You can use get(int) which would also return null if key is not found. Like;

Bitmap bitmap = cache.get(key);

Answer 4

Going by the implementation of SparseArray it seems counter-intuitive that it may have better performance (time-complexity) than HashMap (other than lower space-requirement which makes sense for a mobile environment) since the get() member of SparseArray uses binary-search (O(log N)) while for HashMap uses array-indexing(O(1)).

Providing the get() method implementation for both the classes (as-is):

public V get(Object key) { // for HashMap
    if (key == null)
        return getForNullKey();
    int hash = hash(key.hashCode());
    for (Entry<K,V> e = table[indexFor(hash, table.length)];
            e != null;
            e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
            return e.value;
    }
    return null;
}

public E get(int key, E valueIfKeyNotFound) {  //for SparseArray
    int i = binarySearch(mKeys, 0, mSize, key);

    if (i < 0 || mValues[i] == DELETED) {
        return valueIfKeyNotFound;
    } else {
        return (E) mValues[i];
    }
}

as to whether to use indexOfKey(key) < 0 or get(key) == null for checking existence of key in a SparseArray, anything is ok since both use binary-search underneath.

public int indexOfKey(int key) {  // for SparseArray
    if (mGarbage) {
        gc();
    }

    return binarySearch(mKeys, 0, mSize, key);
}

Answer 5

Multiple ways:

1. If you want to use the value that is associated to the key anyway, you can use get() :

   val sparseArray = SparseArray<String>()
   val someKey = 123
   val someValue: String? = sparseArray[someKey]
   if(someValue!=null){
       //do something
   }
   

Note that as opposed to what the IDE thinks, it can be null, which is why I added ? .

2. if you just want to check if it exists, you can use indexOfKey(key) >= 0

3. If you don't like the above, and want a more readable option, you can use containsKey of the ktx-collection dependency:

   implementation 'androidx.core:core-ktx:#'
   implementation 'androidx.collection:collection-ktx:#'
   

Usage:

    val sparseArray = SparseArray<String>()
    val someKey = 123
    if (sparseArray.containsKey(someKey)) {
        //do something
    }