如何按插入顺序迭代映射(maps)?

huangapple go评论96阅读模式
英文:

How to iterate maps in insertion order?

问题

我有一个作为地图的导航栏:

var navbar = map[string]navbarTab{
}

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

这是playground链接:http://play.golang.org/p/nSL1zhadg5,尽管它似乎没有展示相同的行为。

如何在不破坏插入顺序的情况下迭代这个地图?

英文:

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?

答案1

得分: 38

地图数据结构的一般概念是它是一组键值对的集合。没有提到“有序”或“排序”。

Wikipedia定义:

在计算机科学中,关联数组映射符号表字典是由一组(key, value)对组成的抽象数据类型,使得集合中的每个可能的键只出现一次。

地图是计算机科学中最有用的数据结构之一,因此Go语言提供了它作为内置类型。然而,语言规范只指定了一个一般的地图(Map types):

地图是一组无序的元素,元素类型称为元素类型,由另一种类型的唯一键集索引。未初始化地图的值为nil

请注意,语言规范不仅省略了“有序”或“排序”这些词,而且明确指出了相反的情况:“无序”。但是为什么呢?因为这给了运行时更大的自由来实现地图类型。语言规范允许使用任何地图实现,如哈希地图、树地图等。请注意,当前(和之前)的Go版本使用了哈希地图实现,但你不需要知道这一点才能使用它。

关于这个问题,必读的博文是Go maps in action

在Go 1之前,当地图没有改变时,运行时在多次迭代其键/条目时以相同的顺序返回键。请注意,如果地图被修改,此顺序可能会改变,因为实现可能需要重新哈希以容纳更多的条目。人们开始依赖相同的迭代顺序(当地图没有改变时),所以从Go 1开始,运行时有意地随机化地图迭代顺序,以引起开发人员的注意,顺序没有定义,不能依赖它。

那么该怎么办呢?

如果你需要一个按插入顺序或键类型定义的自然顺序(或任意顺序)的排序数据集(无论是键值对的集合还是其他任何东西),map不是正确的选择。如果你需要一个预定义的顺序,切片(和数组)是你的朋友。如果你需要能够通过预定义的键查找元素,你可以另外从切片构建一个地图,以便通过快速查找元素。

你可以先构建map,然后按正确的顺序构建一个切片,或者先构建切片,然后从中构建一个map,完全取决于你。

上述的 Go maps in action 博文有一个专门讲述迭代顺序的部分:

当使用range循环迭代地图时,迭代顺序没有指定,也不能保证从一次迭代到下一次迭代是相同的。从Go 1开始,运行时随机化地图迭代顺序,因为程序员依赖于先前实现的稳定迭代顺序。如果你需要稳定的迭代顺序,你必须维护一个单独的数据结构来指定该顺序。以下示例使用一个单独的已排序键切片按键顺序打印map[int]string

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

附言:

...尽管它似乎没有展示相同的行为。

在Go Playground上看到“相同的迭代顺序”,是因为Go Playground上的应用程序/代码的输出是缓存的。一旦执行一个新的、尚未执行过的代码,它的输出就会被保存为新的输出。一旦执行相同的代码,保存的输出就会被呈现,而不会再次运行代码。所以基本上你看到的不是相同的迭代顺序,而是完全相同的输出,而不执行任何代码。

附言 #2

尽管使用for range迭代顺序是“随机的”,但标准库中有一些显著的例外,它们以排序顺序处理地图,即encoding/jsontext/templatehtml/templatefmt包。更多详情请参见https://stackoverflow.com/questions/55925822/in-golang-why-are-iterations-over-maps-random/55925880#55925880

英文:

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 https://stackoverflow.com/questions/55925822/in-golang-why-are-iterations-over-maps-random/55925880#55925880

答案2

得分: 31

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

选择最简单的方法来满足你的需求。

英文:

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.

huangapple
  • 本文由 发表于 2015年3月9日 02:44:57
  • 转载请务必保留本文链接:https://go.coder-hub.com/28930416.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定