Scala混沌哈希与Java本机哈希的比较

Question

Scala混沌哈希与Java本机哈希的比较

javascalahash

4

我正在学习Scala，在case类的哈希码部分有些困惑。

就我所见，case类提供了toString、equals和hashCode的自动生成功能。

在Java中，传统的智慧是Java哈希码使用本地实现。

但在Scala中，它使用Murmur哈希（MurmurHash3算法）

我的问题：

1）Java具有本地哈希码，因为哈希码是机器相关的，但如果Scala使用Murmur哈希，则如何实现机器无关性？

2）Scala除了case类还有常规类，通常类也使用Murmur哈希吗？

3）如果Murmur哈希真的是Java本地实现之后最快的实现，那么为什么Java仍然使用本地实现？

- Greedy Coder

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rex Kerr · Accepted Answer

MurmurHash是一种快速高质量的哈希函数。Scala为集合、元组、case类和大多数其他库提供的对象（连同equals）提供自动hashCode，由于许多这些东西被用于哈希映射中，拥有一个好的默认哈希函数非常重要。MurmurHash可以提供这个功能。据我所知，即使有时候Java哈希是使用本地代码实现的，但它们也不依赖于机器。重要的是算法在任意机器上都是相同的，Scala的实现完全是字节码，而Java的实现则是因为所有不在字节码中的内容（我没有检查所有内容！）都是仔细处理的。

（至少对于扩展java.util.AbstractList的任何东西，传统的智慧是错误的。它根本不是原生实现，只是循环迭代器并调用其中每个元素的hashCode方法。但JVM擅长这种循环和计算，为什么你想让它成为本地实现？）

在Scala中，普通类没有覆盖hashCode，因此它们不使用MurmurHash。然而，大多数非case类的库类确实使用MurmurHash——例如所有有序集合。（不能在集合中使用依赖于顺序的MurmurHash，因为顺序无关紧要。）

尽管MurmurHash非常快，但它并不是可能的最快哈希函数。Java通常使用类似于x（n）* 31 + x（n + 1）的算法进行哈希，这更快。不幸的是，这也是一种相当糟糕的哈希函数。很容易发生冲突。此外，MurmurHash在低开销和整体速度快速之间有一个不错的平衡，但其他哈希函数（例如XxHash或CityHash）对于大型对象可能会更快，代价是稍微多一点的启动开销。因此，并非每个人都应该全部使用MurmurHash。

然而，MurmurHash被选择用于Scala，主要是因为相对简单的典型Java风格哈希算法存在已知缺陷，而且通常情况下使用MurmurHash效果良好。那么为什么Java没有采用它呢？可能只是因为Java作为一种更成熟的语言，变化比Scala慢，还没有人着手实现；或者关心此事的人已经在使用自己的定制哈希解决方案了。