Hi all，

最近在比较各个语言中哈希表实现的性能。比如python中的dict，C++中的 
unordered_map，go中的map，最后，让我最不解的：java中的HashMap。

知道列表上牛人多，也许能帮我解答一下，或者提供什么思路。

目前的做法是，对使用每个语言，利用其中的哈希表实现，写一个 
benchmark，benchmark要做的事情很简单：插入N个数到哈希表中，将该数字的10 
进制表示的字符串作为key，前面补零以保证没个key长度都为9个字符（保证计算 
哈希值的时候时间一致）。哈希表的key就是这些十进制表示的字符串，哈希表的 
value，就是对应的数字值。最后，随机取出每个key和对应值（保证cache miss 
rate在不同大小的情况下维持在一定水平），计算取出全部内容所需时间，除以 
N，得到平均每次取操作所花费的时间。（前面的插入，打乱顺序等操作均不计入 
时间）。

多说无益，上代码。这里是java的代码：http://pastebin.com/RmnsYYdC

说说结果吧。先看看C++的运行结果（代码我就不给了，很简单的东西，想必大伙 
都能自己写）：

Unordered Map Random Access. N = 10. 0.4us/op. checksum: 45
Unordered Map Random Access. N = 100. 0.17us/op. checksum: 4950
Unordered Map Random Access. N = 1000. 0.168us/op. checksum: 499500
Unordered Map Random Access. N = 10000. 0.2667us/op. checksum: 49995000
Unordered Map Random Access. N = 100000. 0.58731us/op. checksum: 704982704
Unordered Map Random Access. N = 1000000. 0.688527us/op. checksum: 
1783293664

大概分析两句：当N比较小的时候（10，100），overhead比较大，cache miss的主 
要来源是第一次需要数据的时候把内存载入cache所花的时间（compulsory 
miss）。随着N加大（1000），compulsory miss减少。但随着N继续增加，cache 
miss的主要来源是conflict miss和capacity miss，由此导致操作继续变慢。

这套解释我很信服，使用其他语言也是类似结果（先比较大，慢慢减少，然后再变 
大）。但是Java的HashMap结果却出乎意料：

HashMap Random Access. N = 10: 0.862200 us/op. checksum: 45
HashMap Random Access. N = 100: 0.312150 us/op. checksum: 4950
HashMap Random Access. N = 1000: 0.303698 us/op. checksum: 499500
HashMap Random Access. N = 10000: 0.486622 us/op. checksum: 49995000
HashMap Random Access. N = 100000: 0.225230 us/op. checksum: 704982704
HashMap Random Access. N = 1000000: 0.165556 us/op. checksum: 1783293664

检查checksum，发现代码没错（实际我打印了每个循环，发现也的确没错，而且访 
问也的确足够随机）。但是问题来了：平均访问时间随着N增加，先比较大（正 
常），再减小（正常），再变大（正常），然后，然后它又减小了！而且最后竟然 
减小到0.17us/op。

能够解释其中原因的，我觉得就是JVM的prefetch技术。因为我把访问哈希表的顺 
序经过随机打乱，存在了数组seq中，然后通过循环对数组每个元素的访问，进而 
访问哈希表中的每个元素。而随着N增加，JVM具备了足够知识，在我需要某个元素 
之前，通过察看seq的内容，提前把哈希表里的东西给载入到了cache中，提高了缓 
存命中率。

这个说法我觉得倒是行得通。我假设这个为真，为了避免JVM学习到循环下一次的 
行为，我决定直接在循环内部插入随机数生成的代码。换句话说，只有在循环执行 
到了那一步，才能知道哈希表中哪个元素该被访问（假设随机数生成器能生成质量 
比较高的伪随机数），以下是代码：

http://pastebin.com/h7Kk3kGS

可以看到，循环内部有随机数产生的代码。但是诡异的行为继续发生了：

HashMap Random Access. N = 10: 1.296800 us/op. checksum: 34
HashMap Random Access. N = 100: 0.700910 us/op. checksum: 4899
HashMap Random Access. N = 1000: 0.655325 us/op. checksum: 490286
HashMap Random Access. N = 10000: 0.693663 us/op. checksum: 50013157
HashMap Random Access. N = 100000: 0.320951 us/op. checksum: 684834485
HashMap Random Access. N = 1000000: 0.321542 us/op. checksum: -2073618973

这一次，checksum不正确是很可能的，因为这样随机的访问并不能保证每个元素被 
访问且只被访问一次。但是怎么每个循环运行的时间依然在最后减少了呢？

下一个推论：我使用的是伪随机数发生器，说到头，只要JVM愿意，它还是可以知 
道下面几个循环可能会访问哪些内容的。

如果这个推论继续成立，那么我只要找到一个真随机数发生器，就可以让java的运 
行时间和其他语言的运行时间一样，先降低，再增长，最后继续增长。

不过java的标准库似乎没有真随机数发生器。不知道哪位朋友能帮我看看。如果哪 
位朋友能够证实我前面的推论是正确的，那么也剩了我找真随机数发生器的时间了。

多谢了！
-Monnand