3

让我们看看下面的 Go 代码：

package main

import "fmt"

type Vertex struct {
    Lat, Long float64
}

var m map[string]Vertex

func main() {
    m = make(map[string]Vertex)
    m["Bell Labs"] = Vertex{
        40.68433, 74.39967,
    }
    m["test"] = Vertex{
        12.0, 100,
    }
    fmt.Println(m["Bell Labs"])
    fmt.Println(m)
}

它输出这个： 

{40.68433 74.39967}

map[Bell Labs:{40.68433 74.39967} test:{12 100}]

但是，如果我更改测试顶点声明的一小部分，通过向右移动“ }”4 个空格，如下所示：

m["test"] = Vertex{
    12.0, 100,
}

..然后输出变为：

{40.68433 74.39967}

map[test:{12 100} Bell Labs:{40.68433 74.39967}]

为什么这个小小的修改会影响我的地图顺序？

4

2 回答 2

14

映射“顺序”取决于使用的散列函数。散列函数是随机的，以防止使用散列冲突的拒绝服务攻击。有关详细信息，请参阅问题跟踪器：

http://code.google.com/p/go/issues/detail?id=2630

根据规范不保证地图顺序。尽管在当前的 go 实现中没有这样做，但未来的实现可能会在 GC 或其他更改映射顺序的操作期间进行一些压缩，而无需您的代码修改映射。假设规范中未定义的属性是不明智的。

映射是一种类型的无序元素组，称为元素类型，由另一种类型的一组唯一键索引，称为键类型。

于 2012-08-07T20:23:54.603 回答
7

地图不应该总是以任何固定的顺序打印它的键元素：
请参阅“ Go：什么决定了地图键的迭代顺序？ ”

然而，在最新的 Go 每周版本中（以及可能在本月发布的 Go1 中），迭代顺序是随机的（它从伪随机选择的键开始，哈希码计算以伪随机为种子）数字）。
如果您使用每周版本（和 Go1）编译程序，则每次运行程序时迭代顺序都会不同。

但是，它并没有像规范中那样完全拼写出来（Ref Map Type）：

映射是一种类型的无序元素组，称为元素类型，由另一种类型的一组唯一键索引，称为键类型。

实际上，规范确实说明了它，但在For 语句部分：

未指定映射的迭代顺序，也不保证从一次迭代到下一次迭代顺序相同。

  • 如果在迭代过程中删除了尚未到达的映射条目，则不会产生相应的迭代值。
  • 如果在迭代期间插入映射条目，则行为取决于实现，但每个条目的迭代值最多会生成一次。
  • 如果 map 为 nil，则迭代次数为 0。

这已由2011 年 10 月的代码审查 5285042引入：

运行时：地图迭代的随机偏移量

疯狂的线程指出：

“它的存在是为了阻止人们做坏事”的原因似乎特别弱。
避免恶意哈希冲突更有意义。
此外，指向代码的指针使得在开发中可以在存在难以解决的间歇性错误的情况下恢复该行为。

Patrick Mylund Nielsen 回复：

Dan 的注释实际上是 Python 开发人员不愿采用哈希 IV 随机化的主要论据——它破坏了他们的单元测试！PHP 最终选择了根本不做，而是限制了http.Requestheader 的大小，Oracle 等人根本不认为这是语言问题。
Perl 看到了这个问题并应用了类似于 Go 的修复程序，该修复程序在 2003 年包含在 Perl 5.8.1 中。
我可能是错的，但我认为当这篇论文发表时，他们是唯一真正关心的人：“拒绝服务通过算法复杂性攻击”，攻击哈希表。

最坏的情况是
（最坏情况的哈希表冲突）

对于其他人来说，这在大约一年前变得非常流行，是一个很好的动力：
“ 28c3：针对 Web 应用程序平台的有效拒绝服务攻击（YouTube 视频，2011 年 12 月） ”大多数流行的 Web 编程语言和平台（包括 PHP、ASP.NET、Java 等）都可以（ab）用于强制 Web 应用程序服务器在几分钟到几小时内为单个 HTTP 请求使用 99% 的 CPU。
这种攻击大多独立于底层 Web 应用程序，仅依赖于 Web 应用程序服务器通常如何工作的一个共同事实。

于 2012-08-07T20:23:16.913 回答