如何按插入顺序迭代地图？

Question

我有一个导航栏作为地图：

var navbar = map[string]navbarTab{
}

其中 navbarTab 具有各种属性、子项等。当我尝试渲染导航栏（使用 for tabKey := range navbar）时，它以随机顺序显示。我知道 range 在运行时会随机排序，但似乎无法获得有序的键列表或按插入顺序迭代。

游乐场 link 在这里：http://play.golang.org/p/nSL1zhadg5 尽管它似乎没有表现出相同的行为。

如何在不破坏插入顺序的情况下遍历此映射？

Answer 1

Go maps不维护插入顺序；您必须自己实施此行为。

示例：

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)
}

此示例不完整且未涵盖所有用例（例如，更新重复键上的插入顺序）。

如果您的用例包括多次重新插入相同的键（这不会更新键 k 的插入顺序，如果它已经在地图中）：

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

选择满足您要求的最简单的东西。

Answer 2

地图数据结构的一般概念是，它是键值对的集合。 "Ordered" 或 "sorted" 没有被提及。

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.

map 是计算机科学中最有用的数据结构之一，因此 Go 将其作为内置类型提供。但是，语言规范只指定了一个 general 映射 (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.

请注意，语言规范不仅省略了 "ordered" 或 "sorted" 词，它还明确指出了相反的内容： “无序”。但为什么？因为这为运行时提供了 更大的自由度 来实现地图类型。语言规范允许使用任何映射实现，如 hash 映射、tree 映射等。请注意，当前（和以前）版本的 Go 使用哈希映射实现，但您不需要知道它就可以使用它。

博客 post Go maps in action 是关于这个问题的必读内容。

在 Go 1 之前，当映射未更改时，运行时会在您多次迭代其 keys/entries 时以相同的顺序返回键。请注意，如果映射被修改，此顺序 可能会 更改，因为实现可能需要重新哈希以容纳更多条目。人们开始依赖相同的迭代顺序（当 map 未更改时），因此从 Go 1 开始，运行时随机化 map 迭代顺序故意以引起开发人员的注意顺序没有定义，不能依赖。

那怎么办？

如果您需要按插入顺序或键类型定义的自然顺序或任意的顺序，map 不是正确的选择。如果你需要一个预定义的顺序，切片（和数组）是你的朋友。如果您需要能够通过预定义键查找元素，您可以另外从切片构建一个映射以允许通过 [=59= 快速查找元素]键.

是先构建 map 然后按正确顺序构建切片，还是先构建切片然后从中构建 map 完全取决于您。

前面提到的 Go maps in action 博客 post 有一个专用于 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.

您似乎在 Go Playground 上看到了“相同的迭代顺序”，因为 Go Playground 上 applications/codes 的输出被缓存。一旦执行了新的但唯一的代码，其输出将另存为新代码。一旦执行了相同的代码，保存的输出将再次显示而没有运行代码。所以基本上它与您看到的迭代顺序不同，它是完全相同的输出而无需再次执行任何代码。

P.S。 #2

虽然使用 for range 迭代顺序是“随机”的，但在按排序顺序执行过程映射的标准库中有明显的例外，即 encoding/json、text/template、 html/template 和 fmt 包。有关详细信息，请参阅 In Golang, why are iterations over maps random?

如何按插入顺序迭代地图？

How to iterate maps in insertion order?

iteration

dictionary

go