8

Perl 中的哈希键顺序没有太多保证。在我找不到的文档中是否有任何提及会说只要两个哈希使用完全相同的键，它们就会以完全相同的顺序排列？

简短的测试似乎证实了这一点。即使我在分配给两个不同的哈希之间为内部键表生成了一些额外的键，它们的键也会以相同的顺序返回：

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。valueseach

4

6 回答 6

13

来自 perlsec：

Perl 从不保证散列键的任何顺序，并且在 Perl 5 的生命周期中，顺序已经改变了好几次。此外，散列键的顺序一直并且继续受到插入顺序的影响。

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

于 2012-10-04T09:25:09.127 回答
7

更长的测试证明了这一点。

因此，具有相同键集的不同哈希并不总是具有相同的顺序。对我来说，下面的程序演示了两个带有键的哈希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 类之一 - 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:\温度> 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 回答
0

从至少 5.18 开始，在perldoc perlsec中明确提到了以下内容：

keys, values, 并each以每个哈希随机顺序返回项目。通过插入修改哈希将更改该哈希的迭代顺序。

Perl 从未保证哈希键的任何顺序，并且在 Perl 5 的生命周期中顺序已经改变了好几次。此外，哈希键的顺序一直并且继续受到插入顺序和历史记录的影响哈希在其生命周期内所做的更改。

因此，具有相同键集的两个哈希不能明确保证以相同的顺序迭代。

于 2017-04-24T11:04:03.043 回答