4

我是 Perl 脚本的新手，foreach对哈希变量有疑问。我想打印我的哈希的所有值。这是一个程序：

%colors = (a => 1, b=>2, c=>3, d=>4, e=>5);
foreach $colors(keys %colors)
{
    print "$colors{%colors} \n";
}

输出是：

5
3
1
2
4

为什么值是随机排序的？或者这种随机性背后的逻辑是什么？请澄清我的疑问。

4

4 回答 4

8

我认为您的困惑在于不知道 Hash 到底是什么。大多数语言都有类似于键值存储的东西，在 Ruby 和 Perl 中，它们被称为 Hashes，在 Java Maps 中，在 Python 字典中，等等......

它们本质上都是一样的，你将一个带有唯一键的值插入到一些底层数据结构中，以内存为代价直接访问它。

那么，当您将键和值添加到散列时，实际会发生什么？

散列是围绕散列函数的概念构建的，散列函数将一些值作为输入计算唯一的输出（理想情况下，每个输入都有自己的唯一输出）。如果两个输入都映射到相同的输出，则称为冲突。

现在我们需要讨论 Hash 是如何实现的，两个经典示例是使用单个数组或链表数组。我将在下面展示数组示例。

大批

在简单数组的情况下，哈希底层的数据结构只是一个一定大小的数组。散列函数用于计算该数组的索引。如果我们假设一个简单的哈希算法

h(x) = length(x) % ARRAY_SIZE

这x是一个字符串，ARRAY_SIZE是我们底层数组的大小，该语句将确保所有值x都在该范围内0..ARRAY_SIZE - 1

看一个视觉示例，考虑一个大小为 5 的数组：

   0     1     2     3     4
 ------------------------------
|     |     |     |     |      |
 ------------------------------

并假设我们正在尝试5使用 key存储值abcd，根据我们的散列算法

h('abcd') = length('abcd') % ARRAY_SIZE
          =      4         %      5
          =      4

因此该值5将存储在 index 4：

   0     1     2     3     4
 ------------------------------
|     |     |     |     |   5  |
 ------------------------------

现在如果我们尝试3使用 key存储值会发生什么dcba，这两个键是不同的，对吧？他们应该映射到不同的地方。

h('dcba') = length('dcba') % ARRAY_SIZE
          =      4         %      5
          =      4

哎呀！这个键也映射到索引4，那么我们现在要做什么？好吧，我们不能仅仅丢弃键值对，因为程序员显然需要/希望在他们的 Hash 中使用这种配对，所以我们需要决定在发生冲突时该怎么做。有很多算法可以做到这一点，但最简单的一种是在数组中寻找下一个开放的插槽并存储3它们。所以现在我们的数组看起来像：

   0     1     2     3     4
 ------------------------------
|   3  |     |     |     |  5  |
 ------------------------------

这不是一个非常深入的解释，但希望它能让您深入了解为什么从哈希中检索值似乎是随机的，这是因为底层数据结构不断变化，如果您现在要从哈希中请求密钥，您会可能会回来(3, 5)，即使您5先插入，也只是因为3首先出现在数组中。

希望这会有所帮助。

于 2013-07-25T13:07:45.977 回答
7

引用perldata - Perl 数据类型：

哈希是标量值的无序集合，由其关联的字符串键索引。

您可以sort使用键，或者，如果您想保留初始化中给出的顺序，请使用Tie::Hash::Indexed或Tie::IxHash。

于 2013-07-25T10:27:41.660 回答
3

perldockeys中的描述有以下片段：

哈希条目以明显随机的顺序返回。实际的随机顺序特定于给定的哈希；对两个散列进行完全相同的一系列操作可能会导致每个散列的顺序不同。任何插入到散列中的操作都可能会更改顺序，任何删除操作也一样，但每个或多个键返回的最新键可能会在不更改顺序的情况下被删除。只要给定的散列未被修改，您就可以依赖键、值和每个重复返回彼此相同的顺序。有关为什么哈希顺序随机化的详细信息，请参阅perlsec 中的算法复杂性攻击。除了这里提供的保证之外，Perl 的散列算法和散列遍历顺序的确切细节在任何 Perl 版本中都可能发生变化。

