perl - 是否可以以具有 `O(log(n))` 查找和插入的方式使用 Perl 哈希？

Question

是否可以以具有 O(log(n)) 的方式使用 Perl 哈希？查找和插入？

默认情况下，我假设查找是 O(n)因为它由一个未排序的列表表示。

我知道我可以创建一个数据结构来满足这个(即树等)但是，如果它是内置的并且可以用作普通哈希(即带有 %)会更好

Answer 1

Perl 5 中的关联数组是用 hash tables 实现的已摊销 O(1)(即恒定时间)插入和查找。这就是为什么我们倾向于称它们为哈希而不是关联数组。

很难找到说明 Perl 5 使用哈希表来实现关联数组的文档(除了我们将关联数组称为“哈希”这一事实之外)，但至少在 perldoc perlfaq4 中有这一点。

What happens if I add or remove keys from a hash while iterating over it?
   (contributed by brian d foy)

   The easy answer is "Don't do that!"

   If you iterate through the hash with each(), you can delete the key
   most recently returned without worrying about it.  If you delete or add
   other keys, the iterator may skip or double up on them since perl may
   rearrange the hash table.  See the entry for "each()" in perlfunc.

来自 perldoc perldata 的更好报价:

   If you evaluate a hash in scalar context, it returns false if the hash
   is empty.  If there are any key/value pairs, it returns true; more
   precisely, the value returned is a string consisting of the number of
   used buckets and the number of allocated buckets, separated by a slash.
   This is pretty much useful only to find out whether Perl's internal
   hashing algorithm is performing poorly on your data set.  For example,
   you stick 10,000 things in a hash, but evaluating %HASH in scalar
   context reveals "1/16", which means only one out of sixteen buckets has
   been touched, and presumably contains all 10,000 of your items.  This
   isn't supposed to happen.  If a tied hash is evaluated in scalar
   context, a fatal error will result, since this bucket usage information
   is currently not available for tied hashes.

当然，O(1) 只是理论性能。在现实世界中，我们没有完美的散列函数，所以当它们变大时，散列确实会变慢，并且有一些退化的情况会将散列变成 O(n)，但是 Perl 尽力防止这种情况发生。这是 Perl 散列的基准，具有 10、100、1,000、10,000、100,000 个键:

Perl version 5.012000
               Rate 10^5 keys 10^4 keys 10^3 keys 10^2 keys 10^1 keys
10^5 keys 5688029/s        --       -1%       -4%       -7%      -12%
10^4 keys 5748771/s        1%        --       -3%       -6%      -11%
10^3 keys 5899429/s        4%        3%        --       -4%       -9%
10^2 keys 6116692/s        8%        6%        4%        --       -6%
10^1 keys 6487133/s       14%       13%       10%        6%        --

这是基准代码:

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark;

print "Perl version $]\n";

my %subs;
for my $n (1 .. 5) {
    my $m = 10 ** $n;
    keys(my %h) = $m; #preallocated the hash so it doesn't have to keep growing
    my $k = "a";
    %h = ( map { $k++ => 1 } 1 .. $m );
    $subs{"10^$n keys"} = sub {
        return @h{"a", $k};
    }
};

Benchmark::cmpthese -1, \%subs;