Google Go Lang转让订单

Question

我们来看看以下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}]

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

Answer 1

映射"顺序"取决于使用的散列函数.哈希函数是随机的,以防止使用哈希冲突的拒绝服务攻击.有关详细信息,请参阅问题跟踪器:

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

根据规范不保证地图顺序.虽然在当前的go实现中没有完成,但是未来的实现可以在GC或其他操作期间进行一些压缩,这些操作会改变映射的顺序而不会使代码修改映射.假设未在规范中定义的属性是不明智的.

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

Answer 2

地图不应始终以任何固定顺序打印其键元素:
请参阅" Go:什么决定了地图键的迭代顺序？ "

然而,在最新的Go每周版本中(以及可能预期在本月发布的Go1中),迭代顺序是随机的(它从伪随机选择的密钥开始,并且哈希码计算以伪随机方式播种)数).
如果使用每周版本(以及使用Go1)编译程序,则每次运行程序时迭代顺序都会不同.

虽然(参考地图类型)没有像规范那样精确拼写:

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

实际上,规范确实拼写出来,但在For语句部分:

未指定地图上的迭代顺序,并且不保证从一次迭代到下一次迭代是相同的.

• 如果在迭代期间删除尚未到达的映射条目,则不会生成相应的迭代值.
• 如果在迭代期间插入了映射条目,则行为依赖于实现,但每个条目的迭代值最多只会生成一次.
• 如果映射为nil,则迭代次数为0.

这是由2011年10月的代码审查5285042引入的:

runtime:地图迭代的随机偏移量

在去螺母螺纹指出:

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

Patrick Mylund Nielsen回复:

Dan的说明实际上是为什么Python开发人员不愿意采用哈希IV随机化的主要论点 - 它打破了他们的单元测试!PHP最终选择不执行此操作,而是限制了http.Request标头的大小,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应用程序服务器通常如何工作的常见事实.