Sorting Go Dictionaries

Introduction

Unlike other languages, in Go, dictionaries (maps) are unordered collections. In this lab, we will learn about sorting dictionaries and how to use them more flexibly.

Key Concepts:

• Sorting dictionaries
• Swapping keys and values in a dictionary
• Slices of dictionaries
• Dictionaries with slices as values
• Reference type characteristics of dictionaries

Skills Graph

Sorting Dictionaries

Create a map.go file in the ~/project directory:

touch ~/project/map.go

Write the following code into the map.go file:

package main

import (
	"fmt"
)

func main() {
	// Declare and initialize a map with string keys and integer values
	// The map stores student names and their scores
	m := map[string]int{
		"Alice":   99, // Each key-value pair represents a student and their score
		"Bob":     38,
		"Charlie": 84,
	}

	// Iterate through the map using a for-range loop
	// 'key' represents student names, 'value' represents scores
	for key, value := range m {
		fmt.Println(key, value)
	}

	fmt.Println("\nInsert Data")

	// Demonstrate how to add a new key-value pair to the map
	// The syntax is: map[key] = value
	m["David"] = 25

	// Iterate again to show the updated map contents
	// Note that the order may be different in each execution
	for key, value := range m {
		fmt.Println(key, value)
	}
}

Run the program:

go run ~/project/map.go

The output of the program may look like this:

Charlie 84
Bob 38
Alice 99

Insert Data
David 25
Charlie 84
Bob 38
Alice 99

The output may vary since the order of the inserted data is not fixed. This is a core characteristic of Go maps - they do not guarantee any particular order of elements when you iterate through them.

You can try running the program multiple times and observe that the order of the inserted data may vary. This illustrates that you cannot rely on the order of elements in a map.

But sometimes we need to sort the dictionary after inserting data. How can we achieve that?

Since a map itself cannot be sorted, we can convert the map into a slice and then sort the slice.

Sort by Key

First, let's learn how to sort the dictionary by key.

Here are the steps:

• Convert the keys of the dictionary into a slice. A slice is an ordered, dynamic array that we can sort.
• Sort the slice using Go's built-in sort package.
• Retrieve the corresponding values using the dictionary's lookup method. Since we know the order of keys in our slice, we can look up the values in the map and they will appear in that sorted key order.

Write the following code into the map.go file:

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Initialize the dictionary
	m1 := map[int]string{
		3: "Bob",
		1: "Alice",
		2: "Charlie",
	}
	keys := make([]int, 0, len(m1)) // Initialize the slice with capacity. This is a performance optimization -  the slice will allocate memory equal to the size of the map initially, avoiding re-allocations.
	for key := range m1 {
		// Convert the key to a slice
		keys = append(keys, key)
	}
	// Sort the key slice using the sort package. The `sort.Ints()` function specifically sorts a slice of integers.
	sort.Ints(keys)
	for _, key := range keys {
		// The output is in order now
		fmt.Println(key, m1[key])
	}
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

1 Alice
2 Charlie
3 Bob

Through this approach, we have achieved sorting the dictionary based on the key. The keys are extracted into a slice, sorted, and then used to look up and print the corresponding values from the map.

Swapping Keys and Values in a Dictionary

Before we explain how to sort by value, let's learn how to swap the keys and values in a dictionary.

Swapping keys and values means interchanging the positions of keys and values in a dictionary, as shown in the figure below:

The implementation code is simple. Write the following code into the map.go file:

package main

import "fmt"

