分配顺序

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

Assignment order

问题

让我们看一下下面的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}]

为什么这个小修改会影响到map的顺序呢?

英文:

Let's look at the following Go code:

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

It outputs this:

{40.68433 74.39967}

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

However, if I change one minor part of the test vertex declaration, by moving the right "}" 4 spaces, like so:

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

.. then the output changes to this:

{40.68433 74.39967}

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

Why does that little modification affect the order of my map?

答案1

得分: 15

"order"的映射取决于使用的哈希函数。哈希函数是随机的,以防止使用哈希碰撞的拒绝服务攻击。有关详细信息,请参阅问题跟踪器:

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

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

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

英文:

Map "order" depends on the hash function used. The hash function is randomized to prevent denial of service attacks that use hash collisions. See the issue tracker for details:

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

Map order is not guaranteed according to the specification. Although not done in current go implementations, a future implementation could do some compacting during GC or other operation that changes the order of a map without the map being modified by your code. It is unwise to assume a property not defined in the specification.

> 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.

答案2

得分: 7

一个地图不应该总是以任何固定的顺序打印它的键元素:
参见“Go:什么决定了地图键的迭代顺序?

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

尽管规范中没有明确说明(参考地图类型2):

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

实际上,规范确实有明确说明,但在For语句部分

地图的迭代顺序没有指定,并且不能保证从一次迭代到下一次迭代是相同的

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

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

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


go-nuts线程指出:

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

对此,Patrick Mylund Nielsen回答道:

但实际上,丹的笔记是Python开发人员不愿采用哈希IV随机化的主要论据-它破坏了他们的单元测试!PHP最终选择根本不这样做,而是限制了http.Request头的大小,Oracle和其他人根本不认为这是一个语言问题。
Perl看到了这个问题,并应用了类似于Go的修复方法,该方法在2003年的Perl 5.8.1中包含。
我可能错了,但我认为当这篇论文被提出时,他们是唯一一个真正关心的人:“通过算法复杂性攻击进行拒绝服务”,攻击哈希表。

分配顺序
(最坏的哈希表冲突)

对于其他人来说,这个在大约一年前非常流行的东西是一个很好的动力:
28c3:针对Web应用平台的有效拒绝服务攻击(YouTube视频,2011年12月)”,展示了大多数流行的Web编程语言和平台(包括PHP,ASP.NET,Java等)实现中的一个常见缺陷可以(滥)用来迫使Web应用服务器在几分钟到几小时内使用99%的CPU处理单个HTTP请求。
这种攻击在很大程度上与底层Web应用程序无关,只依赖于Web应用程序服务器通常的一个共同事实。

英文:

A map shouldn't always print its key-element in any fixed order:
See "Go: what determines the iteration order for map keys?"

> However, in the newest Go weekly release (and in Go1 which may be expected to be released this month), the iteration order is randomized (it starts at a pseudo-randomly chosen key, and the hashcode computation is seeded with a pseudo-random number).
If you compile your program with the weekly release (and with Go1), the iteration order will be different each time you run your program.

It isn't exactly spelled out like that in the spec though (Ref Map Type):

> 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.

Actually, the specs do spell it out, but in the For statement section:

> The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.

> - If map entries that have not yet been reached are deleted during iteration, the corresponding iteration values will not be produced.

  • If map entries are inserted during iteration, the behavior is implementation-dependent, but the iteration values for each entry will be produced at most once.
  • If the map is nil, the number of iterations is 0.

This has been introduced by code review 5285042 in October 2011:

> runtime: random offset for map iteration


The go-nuts thread points out:

> The reason that "it's there to stop people doing bad stuff" seemed particularly weak.
Avoiding malicious hash collisions makes a lot more sense.
Further the pointer to the code makes it possible in development to revert that behaviour in the case that there is an intermittent bug that's difficult to work through.

To which Patrick Mylund Nielsen replies:

> Dan's note was actually the main argument why Python devs were reluctant to adopt hash IV randomization--it broke their unit tests! PHP ultimately chose not to do it at all, and instead limited the size of the http.Request header, and Oracle and others didn't think it was a language problem at all.
Perl saw the problem and applied a fix similar to Go's which was included in Perl 5.8.1 in 2003.
I might be wrong, but I think they were the only ones to actually care then when this paper was presented: "Denial of Service via Algorithmic Complexity Attacks", attacking hash tables.

> 分配顺序
(Worst-case hash table collisions)

> For others, this, which became very popular about a year ago, was a good motivator:
"28c3: Effective Denial of Service attacks against web application platforms (YouTube video, December 2011)", which shows how a common flaw in the implementation of most of the popular web
programming languages and platforms (including PHP, ASP.NET, Java, etc.) can be (ab)used to force web application servers to use 99% of CPU for several minutes to hours for a single HTTP request.
This attack is mostly independent of the underlying web application and just
relies on a common fact of how web application servers typically work..

huangapple
  • 本文由 发表于 2012年8月8日 04:14:07
  • 转载请务必保留本文链接:https://go.coder-hub.com/11853396.html
匿名

发表评论

匿名网友

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

确定