Perlsec对 Hash 算法进行了如下说明：

  • 散列算法 - 众所周知，像 Perl 中使用的散列算法容易受到对其散列函数的碰撞攻击。此类攻击涉及构建一组密钥，这些密钥会碰撞到同一个桶中，从而产生低效的行为。此类攻击通常依赖于发现用于将密钥映射到存储桶的哈希函数的种子。然后使用该种子对可用于发起拒绝服务攻击的密钥集进行暴力破解。在 Perl 5.8.1 中引入了一些更改来强化 Perl 对此类攻击的攻击，后来在 Perl 5.18.0 中，这些功能得到了增强，并添加了额外的保护。在撰写本文时，Perl 5.18.0 被认为已经很好地抵御了对其哈希实现的算法复杂性攻击。这主要归功于以下措施减轻攻击：

    • 哈希种子随机化
      为了不知道要为哪个种子生成攻击密钥集，这个种子在进程开始时随机初始化。这可以通过使用 PERL_HASH_SEED 环境变量来覆盖，请参阅 perlrun 中的 PERL_HASH_SEED。此环境变量控制项目的实际存储方式，而不是它们如何通过键、值和each呈现。

    • 散列遍历随机化
      与散列函数中使用的种子无关，键、值和每个都以每个散列随机顺序返回项目。通过插入修改哈希将更改该哈希的迭代顺序。可以通过使用 Hash::Util 中的 hash_traversal_mask() 或使用 PERL_PERTURB_KEYS 环境变量来覆盖此行为，请参阅 perlrun 中的 PERL_PERTURB_KEYS。请注意，此功能控制键的“可见”顺序，而不是它们存储的实际顺序。

    • 桶顺序扰动
      当项目碰撞到给定的哈希桶中时，它们存储在链中的顺序在 Perl 5.18 中不再可预测。这样做的目的是使观察碰撞变得更加困难。可以使用 PERL_PERTURB_KEYS 环境变量覆盖此行为，请参阅 perlrun 中的 PERL_PERTURB_KEYS。
    • 新
      的默认散列函数默认散列函数已被修改，目的是更难推断散列种子。
    • 替代散列函数
      源代码包括多种散列算法可供选择。虽然我们认为默认的 perl 哈希对攻击具有鲁棒性，但我们已将哈希函数 Siphash 作为备用选项包括在内。在 Perl 5.18.0 发布时，Siphash 被认为具有加密强度。这不是默认值，因为它比默认哈希慢得多。

如果不编译特殊的 Perl，就无法获得与 Perl 5.18.0 之前的任何版本完全相同的行为。最接近的方法是将 PERL_PERTURB_KEYS 设置为 0 并将 PERL_HASH_SEED 设置为已知值。由于上述安全考虑，我们不建议将这些设置用于生产用途。

Perl 从未保证哈希键的任何顺序，并且在 Perl 5 的生命周期中顺序已经改变了好几次。此外，哈希键的顺序一直并且继续受到插入顺序和历史记录的影响哈希在其生命周期内所做的更改。

另请注意，虽然哈希元素的顺序可能是随机的，但这种“伪排序”不应该用于像随机打乱列表这样的应用程序（使用 List::Util::shuffle()，请参阅 List::Util ，自 Perl 5.8.0 以来的标准核心模块；或 CPAN 模块 Algorithm::Numerical::Shuffle ），或用于生成排列（使用例如 CPAN 模块 Algorithm::Permute 或 Algorithm::FastPermute ），或用于任何加密应用程序.

于 2013-07-25T11:08:36.517 回答
2

您可以使用 sort 按字母顺序（因为您的键是字母数字）排序方式打印出结果，如下所示：

%colors = ("a" => 1, "b"=>2, "c"=>3, "d"=>4, "e"=>5);
foreach (sort keys %colors) {
    print $colors{$_} . "\n";
}

或者，如果您更喜欢按值排序：

%colors = ("a" => 1, "b"=>2, "c"=>3, "d"=>4, "e"=>5);
foreach (sort { $colors{$a} <=> $colors{$b} } keys %colors) {
    print $colors{$_} . "\n";
}
于 2013-07-25T10:59:03.463 回答