为什么每次运行程序时,从常量列表创建的哈希"以不同的顺序"？

Question

下面是Perl中的小脚本.每次运行此代码时,我都会得到不同的输出.

任何人都可以帮助我理解哈希变量的存储基础知识,即如何为Perl的哈希变量的键值对进行索引.

#!/usr/bin/perl

%data = ('John Paul' => 45, 'Lisa' => 30, 'Kumar' => 40);
@names = keys %data;
print "$names[0]\n";
print "$names[1]\n";
print "$names[2]\n";

Answer 1

这种行为记录在perlsec的算法复杂性攻击中.

哈希是链表的数组.散列函数将密钥转换为一个数字,该数字用作存储值的数组元素("bucket")的索引.多个密钥可以散列到相同的索引("冲突"),这是由链表处理的情况.

如果恶意用户知道散列算法,他可以设计散列到同一索引的值,从而导致散列退化为链接列表.这可能会导致某些应用程序性能大幅下降,因此可用作拒绝服务(DoS)攻击的一部分.

采取了两项措施来避免这种情况.一种方法是使散列算法加盐以随机化存储元素的顺序,另一种方法是通过扰乱迭代器访问散列元素的顺序来更难检测盐.

$ perl -E'
   my @k = "a".."z";
   for (1..3) {
      my %h = map { $_ => 1 } @k;
      say keys %h;
   }
'
iocmbygdkranwxfejuqpzvltsh
bmcoigdywrankujfxezpqlvths
juexfwarnkgdybmcoihstlvzpq

Answer 2

此行为描述于perldoc -f keys

哈希条目以明显随机的顺序返回。实际的随机顺序特定于给定的哈希；对两个哈希进行完全相同的一系列操作可能会导致每个哈希的顺序不同。任何对散列的插入都可能会改变顺序，任何删除也可能会改变顺序，但每个或多个键返回的最新键可能会被删除而不改变顺序。只要给定的散列未被修改，您就可以依赖键、值和每个键、值来重复返回彼此相同的顺序。

.. 为了阻止Algorithmic Complexity Attacks