Kotlin Training Program

DOWNLOAD APP

FEEDBACK

Map

Map is one of the most important Collection in Kotlin. Before Map, let us understand what a Pair - the building block of Map, is.

Pair

Pair<A, B> data structure stores a pair of related values, one of type A & another of type B.

Pair is used to store two related (associated) values. Examples of related values that can be stored using Pair :

Creating a Pair

You can create a Pair using either the Pair constructor or the to keyword :

 Pair(/* one */, /* other */)
// OR
/* one */ to /* other */

Example :

 fun main() {
		val pair = Pair("Jan", 31) // Pair<String, Int>
		// OR
		val pair1 = "Jan" to 31
		println(pair) // Prints (Jan, 31)
}

Map

Map<K, V> data structure is a list of Pair<K, V> where K & V can be any data type.

In the context of Maps,

Recall that to get data from a List, we need to know its index. There index was the key to get a value from the list. Map<K, V> can be understood as a List<V> but instead of using index to retrieve values, we use keys of type K.

Example (DOBsMap)

Suppose we need a data structure to store DOBs of some persons along with their name. When a user enters name of a person, we need to print the respective DOB. For this usecase, Map<String, String> is best suited. Here key will be person’s name & value will be person’s DOB. Program :

 fun main() {
    // Create the map
    val dobsMap = mapOf(
        "A" to "1/1/2001",
        "B" to "1/2/2002",
        "C" to "1/1/2003"
    )

    // Input name
    print("Enter name of person : ")
    val name = readln()

    // Retrieve DOB
    val dob = dobsMap[name]

    // Handle found / not found case
    if (dob != null) {
        println("DOB of $name = $dob")
    } else {
        println("DOB of $name not found!")
    }
}

/* Output 1 :

Enter name of person : B
DOB of B = 1/2/2002
 */

/* Output 2 :

Enter name of person : D
DOB of D not found!
 */

Features

Constant time search

Need for Maps

For the DOBsMap example we need not use Map, we can simply create a List of Person(name, dob). And to look for DOB given a name, we can use the find() function :

 private class Person(
    val name: String,
    val dob: String
)

fun main() {
    // Create the list
    val persons = listOf(
        Person("A", "1/1/2001"),
        Person("B", "1/2/2002"),
        Person("C", "1/1/2003")
    )

    // Input name
    print("Enter name of person : ")
    val name = readln()

    // Find the person with given name
    val person = persons.find { it.name == name }

    // Handle found / not found case
    if (person != null) {
        println("DOB of $name = ${person.dob}")
    } else {
        println("DOB of $name not found!")
    }
}

Then, why do we need a Map? We need it for Fast & Efficient Lookups. Let us understand how Map helps us achieve that.

Problem
  • In the above approach (using List), we are using find() function.
  • Time complexity of find() is O(N) i.e. in the worst case we may need to iterate over the entire list to find the element we are looking for.
  • Now imagine : if we use the same approach for thousands or millions of Persons, then to find a person with given name we’ll have to loop over the entire list. Which means thousands or millions of equality checks! This is where the List approach fails - its Lookup time is high (O(N)).
Solution
  • We use Maps because Maps use Hashing for Fast & Efficient Lookups. Lookup time in Maps is almost O(1) - Constant time, whereas that of Lists is O(N)!
  • Let us now understand what Hashing is and how it leads to constant time search.

Hashing

Hashing refers to converting data of any type to Int, using mathematical operations.

Internally Maps store the data in a List. When saving data, key is hashed into Int to find the index for saving the value. So maps do not save the values in the list sequentially, rather it hashes the key & saves the values in non-sequential manner.

Here comes the best part. For lookups, map need not iterate over the list. Instead, it again hashes the key to find out the index. Since it knows the index, no need of iteration & we get the value corresponding to a key in constant time 😎!

💡 Can different keys have the same hash? Very much possible since hashing maps potentially infinite number of keys to finite number of positions in the list. Different keys may end up on the same index. This is known as a Collision. You can learn more about Collisions and its resolution techniques.

Operations

Creating & Printing a map

We can create three types of Maps (there are more but these are the most basic ones) :

  • Map : immutable, maintains order of pairs
  • MutableMap : mutable, maintains order of pairs
  • HashMap : mutable, Doesn’t maintain order of pairs
 // Map
emptyMap<K, V>()      // Empty
mapOf(/* entries */)  // Non-empty

// MutableMap
map.toMutableMap()            // From an immutable map
mutableMapOf<K, V>()          // Empty
mutableMapOf(/* entries */)   // Non-empty

// HashMap
hashMapOf<K, V>()          // Empty
hashMapOf(/* entries */)   // Non-empty

Example :

 fun main() {
		val grades = mapOf(
		    "A+" to 10,
		    "A" to 9,
		    "B" to 8,
		    "C" to 7,
		    "D" to 6
		)
		println(grades)
}

// Output : {A+=10, A=9, B=8, C=7, D=6}

Note that Map’s toString() function is already implemented which nicely formats a map enclosed in {}.

Lookup (Access an entry)

To lookup / access an entry, we can either use the indexing operator or the get() function:

 map[/* key */]
// OR
map.get(/* key */)

Example :

 fun main() {
		val grades = mapOf(
		    "A+" to 10,
		    "A" to 9,
		    "B" to 8,
		    "C" to 7,
		    "D" to 6
		)
		println(grades["A+"]) // Prints 10
		println(grades.get("A")) // Prints 9
}

Iteration

Following are various ways in which we can iterate over a Map :

 /* Iterate over entries */
for (entry in map) { /* code */ }
// OR
for ((key, value) in map) { /* code */ }
// OR
map.forEach { (key, value) -> /* code */ }

/* Iterate over keys only */
for (key in map.keys) { /* code */ }
// OR
map.keys.forEach { key -> /* code */ }

/* Iterate over values only */
for (value in map.values) { /* code */ }
// OR
map.values.forEach { value -> /* code */ }

Example :

 fun main() {
		val grades = mapOf(
		    "A+" to 10,
		    "A" to 9,
		    "B" to 8,
		    "C" to 7,
		    "D" to 6
		)
		for ((key, value) in grades) {
				println("grades[$key] = $value")
		}
}

/* Output :

grades[A+] = 10
grades[A] = 9
grades[B] = 8
grades[C] = 7
grades[D] = 6
 */

Put (Adding a new entry)

To add a new entry in a MutableMap, we can either use the indexing operator or the put() function :

 map[/* key */] = /* value */
// OR
map.put(/* key */, /* value */)

Example :

 fun main() {
		val grades = mapOf(
		    "A+" to 10,
		    "A" to 9,
		    "B" to 8,
		    "C" to 7,
		    "D" to 6
		)
		grades["E"] = 5
		grades.put("E", 5)
}

Check whether an entry exists

To check whether a key or value exists in Map, we use the containsKey() & containsValue() function :

 map.containsKey(/* key */)
map.containsValue(/* value */)

Example :

 fun main() {
		val grades = mapOf(
		    "A+" to 10,
		    "A" to 9,
		    "B" to 8,
		    "C" to 7,
		    "D" to 6
		)

		println(grades.containsKey("A+")) // Prints true
		println(grades.containsKey("Z")) // Prints false

		println(grades.containsValue(10)) // Prints true
		println(grades.containsValue(1)) // Prints false
}

Remove an entry

To remove an entry from a MutableMap, we use the remove() function :

 map.remove(/* key */)

Example :

 fun main() {
		val grades = mapOf(
		    "A+" to 10,
		    "A" to 9,
		    "B" to 8,
		    "C" to 7,
		    "D" to 6
		)

		grades.remove("E")
}