文档中是否保证具有相同键的哈希表也具有相同的顺序？

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";

然而，我不会依赖于未经记录的行为。文档中容易找到的事实是，只要哈希表没有被修改，keys、values和each都将使用相同的顺序。

- Oleg V. Volkov

Answer 1

来自perlsec：

Perl从未保证哈希键的顺序，在Perl 5的生命周期中，这种顺序已经改变了多次。此外，哈希键的顺序始终受到插入顺序的影响。

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

- matt freake

---

是的，我明白顺序本身并不保证，但仍然无法确定在不同的哈希中是否会有相同的伪随机序列。我添加了第三个哈希，插入顺序不同：@ddd{qw(l k c d e f g h i j a)}=(); $ddd{b} = (); 但在 print 中仍然显示相同的顺序。 - Oleg V. Volkov

@OlegV.Volkov，Disco指出“没有保证顺序”，这确实回答了你的问题。你问是否保证了特定类型的顺序（相同键的两个哈希之间的相同顺序），答案是否定的。它现在可能对你有用，但你不能依赖它一直有效。 - dan1111

@dan1111，这个短语并不意味着“没有任何顺序保证”，因为在perldoc -f keys中还有另一段话：“但是它保证的顺序要么与值相同，要么与每个函数生成的顺序相同。”可以看出，我们至少有一个保证，我正在寻找是否还有其他需要的保证。 - Oleg V. Volkov

这段话讲的是哈希表中相同哈希值的键的顺序，而不是不同哈希值的键的顺序。在不同哈希值的键的顺序方面没有任何保证。 - darch

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

# https://dev59.com/o2nWa4cB1Zd3GeqPxzDR

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

- pilcrow

---

这个关键字重新排序对我来说一直持续到5.8.8版本。 - pilcrow

嗯，这正是我一开始所预料的。而且，要证明某个东西在文档中不存在是很困难的，但实际演示无疑是对这种假设最好的论据。 - Oleg V. Volkov

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开始，键将随机排序。

- Joe McMahon

Answer 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
w r a x d j y u k h g f t i n v m s l c p q b z o
w r a x d j y u k h g f t i n v m s l c p b q z o

- Sinan Ünür

Answer 5

perldoc -f keys 中有一些关于排序的信息:

哈希表的键以似乎随机的顺序返回。实际的随机顺序可能会在将来的 Perl 版本中发生变化，但是确保与值或 each 函数生成的顺序相同（假设哈希表未被修改）。自 Perl 5.8.1 以来，由于安全原因，排序甚至可以在不同的 Perl 运行之间不同（参见 perlsec 中的算法复杂度攻击）。

因此，唯一的保证是没有排序得到保证。

- amon

---

那不相干。我比较不同哈希的顺序，但在同一个执行中。 - Oleg V. Volkov

@Oleg V. Volkov，这是100％相关的。您有两个相同的代码片段，并且引用的段落说可能会导致不同的排序，因此您可以得到不同的排序。 - ikegami

@ikegami，正如我在第一条评论中所提到的，我不关心“Perl的不同运行”-我只对SAME运行感兴趣。因此，这完全不相关。但是，我最近审查了引用中提到的perlsec，并发现了更相关的引用，我刚刚发布为自我回答。 - Oleg V. Volkov

我没有说过不同的运行状态！？！？ - ikegami

Answer 6

自至少5.18版本开始，在perldoc perlsec中明确提到以下内容：

keys、values和each以哈希表随机顺序返回项。通过插入修改哈希表将改变该哈希表的迭代顺序。

---

Perl从未保证哈希键的任何顺序，并且在Perl 5的生命周期中，排序已经多次更改。此外，哈希键的排序始终受到插入顺序和对哈希进行的更改历史的影响，并将继续受到影响。

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

- Oleg V. Volkov