Maps, sometimes known as dictionaries, differ from lists in that you can access items in a map by a key rather than a position. Later in this book you will see that there are many ways to implement a map, and Kotlin provides multiple options. As we did in the section on lists, we will constrain our discussion to the default map that Kotlin provides when using the mutableMapOf or MutableMap functions. Internally, Kotlin refers to this default implementation as a LinkedHashMap. It should be understood for the remainder of this section that when we talk about performance of a Kotlin map, we are talking about the performance for this implementation in particular 1
As of the time of this writing, Kotlin directly provides three implementations of mutable maps. The HashMap, which is automatically included from Java, is a typical hash-based implementation. The LinkedHashMap, which is the default in Kotlin, is also leveraged from Java. A LinkedHashMap is similar to a HashMap, but additionally implements a doubly-linked list that contains all of its entries, which is used for producing a consistent iteration order. Finally, Kotlin also allows you to convert a map to a SortedMap via the toSortedMap member function. The map that is returned is a TreeMap, again provided from Java.
The thing that is most important to notice right now is that the get and put operations on this Kotlin map are \(O(1)\text{.}\) Another important map operation is the containsKey operation. Checking to see whether a key is in this map or not is also \(O(1)\text{.}\) The efficiency of common Kotlin map operations is summarized in Table 2.7.1. One important side note on map performance is that the efficiencies we provide in the table are for average performance. In some rare cases the contains, get, and set operations can degenerate into \(O(n)\) performance, but we will get into that later when we talk about the different ways that a map could be implemented.
For our last performance experiment, we will compare the performance of the contains method for Kotlin lists and the containsKey operation for Kotlin maps. In the process we will confirm that the operation for lists is \(O(n)\) and the operation for maps is \(O(1)\text{.}\) The experiment we will use to compare the two is as follows: we’ll make a list with a range of numbers in it, then we will pick numbers at random and check to see if the numbers are in the list. If our performance tables are correct, the bigger the list, the longer it should take to determine if any one number is contained in the list.
We will repeat the same experiment for a map that contains numbers as the keys. In this experiment we should see that determining whether or not a number is in the map is not only much faster, but the time it takes to check should remain constant even as the map grows larger.
Listing 2.7.2 implements this comparison. Notice that we are performing exactly the same operation, even though they have different names: list.contains(number) and map.containsKey(number). (Note: this program takes a while to run, and may time out if you run it within the interactive textbook.)
Figure 2.7.3 summarizes the results of running Listing 2.7.2. You can see that the map is consistently faster. For the smallest size of 10,000 elements, a map is roughly 39 times faster than a list. For the largest size of 990,000 elements the map is 4,863 times faster! You can also see that the time it takes for the contains method on the list grows linearly with the size of the list. This verifies the assertion that the contains method on a list is \(O(n)\text{.}\) It can also be seen that the time for the containsKey method on a map is constant even as the map size grows.
