为什么Go不能按插入顺序迭代地图？

Question

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

var navbar = map[string]navbarTab{
}

哪里navbarTab有各种属性,儿童用品等.当我尝试渲染导航栏(带for tabKey := range navbar)时,它以随机顺序显示.我知道range它在运行时会随机排序,但似乎无法获得有序的键列表或迭代插入顺序.

游乐场链接在这里:http://play.golang.org/p/nSL1zhadg5虽然它似乎没有表现出相同的行为.

如何在不破坏插入顺序的情况下迭代此地图？

Answer 1

地图数据结构的一般概念是它是键值对的集合.没有提到"有序"或"有序".

维基百科定义:

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

该地图是计算机科学中最有用的数据结构之一,因此Go将其作为内置类型提供.但是,语言规范仅指定一般映射(映射类型):

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

请注意,语言规范不仅省略了"有序"或"已排序"的单词,而是明确指出相反的结构:"无序".但为什么？因为这为运行时提供了更大的自由来实现地图类型.语言规范允许使用任何地图实现,如哈希映射,树映射等.请注意,Go的当前(和以前的)版本使用哈希映射实现,但您不需要知道使用它.

关于这个问题,必须阅读博客文章Go map in action.

在Go 1之前,当未更改映射时,运行时多次迭代其键/条目时,运行符以相同的顺序返回键.请注意,如果修改了映射,则此顺序可能已更改,因为实现可能需要执行rehash以容纳更多条目.人们开始依赖相同的迭代顺序(当地图未被更改时),因此从Go 1开始,运行时随机数映射迭代顺序是为了引起开发人员的注意,订单未定义且无法依赖.

该怎么办？

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

要么map按照正确的顺序构建第一个然后是一个切片,要么首先构建一个切片,然后map从中构建一个切片完全取决于您.

上述Go map in action博文中有一个专门用于迭代顺序的部分:

当使用范围循环迭代映射时,未指定迭代顺序,并且不保证从一次迭代到下一次迭代是相同的.由于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])
}

PS:

......虽然它似乎没有表现出相同的行为.

看起来你在Go Playground上看到了"相同的迭代次序",因为Go Playground上的应用程序/代码的输出被缓存了.一旦执行了新的但唯一的代码,其输出将保存为新的.执行相同的代码后,将显示保存的输出,而无需再次运行代码.所以基本上它与您看到的迭代顺序不同,它是完全相同的输出而不再执行任何代码.

Answer 2

Go地图不保持插入顺序; 你必须自己实现这种行为.

例:

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已经在映射中,则不会更新密钥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)
    }
}

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