1. Introduction
As a developer, it’s always a good idea to have a solid understanding of various data structures and how they can help us to solve various problems. A frequency map is a popular data structure that has been found to programmatically address many problems. In brief, it maintains the frequency or count of each value in a dataset.
For instance, for a list [2, 2, 1, 3, 2, 1, 5], the frequency map would be {1:2, 2:3, 3:1, 5:1}, where each key is a distinct value from the original list and each value is the count.
In this tutorial, we’ll explore how to create a frequency map in Kotlin.
2. Using a MutableMap
A simple way to create a frequency map is by using a plain old MutableMap. We can loop through the list of values and increment the count of each value in the map:
fun frequencyMap(list: List<Int>): MutableMap<Int, Int> {
val map = mutableMapOf<Int, Int>()
for (value in list) {
val count = map.getOrDefault(value, 0)
map[value] = count + 1
}
return map
}
Now, let’s test this method for correctness:
@Test
fun `test frequency map using mutable map method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
assertEquals(expectedMap, frequencyMap(list))
}
3. Using the groupingBy() and eachCount() Methods
Kotlin’s groupingBy() and eachCount() methods can also be used to build a frequency map. The groupingBy() method returns a Grouping object, which is a Map of keys to a list of occurrences of those keys (Map<V, List<V>>). While the groupingBy() method groups elements that are equal to one another using a keySelector, the eachCount() function helps us get the Map we desire by mapping each key (list element) to its count (Map<V, Int>):
@Test
fun `test frequency map using groupingBy() method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
val actualMap = list.groupingBy { it }.eachCount()
assertEquals(expectedMap, actualMap)
}
4. Using the Java Collections.frequency() Method
We can also use Collections.frequency() to create a frequency map from our list of elements. It takes in two arguments: the list and the value whose frequency we want to get. We’ll use the distinct() method on the list during iteration so that we only visit each distinct element once. With this method, we still need to build the frequency map one element at a time:
@Test
fun `test frequency map using frequency() method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
val actualMap = mutableMapOf<Int, Int>()
for(value in list.distinct()){
actualMap[value] = Collections.frequency(list, value)
}
assertEquals(expectedMap, actualMap)
}
4.1. Using HashSet
Alternatively, just like using the distinct() method in the previous method, a HashSet is another way to ensure uniqueness with the values while we’re iterating:
fun FrequencyMapUsingHashSetMethod(list: List<Int>): Map<Int, Int> {
val set = HashSet(list)
val map = mutableMapOf<Int, Int>()
for (elem in set) {
map[elem] = Collections.frequency(list, elem)
}
return map
}
We’ll test this method as well to ensure it runs correctly:
@Test
fun `test frequency map using hashset method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
val actualMap = FrequencyMapUsingHashSetMethod(list)
assertEquals(expectedMap, actualMap)
}
5. Using the merge() Method
The merge() method is another great way of creating a frequency map. We can only call this method on a MutableMap, and it operates on the value associated with a key. It accepts three parameters: the key, a default value, and a remapping function to recompute a value if present. As we iterate our list, we add each element to our map if doesn’t exist already, or simply add one to its count if it does exist in the Map:
fun FrequencyMapUsingMergeMethod(list: List<Int>): Map<Int, Int> {
val map = mutableMapOf<Int, Int>()
for (element in list) {
map.merge(element, 1) { oldValue, _ -> oldValue + 1 }
}
return map
}
Now, to ensure correctness, let’s also test this method:
@Test
fun `test frequency map using merge() method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
val actualMap = FrequencyMapUsingMergeMethod(list)
assertEquals(expectedMap, actualMap)
}
6. Using a TreeMap
When it comes to building a frequency map, a TreeMap can come in handy. A TreeMap is a sorted map that stores key-value pairs in natural order based on the keys. It still relies on the standard MutableMap interface, which allows us to generate a frequency map that is pre-sorted:
fun frequencyMapUsingTreeMapMethod(list: List<Int>): MutableMap<Int, Int>{
val map = TreeMap<Int, Int>()
list.forEach { element ->
map[element] = map.getOrDefault(element, 0) + 1
}
return map
}
Now, let’s test this method as well:
@Test
fun `test frequency map using treemap method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
val actualMap = frequencyMapUsingTreeMapMethod(list)
val sortedList = list.sorted().distinct()
assertEquals(expectedMap, actualMap)
assertEquals(sortedList, actualMap.keys.toList())
}
This also shows that the keys of our TreeMap are kept in their natural order.
7. Using a Binary Search Method
Interestingly, a binary search algorithm is another way to approach this problem. First, this algorithm sorts the list and then subsequently determines the index of the first and last occurrence of each element using indexOfFirst() and indexOfLast() methods. To determine the frequency of each list element, we subtract the first index from the last index and add 1:
fun frequencyMapUsingBinarySearchMethod(list: List<Int>): MutableMap<Int, Int>{
val sortedList = list.sorted()
val map = mutableMapOf<Int, Int>()
sortedList.distinct().forEach { element ->
val firstIndex = sortedList.indexOfFirst { it == element }
val lastIndex = sortedList.indexOfLast { it == element }
val freq = lastIndex - firstIndex + 1
map[element] = freq
}
return map
}
Let’s make sure our method works correctly:
@Test
fun `test frequency map binary search method`() {
val list = listOf(1, 2, 1, 3, 2, 4, 4, 7, 9, 7, 3, 2, 1)
val expectedMap = mapOf(1 to 3, 2 to 3, 3 to 2, 4 to 2, 7 to 2, 9 to 1)
val actualMap = frequencyMapUsingBinarySearchMethod(list)
assertEquals(expectedMap, actualMap)
}
8. Conclusion
To sum up, we’ve explored various techniques we can use to create or build a frequency map in Kotlin. Throughout this article, we’ve optimized the creation of our frequency map with the use of intermediary Sets. We’ve also looked at how specific data structures can organize the result differently, such as a TreeMap. Finally, we’ve concluded with unit testing of each method for correctness.
As always, the code samples and relevant test cases pertaining to this article can be found over on GitHub.
