How to iterate maps in insertion order?

Question

I have a navbar as a map:

var navbar = map[string]navbarTab{
}

Where navbarTab has various properties, child items and so on. When I try to render the navbar (with for tabKey := range navbar) it shows up in a random order. I'm aware range randomly sorts when it runs but there appears to be no way to get an ordered list of keys or iterate in the insertion order.

The playground link is here: http://play.golang.org/p/nSL1zhadg5 although it seems to not exhibit the same behavior.

How can I iterate over this map without breaking the insertion order?

Answer 1

The general concept of the map data structure is that it is a collection of key-value pairs. "Ordered" or "sorted" is nowhere mentioned.

Wikipedia definition:

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears just once in the collection.

The map is one of the most useful data structures in computer science, so Go provides it as a built-in type. However, the language specification only specifies a general map (Map types):

A map is an unordered group of elements of one type, called the element type, indexed by a set of unique keys of another type, called the key type. The value of an uninitialized map is nil.

Note that the language specification not only leaves out the "ordered" or "sorted" words, it explicitly states the opposite: "unordered". But why? Because this gives greater freedom to the runtime to implement the map type. The language specification allows to use any map implementation like hash map, tree map etc. Note that the current (and previous) versions of Go use a hash map implementation, but you don't need to know that to use it.

The blog post Go maps in action is a must read regarding to this question.

Before Go 1, when a map was not changed, the runtime returned the keys in the same order when you iterated over its keys/entries multiple times. Note that this order could have changed if the map was modified as the implementation might needed to do a rehash to accommodate more entries. People started to rely on the same iteration order (when map was not changed), so starting with Go 1 the runtime randomizies map iteration order on purpose to get the attention of the developers that the order is not defined and can't be relied on.

What to do then?

If you need a sorted dataset (be it a collection of key-value pairs or anything else) either by insertion order or natural order defined by the key type or an arbitrary order, map is not the right choice. If you need a predefined order, slices (and arrays) are your friend. And if you need to be able to look up the elements by a predefined key, you may additionally build a map from the slice to allow fast look up of the elements by a key.

Either you build the map first and then a slice in proper order, or the slice first and then build a map from it is entirely up to you.

The aforementioned Go maps in action blog post has a section dedicated to Iteration order:

When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. Since Go 1 the runtime randomizes map iteration order, as programmers relied on the stable iteration order of the previous implementation. If you require a stable iteration order you must maintain a separate data structure that specifies that order. This example uses a separate sorted slice of keys to print a map[int]string in key order:

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}

P.S.:

...although it seems to not exhibit the same behavior.

Seemingly you see the "same iteration order" on the Go Playground because the outputs of the applications/codes on the Go Playground are cached. Once a new, yet-unique code is executed, its output is saved as new. Once the same code is executed, the saved output is presented without running the code again. So basically it's not the same iteration order what you see, it's the exactly same output without executing any of the code again.

P.S. #2

Although using for range the iteration order is "random", there are notable exceptions in the standard lib that do process maps in sorted order, namely the encoding/json, text/template, html/template and fmt packages. For more details, see In Golang, why are iterations over maps random?

Answer 2

Go maps do not maintain the insertion order; you will have to implement this behavior yourself.

Example:

type NavigationMap struct {
    m map[string]navbarTab
    keys []string
}

func NewNavigationMap() *NavigationMap { ... }

func (n *NavigationMap) Set(k string, v navbarTab) {
    n.m[k] = v
    n.keys = append(n.keys, k)
}

This example is not complete and does not cover all use-cases (eg. updating insertion order on duplicate keys).

If your use-case includes re-inserting the same key multiple times (this will not update insertion order for key k if it was already in the map):

func (n *NavigationMap) Set(k string, v navbarTab) {
    _, present := n.m[k]
    n.m[k] = v
    if !present {
        n.keys = append(n.keys, k)
    }
}

Choose the simplest thing that satisfies your requirements.