perl - 对使用 perl 合并哈希输出感到困惑

Question

为什么多次执行此程序后，合并哈希的输出会有所不同？

use strict;
use warnings;
my %data1=(a=>'1',b=>'2',c=>'3');
my %data2=(d=>'4',e=>'5',f=>'6');
my %data3=(%data1,%data2);
while(my($key,$value)=each %data3)
{
    print "$key:$value\n";
}

• 我已经验证了堆栈溢出链接(What decides the order of keys when I print a Perl hash?)，但我仍然无法找到正确的解决方案。
• 以上代码解释了哈希的合并。
• 我的问题是为什么每次执行 Perl 程序时哈希的输出都会发生变化。
• 谁能解释输出中的随机变化？

Answer 1

Perl 中的哈希没有固有的顺序，这是哈希工作的基础。

散列中的数据存储在列表中。每个 key 都通过 hash function 运行。 (它的名字来自哪里)以找出它存储在列表中的哪个位置。 “foo”可能会进入插槽 3，“bar”可能会进入插槽 8。让我举个例子。

假设您的哈希将内容存储在一个包含 8 个元素长(0 到 7)的列表中。我们非常糟糕的哈希函数将 key 中每个字符的 ASCII 码相加，然后取 modulus列表的长度。所以 foo 是 102 + 111 + 111 = 324。然后除以 8 并取余数: 4. $hash{"foo"} = 42 实际上是 $hash[4] = ['foo', 42]。

bar 是 98 + 97 + 114 = 309。 309 mod 8 是 5。$hash{"bar"} = 23 实际上是 $hash[5] = ['bar', 23]。 Perl 的哈希函数涉及更多，但你明白了。

通过这种方式，无论散列有多大，您都可以非常快速地添加和删除键。这被称为 "constant time" or O(1)其中算法的速度不取决于数据的大小。

当您要求 keys %hash 或 each %hash 时，Perl 将按照它们在内部列表中的明显随机顺序返回这些键。这就是哈希没有特定顺序的原因。

在旧版本的 Perl 中，每次运行程序时，通常都会对相同的哈希进行相同的排序，但出于安全原因，在 Perl 5.8.1 中故意更改了这一点。现在哈希函数包含了一点随机性，所以每次运行程序时，您都会得到不同的 key 顺序。为什么？考虑一下当两个键进入同一个槽时会发生什么。

bar 和 baz 都哈希为 5。这称为“哈希冲突”。它们是正常的，并且有多种方法可以处理冲突，但是它们会降低哈希的效率。冲突越多，在哈希中查找 key 所需的计算能力就越大。一个好的哈希不会有很多冲突。

如果您的哈希函数是可预测的，则可以创建一个非常长的键列表，这些键会全部发生冲突。这将使处理散列使用大量的 CPU 能力。这可用于创建 denial-of-service attack .最简单的是将病理键列表作为 HTML 表单字段传入。大多数 Perl 程序将采用表单字段并将它们放在散列中。因此，您可以通过制作正确的 URL 来严重降低 Web 服务器的速度。

现在 Perl 在其哈希函数中加入了一些随机性，攻击者不能再创建会导致冲突的键列表。

---

如果你想要订购，你要么必须自己添加......

for my $key (sort { $a cmp $b } keys %data3) {
    my $value = $data3{$key};
    print "$key: $value\n";
}

...或者使用不是散列的东西，比如 Hash::Ordered这将保留已添加到哈希的订单项。

use Hash::Ordered;

my $data = Hash::Ordered->new(d=>'4',e=>'5',f=>'6');
$data->merge( a=>'1',b=>'2',c=>'3' );

my $iterator = $data->iterator;
while( my($key, $value) = $iterator->() ) {
    print "$key: $value\n";
}

# d: 4
# e: 5
# f: 6
# c: 3
# b: 2
# a: 1