使用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?），但我仍然无法找到TP合适的解决方案。
• 上面的代码解释了哈希的合并。
• 我的问题是为什么哈希的输出在每次执行Perl程序时都会改变。
• 任何人都可以解释输出中的随机变化吗？

Answer 1

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

散列中的数据存储在列表中。每个密钥都通过hash function（从中得到它的名字）来找出它存储在列表上的什么位置。 “foo”可能在第3时隙，“bar”可能在第8时隙。让我举个例子。

比方说，你的散列存储的东西在8个元素长（0到7）列表中。我们非常糟糕的哈希函数将密钥中每个字符的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中更改的。现在散列函数会包含一些随机性，所以每次程序运行时，您都会得到不同的键值顺序。为什么？考虑当两个键进入同一个插槽时会发生什么。

bar和baz都散到5这就是所谓的“哈希冲突”。它们是正常的，并且有各种方式来处理碰撞，但是它们使得哈希效率更低。碰撞越多，在散列中查找密钥所需的计算能力就越多。一个好的散列不会有很多冲突。

如果你的散列函数是可预测的，那么可以创建一个非常长的键列表，这将会使全部碰撞。这将使得哈希处理使用大量的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