Memory-efficient data structures in Android

Java and Kotlin support different data structures: lists, sets, maps, queues. Speaking of maps, the most popular ones are HashMap, LinkedHashMap, and TreeMap.

In this topic, we will focus on working with data structures available in Android SDK besides the standard Java ones mentioned above: the ArrayMap, ArraySet, and SparseArray family, designed for less memory consumption than standard ones.

ArrayMap

Let's refresh your knowledge on how standard Java HashMap works: it stores an array of Nodes also known as buckets, and every node contains a key hash, a reference to the key, and to the value. Nodes are positioned inside a bucket array according to their hashes. Hash collisions are solved by linking nodes to each other, which forms a list inside one bucket. Search operation (Map.get, Map.containsKey) determines a bucket by key hash and checks for key equality. In case of collision, a list of nodes is traversed until a node with an equal key is reached. This is called a hash table with closed addressing because key-value pairs are "closed" (locked) to a certain position.

ArrayMap works differently: there are no buckets and linked lists. Instead, it has an array of sorted key hashes and an array of keys and values. Search operation uses binary search to find the correct hash, and, if successful, checks the corresponding key. In case of collisions, a key-value array is traversed linearly until the key is found. Here is a hash table with open addressing and linear probing because key-value pairs are not locked to a certain position but located linearly, one after another:

Avoiding buckets with empty spaces and references to nodes, ArrayMap gives us a more compact memory layout sacrificing lookup and insertion speed.

ArrayMap implements the same (Mutable)Map interface as HashMap and can be considered an easy drop-in replacement.

val cats = ArrayMap<String, Cat>()
cats.put("Barsik", Cat())
cats.put("Murlok", Cat())
cats.put("Vasya", Cat())
cats.forEach { (name, value) ->
    println("$name: $value")
}

As a bonus, ArrayMap has the keyAt() and valueAt() methods that allow us to traverse it without .entrySet().iterator() (which is used by .forEach {}).

for (i in 0 until cats.size) {
    println("${cats.keyAt(i)}: ${cats.valueAt(i)}")
}

val iterator = map.iterator()
val first = iterator.next()
println(first) // key1=value1
val second = iterator.next()
println(first) // key2=value2
println(second) // key2=value2

ArraySet

Standard Java's HashSet wraps HashMap and utilizes its keys, leaving values unused. So, HashSet just reuses the existing code without reinventing anything but wastes some memory. ArraySet, on the other hand, is a modified version of ArrayMap and has no values at all — only keys, which saves even more memory.

val words = ArraySet(listOf("The", "grass", "is", "green."))
words.forEach(::println)

// green.
// is
// The
// grass

The same bonus applies: there's the ArraySet.valueAt() function.

for (i in 0 until words.size) {
    println(words.valueAt(i))
}

SparseArrays

SparseArray<T> acts as an optimized and simplified ArrayMap<Int, T>. Alternatively, it can be described as an array with omissions.

Why do we need special data structures instead of using just Map<Int, T> or Map<Long, T>? Because, using a general-purpose container for primitive values in Java runtime involves boxing these integers, wrapping them in objects, wasting memory, and involving more pointer dereferences.

SparseArray uses two arrays, with the first storing ordered integer keys, and the second one storing the values. Just like ArrayMap uses binary search for key hash lookup, SparseArray uses it to look up the key itself.

Apart from SparseArray<T>, there are several more flavors: SparseLongArray, SparseIntArray and SparseBooleanArray, whose values are Long, Int, and Boolean accordingly, plus LongSparseArray<T> with long keys.

In the example below, we have created 4 types of sparse arrays and filled them with data.

val catById = SparseArray<String>()
catById.put(9, "Charlie")
catById.put(34, "Barsik")
catById.put(38, "Molly")

val salaryByEmpId = SparseLongArray()
salaryByEmpId.put(1, 100L)
salaryByEmpId.put(5, 99L)
salaryByEmpId.put(16, 100L)
salaryByEmpId.put(42, 9223372036854775807L)
salaryByEmpId.put(56, 130L)

val interestingEpisodes = SparseBooleanArray()
interestingEpisodes.put(1, true)
interestingEpisodes.put(2, true)
// haven't watched the third episode
interestingEpisodes.put(4, false)

val catOwners = SparseIntArray()
catOwners.put(9, 1)
catOwners.put(34, 1)
catOwners.put(38, 42)

In addition to the Map-like get(key) method, there are get(key, defaultValue), contains(key), and the keyAt() + valueAt() method pair. Here's an example:

fun salaryOf(empId: Int): Long {
    val salary = salaryByEmpId.get(empId, -1L)
    if (salary < 0) throw NoSuchElementException("emp#$empId")
    return salary
}

fun seenEpisode(id: Int) =
    interestingEpisodes.contains(id)

fun printCatOwners() {
    for (i in 0 until catById.size) {
        val catId = catById.keyAt(i)
        val catName = catById.valueAt(i)
        val ownerId = catOwners.get(catId, -1)
        print("Cat $catName ")
        println(if (ownerId < 0) "has no owner" else "is owned by #$ownerId")
    }
}

Conclusion

Use ArrayMap and ArraySet instead of HashMap and HashSet to save some memory if you are ready to sacrifice the insertion speed on huge collections. Choose SparseArrays of all the possible option if you need integer keys.

Remember the golden rule: by sacrificing memory, we increase performance and vice versa.