Perl 中是否可以保留哈希表的大小？

Question

我正在 Perl 中创建一个大小未知的哈希表。

哈希表将字符串映射到数组的引用。

我的应用程序的主循环在每次迭代中向哈希表添加 5-10 个元素。当哈希表填满时，速度开始急剧减慢。根据观察，当哈希表中有大约 50k 个键时，添加键的速度会减慢 20 倍。

我假设哈希表已满，并且正在发生冲突。我想“保留”哈希表的大小，但我不确定如何保留。

---

有问题的哈希是 hNgramsToWord。

对于每个单词，该单词的 1-len-gram 被添加为键，并引用包含该 ngram 的单词数组。

例如：

AddToNgramHash("Hello");

[h, e, l, l, o, he, el, ll, lo, hel, llo, hell, ello, hello ] 全部添加为键，映射到“hello”

sub AddToNgramHash($) {
    my $word = shift;
    my @aNgrams = MakeNgrams($word);
    foreach my $ngram (@aNgrams) {
       my @aWords;
       if(defined($hNgramsToWord{$ngram})) {
          @aWords = @{$hNgramsToWord{$ngram}};
       }
       push (@aWords, $word);
       $hNgramsToWord{$ngram} = \@aWords;
    }
    return scalar keys %hNgramsToWord;
}

sub MakeNgrams($) {
    my $word = shift;
    my $len = length($word);
    my @aNgrams;
    for(1..$len) {
       my $ngs = $_;
          for(0..$len-$ngs) {
           my $ngram = substr($word, $_, $ngs);
           push (@aNgrams, $ngram);
       }
    }
    return @aNgrams;
}

Answer 1

您可以设置哈希的存储桶数量，如下所示：

keys(%hash) = 128;

该数字将四舍五入为 2 的幂。

也就是说，您看到的速度减慢不太可能是由于过多的哈希冲突造成的，因为 Perl 会根据需要动态扩展存储桶的数量。从 5.8.2 开始，它甚至可以检测导致给定存储桶被过度使用的病态数据，并为该哈希重新配置哈希函数。

显示您的代码，我们很可能能够帮助找到真正的问题。

大量哈希键的演示（不要让它继续下去，直到内存耗尽......）：

use strict;
use warnings;
my $start = time();
my %hash;
$SIG{ALRM} = sub {
    alarm 1;
    printf(
        "%.0f keys/s; %d keys, %s buckets used\n",
        keys(%hash) / (time() - $start),
        scalar(keys(%hash)),
        scalar(%hash)
    );
};
alarm 1;
$hash{rand()}++ while 1;

一旦有很多键，当需要扩展存储桶数量时，您会注意到明显的减速，但仍然保持着相当均匀的速度。

查看您的代码，加载的单词越多，每个单词需要做的工作就越多。

您可以通过将以下内容更改

   my @aWords;
   if(defined($hNgramsToWord{$ngram})) {
      @aWords = @{$hNgramsToWord{$ngram}};
   }
   push (@aWords, $word);
   $hNgramsToWord{$ngram} = \@aWords;

为：

   push @{ $hNgramsToWord{$ngram} }, $word;

无需复制数组两次来修复它。无需检查 ngram 是否已有条目 - 它会为您自动生成数组引用。