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

ただし、テスト頂点宣言のマイナーな部分を1つ}変更すると、次のように右の""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またはマップの順序を変更するその他の操作中に圧縮を実行する可能性があります。仕様で定義されていないプロパティを想定することは賢明ではありません。

マップは、要素タイプと呼ばれる1つのタイプの要素の順序付けられていないグループであり、キータイプと呼ばれる別のタイプの一意のキーのセットによってインデックスが付けられます。

于 2012-08-07T20:23:54.603 に答える
7

マップは、常にそのキー要素を固定された順序で出力する必要はありません。「実行：マップキーの反復順序を決定するものは何ですか？」
を参照してください。

ただし、最新のGoウィークリーリリース（および今月リリースが予定されているGo1）では、反復順序がランダム化されます（疑似ランダムに選択されたキーから開始され、ハッシュコードの計算には疑似ランダムがシードされます）。番号）。
ウィークリーリリース（およびGo1）を使用してプログラムをコンパイルする場合、プログラムを実行するたびに反復順序が異なります。

ただし、仕様ではそのように正確に記述されていません（Ref Map Type）：

マップは、要素タイプと呼ばれる1つのタイプの要素の順序付けられていないグループであり、キータイプと呼ばれる別のタイプの一意のキーのセットによってインデックスが付けられます。

実際には、仕様はそれを詳しく説明していますが、Forステートメントセクションでは：

マップ上の反復順序は指定されておらず、ある反復から次の反復まで同じであることが保証されていません。

  • まだ到達していないマップエントリが反復中に削除された場合、対応する反復値は生成されません。
  • マップエントリが反復中に挿入された場合、動作は実装に依存しますが、各エントリの反復値は最大で1回生成されます。
  • マップがnilの場合、反復回数は0です。

これは、2011年10月のコードレビュー5285042によって導入されました。

ランタイム：マップ反復のランダムオフセット

ゴーナッツスレッドは次のように指摘しています。

「人々が悪いことをするのを止めるためにそこにある」という理由は特に弱いように思われました。
悪意のあるハッシュの衝突を回避することは、はるかに理にかなっています。
さらに、コードへのポインタを使用すると、開発中に、処理が困難な断続的なバグが発生した場合に、その動作を元に戻すことができます。

Patrick Mylund Nielsenが返信します：

ダンのメモは、Python開発者がハッシュIVランダム化を採用することを躊躇した主な議論でした-それは彼らの単体テストを破りました！PHPは最終的にそれをまったく行わないことを選択し、代わりにhttp.Requestヘッダーのサイズを制限し、Oracleなどはそれが言語の問題であるとはまったく考えていませんでした。
Perlは問題を認識し、2003年にPerl 5.8.1に含まれていたGoと同様の修正を適用しました。私は間違っているかもしれませんが、このペーパーが提示さ
れたときに実際に気にかけたのは彼らだけだったと思います。アルゴリズムの複雑さの攻撃"、ハッシュテーブルを攻撃します。

最悪のシナリオ
（最悪の場合のハッシュテーブルの衝突）

他の人にとっては、これは約1年前に非常に人気があり、
「28c3：Webアプリケーションプラットフォームに対する効果的なサービス拒否攻撃（YouTubeビデオ、2011年12月）」の良い動機となりました。人気のあるWebプログラミング言語とプラットフォーム（PHP、ASP.NET、Javaなどを含む）のほとんどは、（ab）を使用して、Webアプリケーションサーバーが単一のHTTP要求に対して数分から数時間CPUの99％を使用するように強制できます。
この攻撃は、基盤となるWebアプリケーションからほとんど独立しており、Webアプリケーションサーバーが通常どのように機能するかという一般的な事実に依存しています。

于 2012-08-07T20:23:16.913 に答える