Go Maps: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
No edit summary
Line 6: Line 6:


=Overview=
=Overview=
A map is the Go language implementation of a hash table.
A map is the Go language implementation of a hash table. A map variable is a value, not a [[Go_Language#.28No.29_Reference_Variables|reference variable]], which means that no two different map variables may point to the same map instance.
 
=Declaration=
=Declaration=
A map is declared with the following notation:
A map is declared with the following notation:

Revision as of 00:45, 29 September 2023

External

Internal

Overview

A map is the Go language implementation of a hash table. A map variable is a value, not a reference variable, which means that no two different map variables may point to the same map instance.

Declaration

A map is declared with the following notation:

var <map_var_name> map[<key_type>]<value_type>
var m map[string]int

Note that this declaration will create a nil slice. See Empty Map and nil Map below.

Literals

m := map[string]int {"Alice": 1, "Bob": 2}

m2 := map[string]int {
  "Alice": 1,
  "Bob": 2, // comma on the last line required
}

Initialization

A map can be initialized with a map literal, using long variable declaration with type inference or short variable declaration.

Long variable declaration with type inference:

var m = map[string]int {"Alice": 1, "Bob": 2}

Short variable declaration:

m := map[string]int {"Alice": 1, "Bob": 2}

A map can also be initialized with make(), which will yield an empty map:

var m map[string]int

m = make(map[string]int)

Empty Map and nil Map

Operators

Indexing Operator []

Values stored in a map can be referenced with the indexing operator [], using the [<key>] syntax. The indexing operator returns two values: the value and a boolean that says whether the key exists or not in the map.

m := map[string]int {"Alice": 1, "Bob": 2}
v, exists := m["Alice"]
fmt.Printf("%d, %t\n", v, exists) // will display 1, true

The values can be changed, or new key/value pairs added with the same operator:

m["Alice"] = 7
println(m["Alice"])

m["Charlie"] = 9
println(m["Charlie"])

Functions

len()

len() is a built-in function that returns the number of keys in the map.

make()

make() is a built-in function that can be used to make new maps. See Initialization above.

delete()

delete() is a built-in function that can be used to delete a key/value pair from the map:

m := map[string]int{"Alice": 1, "Bob": 2}
delete(m, "Alice")

What if the key does not exist?

Iterating over Map Keys and Values

Use the range keyword. range allows to iterate by key and value pairs:

for k, v := range m {
  fmt.Printf("key: %s, value: %d\n", k, v)
}

TO DEPLETE

Overview

A map is an unordered collection of key-value pairs. The map implementation uses the key as an index, quickly retrieving the associated value.

The map key can be a value from any built-in or struct type as long as the value can be used in an expression with an == operator. Slices, functions and struct types that contain slices can't be used as map keys, an attempt will generate a compiler error.

Lexically, a map type is a reference type. The map instances must be initialized before attempting to use into them, either by using the make() function or a map literal, otherwise you will get a runtime error, because a zero value for a map is nil:

panic: assignment to entry in nil map

Unlike arrays, which are values and problematic to pass as function arguments, maps can be easily be passed as values - their memory footprint is very small. If a map is passed to a function and changed in the function, the changes will be reflected by all references to the map. From this point of view, maps are designed to be cheap, similar to slices.

Implementation Details

In order to store a key/value pair in the map, the map hash function is applied to the key, which produces the index of a bucket. The purpose of the hash function is to generate the index that is evenly distributed across the bucket population. Once a bucket is selected, the map stores the key/value pair in the bucket.

In order to retrieve the value corresponding to a key, the same hash function is applied to select the bucket, and then the map iterates over the keys stored in that bucket.

Declaration

Long Declaration

var map_identifier map[key_type]value_type

Example of a map of string to ints:

var m map[string]int

A map declaration and initialization with a map literal:

var m map[string]string = map[string]string {
  "A": "B",
  "C": "D",
}

A map declaration and initialization with make():

var m map[string]string = make(map[string]string)

Short Declaration

Short Declaration with Literals

m := map[string]string {
  "A": "B",
  "C": "D",
}

Using a literal is the idiomatic way to create a map.

Short Declaration with make()

m := make(map[string]string)

More about make() is available here.

nil Maps and Empty Maps

Declaring a map without initializing it creates a nil map - the map variable is initialized with nil. This is common behavior for reference types:

var m map[string]string

For a nil map, fmt.Printf("%p", s) prints 0x0. The underlying data structures are initialized with zero values.

A nil map is different from an empty map:

// empty map
m := map[string]string {}
// empty map
m := make(map[string]string)

For an empty map, fmt.Printf("%p", s) prints a pointer: 0x8201d2210.

Regardless of whether a nil or empty map is used, the built-in functions append(), len() and cap() work the same.

Map Operators and Functions

Indexing Operator

Assigning a key/value pair to the map is performed using the indexing [] and the assignment operators =:

m["something"] = "something else"

Indexing operator [] returns the copy of the value corresponding to the specified key and a boolean value that says whether the key exists or not. If the key does not exist, the zero value for the value type is returned. Note that if the map allows zero values, we cannot rely on the returned value alone to decide whether the key/value has been actually stored in the map or not, we need to use the returned "exists" flag.

value := m["key"] // only the first return value can be used, as long as we are prepared to deal with the zero value
value, exists := m["key"]

Idiom:

if value, exists := m["key"]; exists {
   // it exists ...
}

Map Size

len() returns the number of keys.

Note that the built-in cap() function does not work on maps. Unlike slices, the maps do not have the concept of capacity,

delete()

Removes the element corresponding to the given key from the map:

delete(m, "something")

It is a no-op if the key does not exist.

make()

The make() function creates the map:

m := make(map[key_type]value_type)

Note that make() returns the map instance, not a pointer.

Iterating over Maps

range Keyword