在具有相同键的哈希值的文档中是否可以保证具有相同的顺序？

Question

关于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,values并且each只要哈希不被修改,所有都将使用相同的顺序.

Answer 1

来自perlsec:

Perl从未保证散列键的任何排序,并且在Perl 5的生命周期中排序已经多次改变.此外,散列键的排序一直并且继续受插入顺序的影响.

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

Answer 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
#^^             ^^  ^^
#||             ||  ||

Answer 3

特别保证这是不可靠的.

请参阅完整的算法复杂性攻击部分perlsec.尽管存在令人遗憾的不连贯性,但它表明了这一点

• 在5.8.1中,订单每次都保证是随机的.
• 在5.8.2及更高版本中,除非Perl检测到病态行为(具体地说,一系列密钥将全部散列到少量桶,导致散列性能受损),顺序将是相同的.在那些情况下,"函数被伪随机种子扰乱".

文档并不能保证订货会始终是相同的; 事实上,它明确规定,这将不会是一个病态的情况下,可以预见的.如果在将来的版本中改变散列函数,那么先前未生成退化散列的数据现在可能会这样做,然后将受到随机扰动的影响.

所以需要注意的是,如果你没有使用5.8.1,也许你会得到相同的订单,也许它在你更新你的Perl时不会改变,但它可能会.如果您使用5.8.1,则保证随机顺序.

如果你想要一个可靠的顺序,使用一个提供具有保证键顺序的散列的CPAN类 - Tie :: Hash :: Indexed,Tie :: IxHash - 或者只是对你的键进行排序.如果你的哈希值少于几千个键,你可能不会注意到明显的差异.如果它不止于此,那么你应该考虑一个比较重的解决方案,比如数据库.

编辑:只是为了使它更有趣,键将从5.18开始随机排序.

Answer 4

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

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

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

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