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); 

Solution 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().

Solution 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 
}

Solution 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);

Solution 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);
}

View more solutions

Comments

[magritte]

Thanks Sam, good spot on the overload, I've gone with your suggestion of just replacing with if (get(key) != null).

[user1991679]

Key may have null value, in that case with your code you won't be able to determine whether key exists or not. i.e. if key is not exists it'll return null and if key has null value it'll return null too. indexOfKey should be user in this case (See Alex's answer)

[auselen]

@user1991679 quite old answer and what you suggest is I guess via newer apis. However answer to your comment is, int primitive can't be null.

[user1991679]

I don't understand how the fact that primitive can't be null related to my comment. BTW, indexOfKey was introduced in API 1.

[auselen]

@uset1991679 ok I see what you mean now but I think question wasn't really about null values. Or that was my take.

[auselen]

@user1991679 thing is sparsearray isn't supposed to be a map. It is an array, very long one. Like normal array you should get an null value or reference back. If you need to check existance of keys then may be you need a map not an array. I think that's why Alex's answer is not relevant.

[auselen]

@user1991679 "key may have null value" -> "key may map to null value " I guess that's why I didn't get it first time.

[The incredible Jan]

I cannot understand where the connection from your answer to the questions is.

[Smar]

Is this better/worse than just using .get?

[mylovemhz]

.get(int) is O(1) because it's checking the underlying array directly. indexOf(int) is O(log(n)) because it does a binary search to find the right index

[Ace]

@mylovemhz Wrong! the int in get(int) is not an index, it's a key. Therefore, it's not O(1). Both get(int) and indexOfKey(int) have the same complexity O(log(n)), one returns the value in the position if found, null otherwise, the other only returns the index if found, a negative value otherwise.

[mylovemhz]

True, both get(int) and indexOfKey(int) do binary search. My mistake.

[Androidcoder]

I go with checking get() for null. What makes very new methods like contains() (API 30) hazardous is they will compile and run without warning if your test device API is high enough. Then later, older API user devices downloading the production code crash.