article banner (priority)

Effective Kotlin Item 52: Consider associating elements to a map

This is a chapter from the book Effective Kotlin. You can find it on LeanPub or Amazon.

It is not uncommon to have a bigg set of elements in which we need to find elements by a key many times. This might be:

  • A class that stores configurations\ that are loaded from one or more files.
  • A network repository that stores downloaded data.
  • An in-memory repository (such repositories are often used for tests).

This data might represent a list of users, ids, configurations, etc. It is generally fetched as a list, and it is tempting to represent it in memory in the same way:

class ConfigurationsRepository( private val configurations: List<Configuration> ) { fun getByName(name: String) = configurations .firstOrNull { it.name == name } } class NetworkUserRepo( private val userService: UserService ) : UserRepo { private var users: List<User>? = null suspend fun loadUsers() { users = userService.getUsers() } override fun getUser(id: UserId): User? = users ?.firstOrNull { it.id == id } } class InMemoryUserRepo : UserRepo { private val users: MutableList<User> = mutableListOf() override fun getUser(id: UserId): User? = users .firstOrNull { it.id == id } fun addUser(user: User) { user.add(user) } }

Using Maps

However, this is rarely the best way to store these elements. Notice how the data we load is used: we most often access an element by an identifier or name (which is typically connected to how we design our data so as to have unique keys in databases). Finding an element in a list has linear complexity (O(n), where n is the size of the list, or more concretely, it takes on average n/2 comparisons to find an element in a list). This is especially problematic for big lists because finding each element requires comparing it with many other elements. A better solution is to use a Map instead of a List. Kotlin by default uses a hashmap (LinkedHashMap), and, as is described in Item 43: Respect the contract of hashCode, performance when finding an element using a hashmap is much better. On JVM, finding an element takes only one comparison because the size of the used hashmap is adjusted to the size of the map itself (given that the hashCode function is implemented properly).

For example, this is the InMemoryRepo from before, but its implementation is using a map instead of a list:

class InMemoryUserRepo : UserRepo { private val users: MutableMap<UserId, User> = mutableMapOf() override fun getUser(id: UserId): User? = users[id] fun addUser(user: User) { user.put(user.id, user) } }

Most other operations, like modifying or iterating over data (likely using collection processing methods like filter, map, flatMap, sorted, sum, etc.) have more or less the same performance for the standard map and list, but finding an element by key is much faster.

Associating elements with keys

The crucial question is how do we transform from a list to a map and vice versa? For this, we use the associate* functions, the most common of which is associateBy, which builds a map by associating each element with the key specified by the key selector function. This key selector function (typically a lambda expression next to associateBy) might point to the property we use to identify the element.

import kotlin.* data class User(val id: Int, val name: String) fun main() { val users = listOf(User(1, "Michal"), User(2, "Marek")) val byId: Map<Int, User> = users.associateBy { it.id } println(byId) // {1=User(id=1, name=Michal), // 2=User(id=2, name=Marek)} val byName: Map<String, User> = users .associateBy { it.name } println(byName) // {Michal=User(id=1, name=Michal), // Marek=User(id=2, name=Marek)} }

Notice that keys in a map must be unique, or duplicates must be removed. This is why we should only associate elements using a unique identifier (to group by something that is not unique, use the groupBy function).

import kotlin.* data class User(val id: Int, val name: String) fun main() { val users = listOf(User(1, "Michal"), User(2, "Michal")) val byName = users.associateBy { it.name } println(byName) // {Michal=User(id=2, name=Michal)} val group: Map<String, List<User>> = users.groupBy { it.name } println(group) // {Michal=[User(id=1, name=Michal), // User(id=2, name=Michal)]} }

To transform from a map to a list, you can use the values property of Map:

import kotlin.* data class User(val id: Int, val name: String) fun main() { val users = listOf(User(1, "Michal"), User(2, "Michal")) val byId = users.associateBy { it.id } println(byId.values) // [User(id=1, name=Michal), User(id=2, name=Michal)] }

Here are some sample usages of this technique:

class ConfigurationsRepository( configurations: List<Configuration> ) { private val configurations: Map<String, Configuration> = configurations.associateBy { it.name } fun getByName(name: String) = configurations[name] } class NetworkUserRepo( private val userService: UserService ) : UserRepo { private var users: Map<UserId, User>? = null suspend fun loadUsers() { users = userService.getUsers() .associateBy { it.id } } override fun getUser(id: UserId): User? = users?.get(id) }

This technique is important, but it is not suitable for all cases. It is most useful when we need to access elements frequently, therefore it is especially important on the backend, where collections might be accessed many times per second. It is not so important on the frontend (by that, I also mean Android or iOS), where a user will access most repositories at most a few times. We also need to remember that mapping from a list to a map also takes time, so it might also impact performance if we do it often.