在使用R之前，我使用了相当多的Perl。在Perl中，我经常使用散列，并且在Perl中查找散列通常被认为是快速的。
例如，以下代码将填充最多10000个键/值对的散列，其中键是随机字母，值是随机整数。然后，它在该哈希中执行10000次随机查找。
#!/usr/bin/perl -w
use strict;
my @letters = ('a'..'z');
print @letters . "\n";
my %testHash;
for(my $i = 0; $i < 10000; $i++) {
my $r1 = int(rand(26));
my $r2 = int(rand(26));
my $r3 = int(rand(26));
my $key = $letters[$r1] . $letters[$r2] . $letters[$r3];
my $value = int(rand(1000));
$testHash{$key} = $value;
}
my @keyArray = keys(%testHash);
my $keyLen = scalar @keyArray;
for(my $j = 0; $j < 10000; $j++) {
my $key = $keyArray[int(rand($keyLen))];
my $lookupValue = $testHash{$key};
print "key " . $key . " Lookup $lookupValue \n";
}
现在越来越多，我想在R中有一个类似哈希的数据结构。以下是等效的R代码：
testHash <- list()
for(i in 1:10000) {
key.tmp = paste(letters[floor(26*runif(3))],sep="")
key <- capture.output(cat(key.tmp,sep=""))
value <- floor(1000*runif(1))
testHash[[key]] <- value
}
keyArray <- attributes(testHash)$names
keyLen = length(keyArray);
for(j in 1:10000) {
key <- keyArray[floor(keyLen*runif(1))]
lookupValue = testHash[[key]]
print(paste("key",key,"Lookup",lookupValue))
}
代码似乎在做同等的事情。然而，Perl一个快得多：
>time ./perlHashTest.pl real 0m4.346s user **0m0.110s** sys 0m0.100s
与R比较：
time R CMD BATCH RHashTest.R real 0m8.210s user **0m7.630s** sys 0m0.200s
什么解释了差异？在R列表查找只是不好吗？
增加到100,000列表长度和100,000次查找只夸大了差异？是否有更好的替代R的哈希数据结构比本机list()？
解决方法
基本原因是具有命名元素的R列表不进行哈希。哈希查找是O(1)，因为在插入过程中，使用散列函数将密钥转换为整数，然后将值放在空间的hash(key)％num_spots数组num_spots long(这是一个大的简化，避免处理冲突的复杂性)。查找键只需要哈希键来找到值的位置(这是O(1)，与O(n)数组查找)。 R列表使用名称查找，它们是O(n)。
正如Dirk所说，使用哈希包。这是一个巨大的限制是，它使用环境(哈希)和覆盖的方法来模仿哈希表。但是一个环境不能包含另一个环境，所以你不能使用哈希函数嵌套哈希。
一开始我在C / R中实现了一个可以嵌套的纯哈希表数据结构，但是在我处理其他事情时，它继续我的项目。这将是很高兴有虽然:-)