Go Maps: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
(Replaced content with "=External= * https://go.dev/ref/spec#Map_types =Internal= * Go Language =TODO= {{Internal|Go_Maps_TODEPLETE|Go_Maps_TODEPLETE}}")
Tag: Replaced
Line 7: Line 7:
=TODO=
=TODO=
{{Internal|Go_Maps_TODEPLETE|Go_Maps_TODEPLETE}}
{{Internal|Go_Maps_TODEPLETE|Go_Maps_TODEPLETE}}
=Overview=
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. When a map is passed as argument to a function, the entire value is copied on the function stack, so changing the map inside the function won't affect the external argument.
=Declaration=
A map is declared with the following notation:
<syntaxhighlight lang='go'>
var <map_var_name> map[<key_type>]<value_type>
</syntaxhighlight>
<syntaxhighlight lang='go'>
var m map[string]int
</syntaxhighlight>
Note that this declaration will create a <code>nil</code> map. See [[#Empty_Map_and_nil_Map|Empty Map and <tt>nil</tt> Map]] below.
=Literals=
Composite literals can be used for map initialization:
<syntaxhighlight lang='go'>
m := map[string]int {"Alice": 1, "Bob": 2}
m2 := map[string]int {
  "Alice": 1,
  "Bob": 2, // comma on the last line required
}
</syntaxhighlight>
=Initialization=
A map can be initialized with a [[#Literals|map literal]], using [[#LVDTI|long variable declaration with type inference]] or [[#SVD|short variable declaration]].
<span id='LVDTI'></span>Long variable declaration with type inference:
<syntaxhighlight lang='go'>
var m = map[string]int {"Alice": 1, "Bob": 2}
</syntaxhighlight>
<span id='SVD'></span>Short variable declaration:
<syntaxhighlight lang='go'>
m := map[string]int {"Alice": 1, "Bob": 2}
</syntaxhighlight>
<span id='Maps_Initialization_with_make'></span>A map can also be initialized with <code>[[Go_Functions#make.28.29|make()]]</code>, which will yield an [[#Empty_Map|empty map]]:
<syntaxhighlight lang='go'>
var m map[string]int
m = make(map[string]int)
</syntaxhighlight>
==<span id='make.28.29'></span>Initialization with <tt>make()</tt>==
<code>[[Go_Functions#make.28.29|make()]]</code> is a [[Go_Functions#cap.28.29|built-in function]] that can be used to make new maps. See  [[#Maps_Initialization_with_make|Initialization]] above.
=<span id='Empty_Map'></span>Empty Map and <tt>nil</tt> Map=
A simple map variable declaration without initialization will create a <code>nil</code> map.
<syntaxhighlight lang='go'>
var m map[string]string // m is a nil map
</syntaxhighlight>
An attempt to read a key with the <code>[]</code> operator will work with the <code>nil</code> map, in that the operator invocation will succeed and will return <code>false</code>.
<syntaxhighlight lang='go'>
_, exists := m["color"]
print(exists) // prints "false"
</syntaxhighlight>
However, an attempt to '''write''' a <code>nil</code> map will panic the program:
<syntaxhighlight lang='go'>
m["color"] = "blue"
</syntaxhighlight>
will result in:
<font size=-2>
panic: assignment to entry in nil map
</font>
To get a writable map, initialize with either the empty map or use <code>make()</code>.
<syntaxhighlight lang='go'>
var m = map[string]string{}
</syntaxhighlight>
or
<syntaxhighlight lang='go'>
m := make(map[string]string)
</syntaxhighlight>
==Testing for a <tt>nil</tt> Map==
<syntaxhighlight lang='go'>
// nil map
var m map[string]struct{}
if m == nil {
  // nil map
}
</syntaxhighlight>
=Operators=
==Indexing Operator <tt>[]</tt>==
Values stored in a map can be referenced with the indexing operator <code>[[Go_Language#Indexing_Operator|[]]]</code>, using the <code>[<key>]</code> syntax. The indexing operator returns two values: the value and a boolean that says whether the key exists or not in the map.
<syntaxhighlight lang='go'>
m := map[string]int {"Alice": 1, "Bob": 2}
v, exists := m["Alice"]
fmt.Printf("%d, %t\n", v, exists) // will display 1, true
</syntaxhighlight>
If the key does not exist in map, the retuned value '''is not <code>nil</code>''', but the [[Go_Language#Zero_Value|zero value]] for the type.
The values can be changed, or new key/value pairs added with the same operator:
<syntaxhighlight lang='go'>
m["Alice"] = 7
println(m["Alice"])
m["Charlie"] = 9
println(m["Charlie"])
</syntaxhighlight>
=Functions=
==<span id='Map_Length'></span><span id='Map_Size'></span><tt>len()</tt>==
<code>len()</code> is a [[Go_Functions#len.28.29|built-in function]] that returns the number of keys in the map.
==<tt>delete()</tt>==
<code>delete()</code> is a [[Go_Functions#cap.28.29|built-in function]] that can be used to delete a key/value pair from the map:
<syntaxhighlight lang='go'>
m := map[string]int{"Alice": 1, "Bob": 2}
delete(m, "Alice")
</syntaxhighlight>
<font color=darkkhaki>What if the key does not exist?</font>
=Iterating over Map Keys and Values=
Use the <code>[[Go_Keyword_range#Iterating_over_Map_Keys_and_Values|range]]</code> [[Go_Language#Keywords|keyword]]. <code>[[Go_Keyword_range|range]]</code> allows to iterate by key and value pairs:
<syntaxhighlight lang='go'>
for k, v := range m {
  fmt.Printf("key: %s, value: %d\n", k, v)
}
</syntaxhighlight>
If we only want to iterate over keys and the values are not needed, this syntax is valid:
<syntaxhighlight lang='go'>
for k := range m {
  fmt.Printf("key: %s\n", k)
}
</syntaxhighlight>
=Key Identity=
The identity of a key in the map is given by its value '''and''' its type. We can use the same underlying value, but if the type is different, the keys will count as different. Two different [[Go_Language#Type_Alias|aliases]] of the same type count as two different types.
<syntaxhighlight lang='go'>
type A int
type B int
m := map[interface{}]string{}
m[A(1)] = "red"
m[B(1)] = "blue"
fmt.Printf("%v", m)
</syntaxhighlight>
will display:
<font size=-2>
map[1:red 1:blue]
</font>
This behavior is used to implement a [[Go_Package_context#Restoring_Key/Value_Type_Safety_for_Request-Scoped_Data|technique that prevents key collisions]] when <code>[[Go_Package_context#Requests_and_Request-Scoped_Data|context.Context]]</code> is used to store request-scoped key/value pairs.
=TO DEPLETE=
<font color=darkkhaki>
=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 [[Go_Concepts_-_Operators#.3D.3D|==]] 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 [[Go_Concepts_-_The_Type_System#Reference_Types|reference type]]. The map instances must be initialized before attempting to use into them, either by using the <tt>[[#make.28.29|make()]]</tt> function or a map literal, otherwise you will get a runtime error, because a [[Go_Concepts_-_The_Type_System#Zero_Value|zero value]] for a map is <tt>nil</tt>:
<pre>
panic: assignment to entry in nil map
</pre>
Unlike arrays, which [[Go_Arrays#Arrays_are_Values|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 [[Go Slices|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==
<pre>
var map_identifier map[key_type]value_type
</pre>
Example of a map of string to ints:
<pre>
var m map[string]int
</pre>
A map declaration and initialization with a map literal:
<pre>
var m map[string]string = map[string]string {
  "A": "B",
  "C": "D",
}
</pre>
A map declaration and initialization with <tt>make()</tt>:
<pre>
var m map[string]string = make(map[string]string)
</pre>
==Short Declaration==
===Short Declaration with Literals===
<pre>
m := map[string]string {
  "A": "B",
  "C": "D",
}
</pre>
Using a literal is the idiomatic way to create a map.
===Short Declaration with <tt>make()</tt>===
<pre>
m := make(map[string]string)
</pre>
More about <tt>make()</tt> is available <tt>[[Go_Maps#make.28.29|here]]</tt>.
=<tt>nil</tt> Maps and Empty Maps=
Declaring a map without initializing it creates a <tt>nil</tt> map - the map variable is initialized with <tt>nil</tt>. This is common behavior for [[Go_Concepts_-_The_Type_System#Reference_Types|reference types]]:
<pre>
var m map[string]string
</pre>
For a <tt>nil</tt> map, <tt>fmt.Printf("%p", s)</tt> prints <tt>0x0</tt>. The underlying data structures are initialized with zero values.
A <tt>nil</tt> map is different from an ''empty'' map:
<pre>
// empty map
m := map[string]string {}
</pre>
<pre>
// empty map
m := make(map[string]string)
</pre>
For an empty map, <tt>fmt.Printf("%p", s)</tt> prints a pointer: <tt>0x8201d2210</tt>.
Regardless of whether a <tt>nil</tt> or empty map is used, the built-in functions <tt>append()</tt>, <tt>len()</tt> and <tt>cap()</tt> work the same.
=Map Operators and Functions=
==Indexing Operator==
Assigning a key/value pair to the map is performed using the indexing <tt>[[Go Concepts - Operators#.5B.5D|[]]]</tt> and the assignment operators <tt>[[Go_Concepts_-_Operators#.3D|=]]</tt>:
<pre>
m["something"] = "something else"
</pre>
Indexing operator <tt>[[Go Concepts - Operators#.5B.5D|[]]]</tt> 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 [[Go Concepts - The Type System#Zero_Value|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.
<pre>
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"]
</pre>
Idiom:
<pre>
if value, exists := m["key"]; exists {
  // it exists ...
}
</pre>
==<span id='Map_Length'></span>Map Size==
<tt>[[Go Built-In Functions Length and Capacity#len.28.29|len()]]</tt> returns the number of keys.
Note that the built-in <tt>cap()</tt> function does not work on maps. Unlike [[Go Slices|slices]], the maps do not have the concept of capacity,
==<tt>delete()</tt>==
Removes the element corresponding to the given key from the map:
<pre>
delete(m, "something")
</pre>
It is a no-op if the key does not exist.
==<tt>make()</tt>==
The <code>[[Go_Functions#make.28.29|make()]]</code> function creates the map:
<pre>
m := make(map[key_type]value_type)
</pre>
Note that <tt>make()</tt> returns the map instance, not a pointer.
==Iterating over Maps==
<blockquote style="background-color: #f9f9f9; border: solid thin lightgrey;">
:[[Go_Keyword_range#Iterating_over_Key.2FValues_in_a_Map|<tt>range</tt> Keyword]]
</blockquote>

Revision as of 23:22, 26 August 2024

External

Internal

TODO

Go_Maps_TODEPLETE
Retrieved from "https://kb.novaordis.com/index.php?title=Go_Maps&oldid=112453"