Android SparseArray with String key?

Question

I need to use a hashmap to store key / values in my Android app (potentially thousands), but I understand that I should be using SparseArray in order to save memory. However, my key needs to be a String. Is there a way to create a custom implementation of the SparseArray or some other alternative?

Solution 1

SparseArray is only a thing when integers are the key. It's a memory optimization that's only possible with integer values because you need to binary search the keys. Binary searches on strings are expensive and not well defined (should '1' be less than or greater than 'a' or 'crazy japanese character'?), so they don't do it.

BTW, SparseArray saves memory but may take more time. A get on a HashMap should be O(n/size) where size is the number of buckets in the hashmap. SparseArray is going to be O(log(n)). Which to use depends on memory and speed you need. If you have a truly large (100Ks of entries) you'll even run into memory paging issues where the physical realities of cache misses may cause the more HashMap to perform better even if its technically worse, because it will have a max of 1 cache miss per get, while a binary search may have multiple.

Solution 2

You can use ArrayMap : ArrayMap is a generic key->value mapping data structure that is designed to be more memory efficient than a traditional HashMap

For more information : ArrayMap Doc

Solution 3

You can use the hashCode of string -> mystring.hashCode()

Solution 4

SparseArray is a specialized class for maps that have integers as the key type. They basically use that fact to save the int value instead of a reference to an Integer object (hence the memory savings).

There is nothing inherently wrong with using a standardHashMap when the key is of any other type.

View more solutions

Comments

[Mike6679]

Hmmm.ok makes sense. What is best practice when you need to key on a String? Is hashmap the most efficient way possible for speed and memory?

[Gabe Sechan]

Pick one- memory or speed. You're not going to optimize for both. If you need speed, use a hash map. If you need memory go with something array based, a sorted list or a BST (which is what a lot of databases use, not a bad tradeoff with log(n) search and O(n) memory). But you aren't going to be able to optimize both. If you think that's going to be a pain point, isolate it in its own class so you can change the implementation later on.

[Mike6679]

I'm familiar with Binary Search Trees, but it keys on integers , how would I use BST if I need to key on a String value?

[Mike6679]

When keying on a String, is using a HashMap standard practice when: 1. I need to store thousands or even millions of entries and 2. keying on String to retrieve values? There is absolutely no better way for balancing memory and speed?

[Mike6679]

also doesn't using HashMap with thosands of entries on Android have the potential to cause "out of memory exceptions"?

[Gabe Sechan]

To key a BST on a string, you use either a string compare on each node, or you use the hash value of each string. The second is more common, but takes a bit more storage. Yes, a HashMap with thousands of entries could cause OOM issues. It depends on the capacity of the hash table and how much memory the values take (not to mention the rest of your app). Its one of those things you'd have to test and see.

[matiash]

@Mike if your strings are likely to have common prefixes, you might want to use a Radix Tree.

[Ranjithkumar]

@GabeSechan I have String keys only.. Then I am not able to SparseArray ahh?

[Gabe Sechan]

No you can't. You can use hash map instead