CODEWITHSUNDEEP
dictionarygo
Mpac
Mpac

Reputation: 931

Modifying map while iterating over it in Go

Given the following code I would expected an infinite loop but the loop is being stopped at certain point.

m := make(map[int]string, 4)
m[0] = "Foo"
    
for k, v := range m {
    m[k+1] = v
}

I cannot figure out what happen under the hood because different execution return different output. For example these are a few outputs from different executions:

map[0:Foo 1:Foo 2:Foo 3:Foo 4:Foo 5:Foo 6:Foo 7:Foo]
map[0:Foo 1:Foo]
map[0:Foo 1:Foo 2:Foo]

How range works in order to exit from loop at certain point and what is the exit condition?

Upvotes: 14

Views: 12148

Answers (4)

zupa
zupa

Reputation: 13442

What happens under the hood

Because the other answers don't explain that.

Go maps are hash maps. Simplified, it means they are arrays under the hood. Keys are converted to indexes via a hashing (hence hash maps). Crucially, every map has a unique salt that is used by the hash function to make sure different maps will store elements in different order in the underlying array.

Iterating over a map is simply walking over the array. When you write the map during iteration, you insert new elements into the array. This may happen either to the left of the current element, in which case it won't be visited by the iteration, or to the right, in which case it will be visited.

Because of the unique salt, sometimes the inserted element will end up to the left, sometimes to the right, hence the non-deterministic result.

Upvotes: 2

jub0bs
jub0bs

Reputation: 66244

The other answers have already explained the behavior you observe with your snippet.

Because your title is rather generic but your snippet only covers the addition of map entries while iterating over the map, here is a complementary example that should convince you that "cross-removing" map entries while iterating over the map is a bad idea (Playground):

package main

import "fmt"

func main() {
    m := map[string]int{"foo": 0, "bar": 1, "baz": 2}
    for k := range m {
        if k == "foo" {
            delete(m, "bar")
        }
        if k == "bar" {
            delete(m, "foo")
        }
    }
    fmt.Println(m)
}

The spec says:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If a map entry that has not yet been reached is removed during iteration, the corresponding iteration value will not be produced.

As a result, the program outputs either map[bar:1 baz:2] or map[baz:2 foo:0], but there is no way to tell which.

Upvotes: 3

icza
icza

Reputation: 417622

Spec: For statements with range clause says the behavior is unpredictable:

The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next. If a map entry that has not yet been reached is removed during iteration, the corresponding iteration value will not be produced. If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped. The choice may vary for each entry created and from one iteration to the next. If the map is nil, the number of iterations is 0.

Adding elements to the map you're ranging over, those entries may or may not be visited by the loop, you should not assume anything regarding to that.

Upvotes: 14

Burak Serdar
Burak Serdar

Reputation: 51577

Based on the language spec:

If a map entry is created during iteration, that entry may be produced during the iteration or may be skipped.

So if the new elements are skipped, the for-loop eventually ends.

Upvotes: 3

Related Questions