func main() {
	m := map[string]int{
		"Alice":   99,
		"Bob":     38,
		"Charlie": 84,
	}
	m2 := map[int]string{}
	for key, value := range m {
		m2[value] = key
	}
	fmt.Println(m2)
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

map[38:Bob 84:Charlie 99:Alice]

The essence of this code is to extract the keys and values from the original dictionary, and then reinsert them into the dictionary but with swapped roles. It's simple and straightforward. Note that because the map is unordered, the output order of the swapped map may vary.

Sort by Value

Combining the logic of sorting the dictionary by key and swapping keys and values in a dictionary, we can sort the dictionary by value.

Here's how it works: we swap the keys and values, and then treat the swapped keys (original values) as the basis for our sort. We then use the sorted "keys" (original values) to look up the corresponding original keys in the swapped map.

Write the following code into the map.go file:

package main

import (
	"fmt"
	"sort"
)

func main() {
	// Initialize the dictionary
	m1 := map[string]int{
		"Alice":   99,
		"Bob":     38,
		"Charlie": 84,
	}

	// Initialize the reversed dictionary
	m2 := map[int]string{}
	for key, value := range m1 {
		// Generate the reversed dictionary m2 by swapping the key-value pairs
		m2[value] = key
	}

	values := make([]int, 0) // Initialize the sorting slice
	for _, value := range m1 {
		// Convert the values of the original dictionary to a slice
		values = append(values, value)
	}
	// Sort the value slice using the sort package
	sort.Ints(values)

	for _, value := range values {
		// The output is in order now
		fmt.Println(m2[value], value)
	}
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

Bob 38
Charlie 84
Alice 99

Now we have sorted the dictionary based on its values. We converted the values to a slice, sorted the slice, and then used the sorted values to retrieve and print the corresponding original keys from the swapped map.

Sorted by sort.Slice

If the version of Go is later than 1.7, we can use the sort.Slice function to quickly sort a map by key or value. sort.Slice allows you to specify a custom comparison function.

Here is an example:

package main

import (
	"fmt"
	"sort"
)

func main() {
	m1 := map[int]int{
		21: 99,
		12: 98,
		35: 17,
		24: 36,
	}

	type kv struct {
		Key   int
		Value int
	}

	var s1 []kv

	for k, v := range m1 {
		s1 = append(s1, kv{k, v})
	}

	sort.Slice(s1, func(i, j int) bool {
		return s1[i].Key < s1[j].Key
	})

	fmt.Println("Sorted in ascending order by key:")
	for _, pair := range s1 {
		fmt.Printf("%d, %d\n", pair.Key, pair.Value)
	}
}

Run the program:

go run ~/project/map.go

The output is as follows:

Sorted in ascending order by key:
12, 98
21, 99
24, 36
35, 17

In this program, we used a struct kv to store the key-value pairs from the map. We then sorted the slice of structs using the sort.Slice() function and an anonymous comparison function. This comparison function (func(i, j int) bool) determines the sorting order based on the Key field of our struct.

We can also use sort.Slice to sort the map in descending order by key or in ascending order by value by modifying this comparison function. This provides great flexibility in how we want to sort our map data.

Little Test

Create a map2.go file and modify the code from the previous section to sort the map in descending order based on the value.

Expected Output:

Run the program:

go run ~/project/map2.go

Sorted in descending order by value:
21, 99
12, 98
24, 36
35, 17

Requirements:

• The map2.go file should be placed in the ~/project directory.
• You must use the sort.Slice function. You will need to modify the comparison function used in sort.Slice from the previous example.

Slices of Dictionaries

Just as we can use arrays or slices to store related data, we can also use slices where the elements are dictionaries. This lets us hold collections of map data, which can be useful for working with structured information.

Write the following code into the map.go file:

package main

import "fmt"

func main() {
	// Declare a slice of maps and initialize it using make
	var mapSlice = make([]map[string]string, 3) // Creates a slice with a capacity of 3, where each element can be a `map[string]string`.
	for index, value := range mapSlice {
		fmt.Printf("index:%d value:%v\n", index, value)
	}
	fmt.Println("Initialization")
	// Assign values to the first element of the slice
	mapSlice[0] = make(map[string]string, 10) // Creates a map at the first index.
	mapSlice[0]["name"] = "labex"
	mapSlice[0]["password"] = "123456"
	mapSlice[0]["address"] = "Paris"
	for index, value := range mapSlice {
		fmt.Printf("index:%d value:%v\n", index, value)
	}
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

index:0 value:map[]
index:1 value:map[]
index:2 value:map[]
Initialization
index:0 value:map[address:Paris name:labex password:123456]
index:1 value:map[]
index:2 value:map[]

The code demonstrates the initialization of a slice of maps. Initially, each element in the slice is an empty map. We then create and assign a map to the first element, populating it with data. This shows how to manage a list of maps.

Dictionaries with Slices as Values

We can also use dictionaries with slices as values to store more data in a dictionary. This lets us associate multiple values with a single key in a map, effectively creating a "one-to-many" relationship.

Write the following code into the map.go file:

package main

import "fmt"

func main() {
	var sliceMap = make(map[string][]string, 3) // Declares a map where keys are strings and values are slices of strings. The 3 is a capacity hint.
	key := "labex"
	value, ok := sliceMap[key]  // Checks if the key exists
	if !ok {
		value = make([]string, 0, 2) // If it doesn't exist, initialize a new slice with capacity.
	}
	value = append(value, "Paris", "Shanghai") // Appends values to the slice.
	sliceMap[key] = value // Sets the slice as the value for our key in the map.
	fmt.Println(sliceMap)
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

map[labex:[Paris Shanghai]]

The code first declares a map type where the values are slices. It checks if the key exists before adding new items to the associated slice, demonstrating a common pattern for handling maps of slices.

Reference Type Characteristics of Dictionaries

Arrays are value types, so assigning and passing them to functions creates a copy. Changes to the copy don't affect the original array. Maps, however, are reference types. This means that assigning and passing a map to a function does not create a full copy. Instead, the map is passed by reference.

This is important, as changes made within the function will affect the original map data.

Write the following code into the map.go file:

package main

import "fmt"

func modifyMap(x map[string]int) {
	x["Bob"] = 100 // Modifies the map that was passed as an argument.
}

func main() {
	a := map[string]int{
		"Alice":   99,
		"Bob":     38,
		"Charlie": 84,
	}
	// Because the map is passed by reference, the modification in modifyMap changes the original dictionary
	modifyMap(a)
	fmt.Println(a) // map[Alice:99 Bob:100 Charlie:84]
}

Run the program:

go run ~/project/map.go

The output of the program is as follows:

map[Alice:99 Bob:100 Charlie:84]

In the example, we demonstrated the reference transfer characteristic of a dictionary. The modifyMap function changes the original map because a is a reference to the same underlying map data. This behavior is crucial to understand when passing maps to functions.

Summary

In this lab, we have learned about advanced usage of maps in Go, including:

• Sorting maps by key or value, which involves converting the map to a slice and then sorting the slice.
• Swapping keys and values in a map, which creates a new map with reversed roles.
• Using slices of maps, which allows for creating collections of related map data.
• Using maps with slices as values, which allows associating multiple values with a single key.
• Reference type characteristics of maps, where changes in a passed map reflect in the original map.

Understanding these concepts will allow you to use Go maps more effectively in real-world applications.