3

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

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";
}
  • 我已经验证了堆栈溢出链接（当我打印 Perl 哈希时，什么决定了键的顺序？），但我仍然无法找到正确的解决方案。
  • 上面的代码解释了哈希的合并。
  • 我的问题是为什么每次执行 Perl 程序时哈希的输出都会发生变化。
  • 谁能解释输出中的随机变化？
4

2 回答 2

8

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

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

假设您的哈希将内容存储在一个包含 8 个元素长（0 到 7）的列表中。我们非常糟糕的哈希函数将键中每个字符的 ASCII 码相加，然后取列表长度的模数。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 的散列函数涉及更多，但你明白了。

这样一来，无论散列有多大，您都可以非常快速地添加和删除密钥。这被称为“恒定时间”或 O(1)，其中算法的速度不取决于数据的大小。

当你请求keys %hashoreach %hash时，Perl 将按照它们在内部列表中的明显随机顺序返回键。这就是为什么哈希没有特定顺序的原因。

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

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

如果您的哈希函数是可预测的，则可以创建一个很长的键列表，这些键都会发生冲突。这将使处理散列使用大量的 CPU 能力。这可用于创建拒绝服务攻击。最简单的是将病理键列表作为 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
于 2015-11-02T05:05:16.260 回答
1

正如前面的答案中提到的那样，散列被认为具有随机顺序。然而，有一个名为“Tie::IxHash”的 perl 核心模块（您不需要安装），它将您的散列绑定为像这样的有序散列：

use strict;
use warnings;
use Tie::IxHash;

tie(my %data1, "Tie::IxHash",a=>'1',b=>'2',c=>'3');
@data1{'d','e','f'} = (4,5,6);
$data1{'g'} = 7;

while(my($key,$value)=each %data1)
{
    print "$key:$value\n";
}

此外，此模块将在添加条目时保留顺序，如“Hash::Ordered”，但它允许您使用普通哈希，它是任何 perl 安装附带的核心模块。在您的情况下，当然必须绑定所有 3 个哈希以保持排序。否则还有一个面向对象接口，它提供更高级的功能，如“SortByKeys”、“SortByValues”、“ReOrder”等。

于 2019-12-15T13:35:06.503 回答