8

Perl のハッシュ キーの順序については、あまり保証されていません。2つのハッシュがまったく同じキーを使用している限り、それらはまったく同じ順序になると言う、私が見つけることができないドキュメントに言及はありますか?

短いテストでそれが確認されたようです。2 つの異なるハッシュへの割り当ての間に内部キー テーブル用に追加のキーを生成しても、それらのキーは同じ順序で返されます。

my %aaa;
my %bbb;
my %ccc;
my %ddd;

@aaa{qw(a b c d e f g h i j k l)}=();
# Let's see if generating more keys for internal table matters
@ccc{qw(m n o p q r s t u v w x)}=();
@bbb{qw(a b c d e f g h i j k l)}=();
# Just to test if different insertion order matters
@ddd{qw(l k c d e f g h i j a)}=(); $ddd{b} = ();

print keys %aaa, "\n";
print keys %bbb, "\n";
print keys %ddd, "\n";

ただし、udocumented の動作には依存しません。ドキュメントで簡単に見つけることができる唯一の事実は、ハッシュが変更されていない限り、すべて同じ順序を使用しkeysますvalues。each

4

6 に答える 6

13

perlsec より:

Perl はハッシュ キーの順序を一切保証しておらず、順序は Perl 5 の存続期間中にすでに数回変更されています。

http://perldoc.perl.org/perlsec.html

于 2012-10-04T09:25:09.127 に答える
7

より長いテストは反証します。

そのため、同じキー セットを持つ異なるハッシュが常に同じ順序になるとは限りません。私にとって、以下のプログラムは、キーを持つ 2 つのハッシュqw(a b c d e f)の順序が異なる可能性があることを示しています。

v5.16.0
%h1: ecabdf
%h2: eadcbf

プログラム：

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw(say);

# http://stackoverflow.com/q/12724071/132382

use constant KEYS => qw(a b c d e f);

my %h1 = map { $_ => undef } KEYS;
my %h2 = map { $_ => undef } KEYS;

delete @h2{'b', 'd', 'f'};
@h2{'x', 'y', 'z'} = ();
@h2{'b', 'd', 'f'} = ();
delete @h2{'x', 'y', 'z'};

say $^V;
say '%h1: ', keys(%h1);
say '%h2: ', keys(%h2);

アップデート

挿入順序だけが重要であることを示す簡単な例を次に示します。

$ perl -MList::Util=shuffle -E \
> '@keys = ('a'..'z'); @h1{@keys} = @h2{shuffle @keys} = ();
> say keys(%$_) for (\%h1, \%h2)'
wraxdjyukhgftienvmslcpqbzo
warxdjyukhgftienmvslpcqbzo
#^^             ^^  ^^
#||             ||  ||
于 2012-10-04T14:58:35.013 に答える
5

これは信頼できないことが特に保証されています。

完全なのアルゴリズムの複雑さの攻撃のセクションを参照してくださいperlsec。その残念な矛盾にもかかわらず、それは次のように述べています

  • 5.8.1では、順序は毎回ランダムであることが保証されています。
  • 5.8.2以降では、Perlが病理学的動作を検出しない限り、順序は同じになります（具体的には、すべてが少数のバケットにハッシュされ、ハッシュパフォーマンスが低下する一連のキー）。そのような場合、「関数は疑似乱数シードによって摂動されます」。

ドキュメントは、順序が常に同じであることを保証するものではありません。実際、それは病理学的な場合には予​​測できないと具体的に述べています。将来のリリースでハッシュ関数が変更された場合、以前は縮退ハッシュを生成していなかったデータが変更され、ランダムな摂動を受ける可能性があります。

したがって、5.8.1を使用していない場合は、同じ順序になる可能性があり、 Perlを更新しても変更されない可能性がありますが、変更される可能性があります。5.8.1を使用している場合は、ランダムな順序が保証されます。

信頼できる順序が必要な場合は、キーの順序が保証されたハッシュを提供するCPANクラスの1つ（Tie :: Hash :: Indexed、Tie :: IxHash）を使用するか、キーを並べ替えます。数千未満のキーを持つハッシュがある場合、おそらく感知できるほどの違いに気付くことはありません。それ以上の場合は、とにかくデータベースなどのより重いソリューションを検討する必要があります。

編集：そしてそれをより面白くするために、キーは5.18の時点でランダムに並べられます。

于 2012-10-04T17:55:17.703 に答える
4

これは@pilcrowのものよりも短い反例です（この質問を最初に見たとき、明らかに彼の答えを見逃していました）：

#!/usr/bin/env perl

use strict; use warnings;

my @hashes = (
    { map { $_ => rand } 'a' .. 'z' },
    { map { $_ => rand } 'a' .. 'd', 'f' .. 'z' }
);

delete $hashes[0]{e};

print "@{[ keys %$_ ]}\n" for @hashes;

出力：

C:\temp> t
wraxdjyukhgftinvmslcp q b zo
wraxdjyukhgftinvmslcp b qzo
于 2012-10-04T16:17:15.323 に答える
3

perldoc -f keysには順序に関する情報があります:

ハッシュのキーは明らかにランダムな順序で返されます。実際のランダムな順序は、Perl の将来のバージョンで変更される可能性がありますが、値または各関数が生成する順序と同じであることが保証されています (ハッシュが変更されていない場合)。Perl 5.8.1 以降、セキュリティ上の理由から、Perl の異なる実行間でも順序が異なる場合があります(perlsec でのアルゴリズムの複雑さへの攻撃を参照してください)。

したがって、唯一の保証は、順序付けが保証されないことです。

于 2012-10-04T09:24:51.007 に答える