Map types in GO

• A map is an unordered collection of key/value pairs, where each key is unique. If you are coming from python this is similar to dictionary.
• Go provides a built in map type that implements hash table and stores key/value pairs into buckets
• Hash tables provide fast lookup, addition and deletion.
• The idea behind hash map is to have O(1) lookup time on average. Generally it is O(n) provided if hash function gives n collisions which is very rare in real time

Lets see the basic operations of map in golang.

Declaration

Below declaration implies that m is a Map with key as string and value as int

var m map[string]int

Initialization

• The make() function is a built-in function in go which is used to initialize maps along with slices and channels.

• Note that make() function creates generic values for map, slices and channels and it never returns pointer.

Map m1 initializes map with string as key and int as value.

 m1 := make(map[string]int)

• Map m2 is initialized with string as key, int as value and with a capacity of 10 elements which means that it is only a hint that an initial capacity can be 10 (space for initial 10 elements before reallocation happens) but it won't restrict if elements are more than mentioned initial capacity.

• capacity is hint for total number of key/value pairs.
  

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

• The default number of buckets is 1.

• Each bucket is an array with array of 8 elements. Once number of entries in each bucket reaches an average load of buckets, the map get bigger by doubling its number of buckets.

• Map m3 is initialized with string as key, int as value storing "RED", "BLUE" as keys and 1, 2 as values respectively
  

 var m3 := map[string]int {
    "RED": 1,
    "BLUE": 2,
  }

Zero value of map

• If map is declared and initialization is not done then map acts like empty map while reading and map acts like nil while writing, keep this in mind when you are declaring a map next time.

func main() {
    var m map[string]int //Declaration

    //READING VALUE FROM MAP
    v := m["key"]

    fmt.Printf("Read value from map %+v \n", v)

    //WRITING VALUE TO MAP
    m["key2"] = 973

    fmt.Printf("values in map %+v \n", m)
}

from above example reading happens without any issue since map is behaving like empty map while reading, but at line where we are trying to assign value to map m["key2"] = 973 compiler panics with message "assignment to entry in nil map".

Try above example in playground

MAP OPERATIONS

Insert/Update

m := make(map[string]int)
m["RED"] = 123

add to map with key "RED" and value as 123.

Delete

delete(m, "BLUE")

delete elements with key values as BLUE

Iterate over all elements in map

Keyword range can be used to iterate over all elements
in map as you can see in below sample code when range is used it returns key, value pair.

m := map[string]int {
    "RED": 1,
    "BLUE": 2,
}

for key, val := range m {
    fmt.Printf("key: %s, value: %d", key, val)
}

Get Values from Map

val := m["RED"]
val, ok := m["BLUE"]

while getting values from map it returns two variables,value and bool. Bool indicates whether the key exists in map.

What is the use of returned bool value?

• Note that value returned from map will be zero value if key is not present, for example if int is the value for string key but given key is not available in map then zero is returned(since zero value of int is zero).
• This helps in understanding whether value is present as zero for the given key or since key is not available in map zero is returned.

What data types can be used as key in Map?

Any data type which has equality operation defined can be used as key in map that is == and != should be defined on those data types going by that logic we can't have below data types as keys in map
 * slice
 * functions
 * map

Concurrency

• Maps are not safe for concurrent use: it’s not defined what happens when you read and write to them simultaneously.
• If you need to read from and write to a map concurrently, the accesses must be controlled by some kind of synchronization mechanism.
• One common way to protect maps is with sync.RWMutex.

Below statement declares struct stats with RWMutex and a map with string as key and int ass value

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

Reading from stats using Read Lock(concurrent safe read)

counter.RLock()
n := counter.m["total_requests"]
counter.RUnlock()
fmt.Println("total_requests:", n)

Writing to stats using Write Lock(concurrent safe write)

counter.Lock()
counter.m["some_key"]++
counter.Unlock()

What does a Map variable hold?

• Maps are not reference variables.
• Go also doesn't have pass by reference since it doesn't have reference variables.
• To understand more on what is reference variable read below post from Dave Cheyney.

There is no pass by reference in go

• Map m is actually a pointer to 'runtime.hmap'.
• To confirm the same run below code in go playground and see that both map variable m and uintptr has same size

compare map variable with uintptr in go playground

Access hmap and maptype struct which a map is pointed to, run below code in playground to see hmap struct. Try changing key data type, capacity of map etc to see how hmap and maptypes vary.

observe hmap and maptype structs

Compile Time

Go compiler rewrites map operations with different functions calls in runtime below are function calls for respective map operations

m := make(map[int]int)  → runtime.makemap(&t, 0, &h, &b)
v := m["RED"]     → runtime.mapaccess1(m, ”RED", &v)
v, ok := m["BLUE"] → runtime.mapaccess2(m, ”BLUE”, &v, &ok)
m["CYAN"] = 143   → runtime.mapinsert(m, ”CYAN", 143)
delete(m, "BLUE")  → runtime.mapdelete(m, “BLUE”)

Conclusion

I hope this will be useful as a reference for Maps. I will try to add more details on sync.Map in a separate post. If there is something which can be improved/not clear in above post please let me know in comments.

References

Dave Cheyney's talk on How Maps are implemented in go
Discussion on Why maps are not as *map since it is pointer

EDIT 1 : updated variable stats to counter under concurrency as suggested by @dogers