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

Question

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

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

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

Answer 1

Perl 5中的关联数组使用散列表实现,散列表具有分摊的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;

Answer 2

perl哈希是一个哈希表,因此它已经有O(1)插入和查找.