https://www.bilibili.com/video/BV1RTiceCEr6/
大家好，最近我的一个同事和我反馈说，Rust中的HashMap比Java标准库中的HashMap性能要差很多。并且他还给我提供了一份代码，同样的逻辑分别用Java和Rust写了一遍，测试多次后都得出结论说Java中的HashMap性能会好很多。我觉得很有意思，然后把代码拿过来测试一下。我在我自己的工作机器上和家用机器上都进行了多次测试，最终的结论确实和他反馈的保持一致。随后我进行了一些分析，今天给大家来简单分享一下。
我们就来看一下这份代码。首先我们看一下Rust版本，这个代码比较简单。首先我们初始化了一个100万个元素的HashMap，然后它的key和value都是i32类型。然后我们做了100次测试，每次测试去for循环get 1,000,000次，也就是将这个HashMap中的所有元素都访问一遍。每次执行我们都会统计一下这个查询100万次的耗时，最后我们会输出最后五次的结果。
这里我们测试了100次，但是我们只输出最后五次的结果。主要是这份代码主要是为了和参照组的Java保持公平性。原因是Java它是有一个JIT优化的，所以说同样的代码，它对于Java这种语言的话，它前面的性能是会比较差的。如果直接跑五次，然后得出结论的话，对Java来说是非常不公平的。因此我们先跑95次做一次预热。
我们看一下Java版本，其实逻辑是一模一样的。也是初始化一个HashMap，然后往里面添加了100万行元素，然后我们执行100次，也是输出最后5次的结果。逻辑上基本一致。
这是我在我自己的机器上得出的结果。首先Rust每次查询100万次耗时都在20多毫秒，而对照组的Java他们同样执行相同的逻辑，每次的耗时大概在7到13ms。虽然说有些波动，但是可以明显看得到，比Rust的版本的话性能是好很多的。
说实话这个结果我挺出乎我意料的。在我印象中，Java是通过虚拟机去解释执行JVM平台定义的字节码。虽然说他有JIT优化，但是Rust的性能也不至于比Java低这么多，毕竟Rust它是直接编译成当前平台的机器码去执行的。
为此，我就去对比研究了一下Java和Rust中的HashMap的实现。最终定位到的原因是二者的哈希算法的差异。Rust中标准库的HashMap，它采用的是一个叫SipHash的哈希算法，它是一种基于安全考虑的选择。SipHash可以有效抵挡哈希碰撞类的DoS攻击。DoS攻击其实就是拒绝服务攻击，而哈希碰撞类的DoS攻击指的是攻击者精心构造一些数据，这些数据经过哈希函数输出的结果是同样的，因此当它们插入在哈希表中，就会产生大量的碰撞，从而会使得哈希表退化成一个性能极低的数据结构。
比如说一般的哈希表可能会采用链表来解决哈希冲突。如果你的HashMap是用来接收前端的输入，攻击者能利用这个特点精心伪造一些哈希值一样的数据传入后台，那么就会导致这些哈希表退化成性能极低的数据结构，就变成一个完全变成一个链表。这种情况下可能会导致大量的CPU消耗，严重导致系统无法及时响应请求。
Rust中考虑到这一点，采用的是一个叫做SipHash的算法。它的性能在整形和长字符串的场景下，和其他的哈希算法相比会有一定的劣势，但是它是比较安全的。
下面这张图是我从Rust的标准库中截图出来的。RandomState这个结构体它是HashMap和HashSet的模板参数的第三个参数。SipHash的话它是依赖于种子，在种子不同的情况下，同一个key它的哈希值都是不一样的。因此用户想要去精心构造那种哈希值相同的数据是非常有难度的。种子的话它采用的是两个种子，k0和k1。它是一个thread_local初始化的，每一个线程有一个独立的种子变量。而k1的话是在当前线程生命周期中保持不变的，而k0的话每次调用一次则会加一。因此在同一个线程中new出来的两个HashMap，它们的种子也是有不同的。
在一些Rust的开源项目中，在不需要考虑DoS攻击的场合中，我们往往会采用其他的一些更高效的哈希算法来替代默认的标准库实现。比如说下面这个代码，我是从TiKV中截图过来的。TiKV是一个Rust编写的分布式key-value数据库，他们重新定义了HashMap和HashSet。而这个HashMap和HashSet只是标准库HashMap和HashSet的一个别名，但唯一的区别就是他们的第三个参数采用了FxHash去替换了默认的RandomState。
我这边参考了一下TiKV的实现，把我们之前的那种测试代码换成了FxHash，重新跑了一轮测试。最终得到的效果如下，可以看到Rust的版本在使用了FxHash后，每组的耗时明显只有上一组的耗时的一半左右，这是一个很大的改进。但是和对照组的Java来比，明显它的这个数据还是偏高。
为了解决这个问题，我还是去继续分析了一下Java的实现。我这边初步怀疑Java版本的数据比Rust版本数据好看的原因是因为它的哈希算法的问题。我们的key也是一个Integer，它也就是个整形。而Java中哈希函数它是和key绑定的，而不是和容器绑定的。它的哈希函数实际上就是每个类自带的一个叫hashCode的函数。
这里它的hashCode的实现，其实调用了自身的一个static函数，也就是这个hashCode。看到它直接返回了本身。这个很好理解，哈希函数的逻辑本身就是提供一个输入，然后去输出一个对应的哈希值。而整形的话它本身就是一个数值，可以当做哈希值用，因此它就直接返回了自己。它的哈希函数是没有任何开销的。但是我们Rust的版本FxHash的话，它求解的话是需要一定的运算步骤的。我怀疑开销在这里。
我这边找了一个叫做NoHash的库，它的逻辑和Java的版本是一样的。当它的key是这种i32或者i64之类的这种整形数字的话，它就直接将自己作为哈希值返回，就不需要有额外的哈希计算的开销。我把同样的case做了一次重测，最后得到的结果是，Rust使用了类似于Java这种逻辑的情况下，它的平均耗时100次查询耗时大概在1毫秒左右。可以看到这组数据是比较符合我们的预期的。
这里的话是我今天的分享。也其中也包含了一些本人的猜测。如果大家有什么问题或者说发现了错误，欢迎在评论区里面指正。谢谢大家。
原文链接: https://dashen.tech/2018/08/06/Rust杂谈-HashMap性能比不上Java/
版权声明: 转载请注明出处.