logo标签列表

在Perl中，何时更适合使用数组而不是哈希表？

arraysperlhash
11

假设你有一个数组@a = qw/ a b c d/;

和一个哈希%a=('a'=>1,'b'=>1,'c'=>1,'d'=>1);

除了在类似于必须遍历所有值的情况下（例如

for (@a){
    ....

如果你选择使用哈希表，那么你需要使用keys %a来进行操作，对吗？因为在哈希表中查找特定值的效率总是比在数组中高，是这样吗？

4
哈希键没有可预测的顺序，因此它与数组非常不同。 - leonbloy
4
如果关闭这个问题，那就太可惜了。我认为这是一个非常好的问题，它的答案可以帮助很多人。 - Borodin
可能是重复的问题: 为什么要使用数组而不是哈希表？ - ThisSuitIsBlackNot
1
@ThisSuitIsBlackNot，这不是与链接问题重复。链接的问题问的是$x{$i}是否真的比$x[$i]快。 (其实不是这样的。) 这与Tyler的问题无关。 - ikegami
在某些情况下使用哈希的另一个原因：https://dev59.com/rLLma4cB1Zd3GeqPUw6y#54833522 - Sam B
4个回答
10

    • 数组使用数字作为索引。
    • 哈希表使用字符串作为键。

    • 数组中所有索引都存在，包括最大索引。
    • 哈希表存在稀疏索引。（例如，“a”和“c”可以存在而不需要“b”。）

有许多 emergent properties。主要的是：

    • 可以使用数组存储有序列表。
    • 使用哈希表实现该功能会比较丑陋和低效。

    • 除非是最高索引元素，否则无法从数组中删除元素。
    • 虽然从使用数组实现的有序列表中删除除第一个或最后一个元素以外的元素效率低，但是可以删除。
    • 可以从哈希表中删除元素，并且这是有效的。
3

数组是有序的值列表，它们可以包含重复的值。

@array = qw(a b c a);

哈希表是一种将唯一键和可重复值进行映射的数据结构。哈希表是无序的，这意味着键以看似随机的顺序输出，而不是它们输入的顺序。

%hash = (a => 1, b => 2, c => 3);

哈希也可以作为集合使用，仅关注键时。集合是无序的，仅包含唯一的“值”（哈希的键）。

%set = (a => undef, b => undef, c => undef);

根据您的数据和算法，选择使用哪种取决于情况。如果顺序很重要（特别是如果无法排序以得出顺序）或者可能存在重复值，则使用数组。如果值必须唯一且不关心顺序，则使用集合（即使用哈希作为集合）。当唯一性很重要，而顺序不重要（或很容易进行排序），并且查找是基于任意值而不是整数时，请使用哈希。

您可以通过引用将数组和哈希组合在一起，创建任意复杂的数据结构。

@aoa = ([1, 2, 3], [4, 5, 6]);               # array of arrays ("2D" array)
%hoh = (a => { x => 1 }, b => { x => 2 });   # hash of hashes
@aoh = ({a => 1, b => 2}, {a => 3, b => 4}); # array of hashes
%hoa = (a => [1, 2], b => [3, 4]);           # hash of arrays
...etc.
1
关于“数组是有序值列表”的说法，这并不比哈希更为准确。例如，$a[2] = "a"; $a[0] = "b"; $a[1] = "c"; print values(@a); 和 $h{2} = "a"; $h{0} = "b"; $h{1} = "c"; print values(%h); 都无法给出 abc。这些值仅仅是被键控的，你可以对数组和哈希表进行键排序。实际上的区别在于对于数组来说，排序键更加高效。（在你提到push和pop之前，请记住你同样可以为哈希表创建可用的push和pop函数。） - ikegami
1
@ikegami：当然，数组是有序的。你的@a总是会打印为bca。它们是按索引排序的。我从未说过它们的排序是基于插入的。 - Michael Carman
要么你重复了我已经说过的话（你可以对索引进行排序），要么你是在说哈希也是有序的（按桶索引）。 （不要忘记哈希的核心是一个数组。单词“哈希”来自于将键哈希为用作该数组索引的数字的事实。） - ikegami
1
是的，哈希表是有序的，但是这个顺序对程序员来说是隐藏的，并且可能会在不经意间发生改变。从 Perl 5.18 开始，哈希表的顺序是随机的，并且在同一程序的两次执行之间不会相同。这就是为什么我说哈希表 实际上 是无序的。 - Michael Carman
1
另一方面，数组在perldata中被定义为有序的：“...数组是标量有序列表...”。这个顺序是有保证的（没有排序）。我有点困惑，不知道你为什么会持相反的观点。 - Michael Carman
我想说的是，你可以从哈希和数组中按键顺序获取元素。 - ikegami
2
这是关于使用数字作为哈希键的。它没有直接回答问题，因为它没有比较数组提供的便利设施，但我认为这是放置信息的好地方。
假设使用类似以下代码构建了具有十个元素的哈希表：
use strict;
use warnings;

my %hash;
my $n = 1000;
for (1 .. 10) {
  $hash{$n} = 1;
  $n *= 1000;
}

然后我们查询它，寻找是十的幂的键。当然，将整数乘以十最简单的方法是添加一个零，因此写成这样是可以的

my $m = '1';

for (1 .. 100) {
  print $m, "\n" if $hash{$m};
  $m .= 0;
}

它的输出结果为

1000
1000000
1000000000
1000000000000
1000000000000000
1000000000000000000

我们输入了十个元素，但只显示了六个。发生了什么？让我们来看看哈希表中的内容。
use Data::Dump;
dd \%hash;

这将输出

{
  "1000"                => 1,
  "1000000"             => 1,
  "1000000000"          => 1,
  "1000000000000"       => 1,
  "1000000000000000"    => 1,
  "1000000000000000000" => 1,
  "1e+021"              => 1,
  "1e+024"              => 1,
  "1e+027"              => 1,
  "1e+030"              => 1,
}

因此哈希表并不使用我们想象中的键。它会以一种字符串化数字的方式来哈希，模仿它是愚蠢的。

举一个稍微更实际的例子，假设我们有一些圆形，并且想按面积将它们收集到集合中。显然可以使用面积作为哈希键，就像这个程序创建了 100,000 个随机整数直径不超过 1800 万的圆形。

use strict;
use warnings;
use 5.010;

package Circle;

use Math::Trig 'pi';

sub new {
  my $class = shift;
  my $self = { radius => shift };
  bless $self, $class;
}

sub area {
  my $self = shift;
  my $radius = $self->{radius};
  pi * $radius * $radius;
}



package main;

my %circles;

for (1 .. 100_000) {
   my $circle = Circle->new(int rand 18_000_000);
   push @{ $circles{$circle->area} }, $circle;
}

现在让我们看看有多少个哈希键使用科学计数法。
say scalar grep /e/, keys %circles;

这段代码（当然是随机的）

861

所以，如果我们将数字作为哈希索引指定，实际上并没有一种简洁的方法来确定 Perl 将使用哪个字符串。

1
在Perl中，@array是一个值的有序列表($v1, $v2, ...)，可以通过整数（正数和负数）访问，而%hash是一个无序的'key => value'对列表(k1 => $v1, k2 => $v2, ...)，可以通过字符串访问。
CPAN上有一些实现有序哈希的模块，例如：Hash::Ordered和Tie::IxHash。
当您拥有有序的“项”时，可能希望使用数组，特别是这些项数量众多，使用%hash并对键和/或值进行排序会效率低下。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接