Map

Generally, map data structure implementations usually come in two forms: hash table and search tree. The difference is that the former is unordered, while the latter is ordered. In Go, the implementation of map is based on hash buckets (also a hash table), so it is also unordered. This article will not explain the implementation principles in detail as it exceeds the scope of basics and will be analyzed in depth later.

TIP

To learn about the principles of map, you can visit Map Implementation

Initialization

In Go, the key type of map must be comparable. For example, string and int are comparable, while []int is not comparable and cannot be used as a map key. There are two ways to initialize a map. The first is using a literal, with the following format:

map[keyType]valueType{}

Some examples:

mp := map[int]string{
   0: "a",
   1: "a",
   2: "a",
   3: "a",
   4: "a",
}

mp := map[string]int{
   "a": 0,
   "b": 22,
   "c": 33,
}

The second method is to use the built-in function make. For map, it accepts two parameters: the type and the initial capacity. Examples are as follows:

mp := make(map[string]int, 8)

mp := make(map[string][]int, 10)

Map is a reference type. A zero value or uninitialized map can be accessed, but elements cannot be stored in it. Therefore, memory must be allocated for it.

func main() {
   var mp map[string]int
   mp["a"] = 1
   fmt.Println(mp)
}

panic: assignment to entry in nil map

TIP

When initializing a map, you should try to allocate a reasonable capacity to reduce the number of times the map needs to grow.

Access

Accessing a map is similar to accessing an array by index.

func main() {
  mp := map[string]int{
    "a": 0,
    "b": 1,
    "c": 2,
    "d": 3,
  }
  fmt.Println(mp["a"])
  fmt.Println(mp["b"])
  fmt.Println(mp["d"])
  fmt.Println(mp["f"])
}

0
1
3
0

As can be observed from the code, even if the key "f" does not exist in the map, there is still a return value. For non-existent keys, the map returns the zero value of the corresponding type. Additionally, when accessing a map, there are actually two return values: the first is the value of the corresponding type, and the second is a boolean indicating whether the key exists. For example:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   if val, exist := mp["f"]; exist {
      fmt.Println(val)
   } else {
      fmt.Println("key does not exist")
   }
}

Getting the length of a map:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(len(mp))
}

Setting Values

Setting values in a map is also similar to setting values in an array:

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   fmt.Println(mp)
}

When setting a value using an existing key, it will overwrite the original value:

func main() {
   mp := make(map[string]int, 10)
   mp["a"] = 1
   mp["b"] = 2
   if _, exist := mp["b"]; exist {
      mp["b"] = 3
   }
   fmt.Println(mp)
}

However, there is a special case: when the key is math.NaN():

func main() {
  mp := make(map[float64]string, 10)
  mp[math.NaN()] = "a"
  mp[math.NaN()] = "b"
  mp[math.NaN()] = "c"
  _, exist := mp[math.NaN()]
  fmt.Println(exist)
  fmt.Println(mp)
}

false
map[NaN:c NaN:a NaN:b]

From the results, it can be observed that the same key did not overwrite the value; instead, multiple entries can exist. It is also impossible to determine whether it exists, and normal value retrieval is not possible. This is because NaN is defined by the IEEE 754 standard, and its implementation is done by the underlying assembly instruction UCOMISD, which is an instruction for unordered comparison of double-precision floating-point numbers that takes NaN into account. As a result, no number equals NaN, and NaN does not equal itself, causing each hash value to be different. The community has had heated discussions about this, but the official stance is that there is no need to modify it. Therefore, you should avoid using NaN as a map key.

Deletion

func delete(m map[Type]Type1, key Type)

Deleting a key-value pair requires using the built-in function delete. For example:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   fmt.Println(mp)
   delete(mp, "a")
   fmt.Println(mp)
}

map[a:0 b:1 c:2 d:3]
map[b:1 c:2 d:3]

It should be noted that if the value is NaN, you cannot even delete that key-value pair.

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   fmt.Println(mp)
   delete(mp, math.NaN())
   fmt.Println(mp)
}

map[NaN:c NaN:a NaN:b]
map[NaN:c NaN:a NaN:b]

Traversal

You can traverse a map using for range. For example:

func main() {
   mp := map[string]int{
      "a": 0,
      "b": 1,
      "c": 2,
      "d": 3,
   }
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

c 2
d 3
a 0
b 1

As you can see, the result is not ordered, which confirms that map is stored unordered. It is worth mentioning that although NaN cannot be retrieved normally, it can be accessed through traversal:

func main() {
   mp := make(map[float64]string, 10)
   mp[math.NaN()] = "a"
   mp[math.NaN()] = "b"
   mp[math.NaN()] = "c"
   for key, val := range mp {
      fmt.Println(key, val)
   }
}

NaN a
NaN c
NaN b

Clearing

Before go1.21, to clear a map, you could only delete each key from the map:

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  for k, _ := range m {
    delete(m, k)
  }
  fmt.Println(m)
}

However, go1.21 introduced the clear function, so you no longer need to do the previous operation. You can clear with just one clear:

func main() {
  m := map[string]int{
    "a": 1,
    "b": 2,
  }
  clear(m)
  fmt.Println(m)
}

Output:

map[]

Set

Set is an unordered collection that does not contain duplicate elements. Go does not provide a similar data structure implementation, but the keys of a map are exactly unordered and cannot be duplicated. Therefore, you can also use map to replace set.

func main() {
  set := make(map[int]struct{}, 10)
  for i := 0; i < 10; i++ {
    set[rand.Intn(100)] = struct{}{}
  }
  fmt.Println(set)
}

map[0:{} 18:{} 25:{} 40:{} 47:{} 56:{} 59:{} 81:{} 87:{}]

TIP

An empty struct does not take up memory

Note

Map is not a concurrency-safe data structure. The Go team believes that in most cases, map usage does not involve high-concurrency scenarios, and introducing mutexes would greatly reduce performance. Map has internal read-write detection mechanisms; if there is a conflict, it will trigger a fatal error. For example, the following situation has a very high probability of triggering fatal:

func main() {

   group.Add(10)
   // map
   mp := make(map[string]int, 10)
   for i := 0; i < 10; i++ {
      go func() {
         // write operation
         for i := 0; i < 100; i++ {
            mp["helloworld"] = 1
         }
         // read operation
         for i := 0; i < 10; i++ {
            fmt.Println(mp["helloworld"])
         }
         group.Done()
      }()
   }
   group.Wait()
}

fatal error: concurrent map writes

In this case, you need to use sync.Map instead.