Section 6.2 The Map and Set Abstract Data Types
Subsection 6.2.1 The Map Abstract Data Type
One of the most useful Kotlin collections is the map (called a dictionary in other languages such as Python). Recall that a map is an associative data type where you can store key-data pairs. The key is used to look up the associated data value. We often refer to this idea as a map.
The map abstract data type is defined as follows. The structure is an unordered collection of associations between a key and a data value. The keys in a map are all unique so that there is a one-to-one relationship between a key and a value. The operations are given below.
-
put(key, value)adds a new key–value pair to the map. If the key is already in the map, it replaces the old value with the new value. -
remove(key)deletes the key–value pair from the map. It returns the value associated with the removed key, or null if the key is not in the map. -
size()returns the number of key–value pairs stored in the map.
We have already used Kotlin’s built-in
Map and MutableMap for a variety of purposes. In this chapter, we will look at multiple approaches for implementing a map ourselves, and study the advantages and disadvantages of each approach.
As we have done for previous ADTs, here is a Kotlin interface that represents a map. We can then implement this interface when we write code for our own map.
interface MapADT<K, V> {
// Adds the key/value pair to the map.
// If the key is already in the map, it replaces the old value with the new one.
fun put(key: K, value: V)
// Returns the value matching the provided key, or null otherwise.
fun get(key: K): V?
// Removes the key from the map.
// Returns the matching value stored in the map, or null otherwise.
fun remove(key: K): V?
// Returns true if the key is in the map, false otherwise.
fun containsKey(key: K): Boolean
// Returns the number of key/value pairs stored in the map
fun size(): Int
}
Subsection 6.2.2 The Set Abstract Data Type
Another very useful Kotlin collection is the set. A set is used when keeping track of a collection of items where duplicates are prohibited. For example, we might use a set to keep track of which students are enrolled in a class, or to track a collection of friends or followers in a social network. Here are the typical operations:
-
add(element)adds a new element to the set. If the element is already in the set, no change to the set is made. -
remove(element)deletes the element from the set. It returns true if the value was in the set; false otherwise. -
size()returns the number of elements stored in the map.
Here’s the reason we’re talking about sets at the same time as maps: they are nearly identical. If we have a map, we could in a clumsy fashion use it as a set. We would simply use the keys as the items in the set, and just ignore the values in the map entirely. Perhaps we would just store a null value for every key. A different way of looking at it is that the implementation of a set is identical to that of a map, with the sole exception that in a set, we don’t bother with values. We just store the keys. A third way to think about is to notice that in a map, we don’t allow duplicate key values, so a map is, conceptually, a set of keys (with associated values for each).
Here is a Kotlin interface that represents a set. We can then implement this interface when we write code for our own set.
interface SetADT<E> {
// Adds the element to the set.
fun add(element: E)
// Returns true if the element is in the set, false otherwise.
fun contains(element: E): Boolean
// Removes the element from the set.
// Returns true if the element was in the set; false otherwise.
fun remove(element: E): Boolean
// Returns the number of elements stored in the set
fun size(): Int
}
You have attempted of activities on this page.
