article banner (priority)

Effective Kotlin Item 55: 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 big set of elements in which we need to find elements by their keys. 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, so it is tempting to represent it in memory in the same way:

class ConfigurationRepository( 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 related 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), which offers much better performance when finding an element, as is described in Item 43: Respect the contract of hashCode. 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 uses 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 to transform from a list to a map and vice versa? To transform an iterable to a map, we use the associate method, in which we produce key-value pairs for each element.

data class User(val id: Int, val name: String) val users = listOf(User(1, "Michal"), User(2, "Marek")) val nameById: Map<Int, String> = users.associate { it.id to it.name } println(byId) // {1=Michal, 2=Marek}

There are other variants of the associate method. My favorite is associateBy, which keeps an iterable element as a value, and we only have to decide what key should represent it.

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

Note that keys in a map must be unique because duplicates are 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).

val users2 = listOf(User(1, "Michal"), User(2, "Michal")) val byName = users2.associateBy { it.name } println(byName) // {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)] }

By associating elements to a map, we can improve the performance of our code. This is especially important when we need to access elements frequently. For example, we can use this technique to improve the performance of the ConfigurationRepository and NetworkUserRepo from the beginning of this item:

class ConfigurationRepository( 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) }

Thanks to the changes we’ve made, finding a configuration or a user is an immediate operation that we can do as many times as we want without worrying about performance. Of course, the cost is that we need to associate our elements to a map, but this is an operation with linear complexity, just like finding an element in a list.

This technique can also be used for more complicated processing operations. For example, imagine that you need to fetch a list of articles from one service, and details of authors from another one. Then you need to associate each article with its author. This is how a naive implementation might look:

fun produceArticlesWithAuthors( articles: List<Article>, authors: List<Author> ): List<ArticleWithAuthor> { return articles.map { article -> val author = authors .first { it.id == article.authorId } ArticleWithAuthor(article, author) } }

The complexity of this solution is O(n * m), where n is the number of articles, and m is the number of authors. This is because we need to find each article’s author, and finding an author is a linear operation. We can improve the performance of this code by associating authors to a map:

fun produceArticlesWithAuthors( articles: List<Article>, authors: List<Author> ): List<ArticleWithAuthor> { val authorsById = authors.associateBy { it.id } return articles.map { article -> val author = authorsById[article.authorId] ArticleWithAuthor(article, author) } }

The complexity of this solution is O(n + m), because we first associate the authors to a map, which needs one iteration over the authors list; then we iterate over the article list once, and finding the author of each is an extremely fast operation. This is a significant improvement if the number of articles and authors is not small.

Summary

  • Use Map instead of List when you need to find elements by key.
  • Use associate or associateBy to transform from a list to a map.
  • Associating elements to a map to find them by their keys is a powerful technique that can be used to improve the performance of your code.