为什么 String 的 hashCode() 不缓存 0?

2022-08-31 13:02:28

我注意到在 String 的 Java 6 源代码中,hashCode 只缓存 0 以外的值。以下代码段显示了性能的差异:

public class Main{
   static void test(String s) {
      long start = System.currentTimeMillis();
      for (int i = 0; i < 10000000; i++) {
         s.hashCode();
      }
      System.out.format("Took %d ms.%n", System.currentTimeMillis() - start);
   }
   public static void main(String[] args) {
      String z = "Allocator redistricts; strict allocator redistricts strictly.";
      test(z);
      test(z.toUpperCase());
   }
}

在 ideone.com 中运行此命令可得到以下输出:

Took 1470 ms.
Took 58 ms.

所以我的问题是:

  • 为什么 String 的 hashCode() 不缓存 0?
  • Java 字符串哈希为 0 的概率是多少?
  • 避免每次为哈希为 0 的字符串重新计算哈希值会降低性能的最佳方法是什么?
  • 这是缓存值的最佳做法方法吗?(即缓存除一个之外的所有内容?

为了您的娱乐,这里的每一行都是一个哈希为0的字符串:

pollinating sandboxes
amusement & hemophilias
schoolworks = perversive
electrolysissweeteners.net
constitutionalunstableness.net
grinnerslaphappier.org
BLEACHINGFEMININELY.NET
WWW.BUMRACEGOERS.ORG
WWW.RACCOONPRUDENTIALS.NET
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.

答案 1

你什么都不担心。以下是思考这个问题的方法。

假设您有一个应用程序,它除了全年都在散列字符串之外什么都不做。假设它需要一千个字符串,全部在内存中,以轮循机制方式重复调用hashCode(),一百万次通过,然后获取另外一千个新字符串并再次执行。

假设字符串的哈希代码为零的可能性实际上远大于1/2 ^ 32。我敢肯定它比1/2^ 32大一,但让我们说它比这糟糕得多,比如1/2^ 16(平方根!现在这要糟糕得多!)。

在这种情况下,Oracle工程师改进这些字符串的哈希代码的缓存方式比活着的任何其他人都受益更多。所以你写信给他们,要求他们修复它。他们发挥自己的魔力,这样每当s.hashCode()为零时,它就会立即返回(即使是第一次!100%的改进!假设他们这样做不会降低任何其他情况的性能。

万岁!现在你的应用是...我看看。。。速度提高 0.0015%!

过去需要一整天的时间,现在只需要23小时57分48秒!

请记住,我们设置的场景是为了提供怀疑的每一个可能的好处,往往达到荒谬的程度。

这对你来说值得吗?

编辑:自从几个小时前发布这个以来,我已经让我的一个处理器疯狂地寻找零哈希代码的两个单词短语。到目前为止,它已经提出了:bequirtle zorillo,chronogrammic schtoff,contusive cloisterlike,creashaks organzine,drumwood boulderhead,电分析可锻炼,以及最不可理解的。这大约有2^ 35种可能性,因此对于完美分布,我们预计只看到8种。显然,当它完成时,我们将有几次那么多,但不会奇怪地更多。更重要的是,我现在想出了一些有趣的乐队名称/专辑名称!没有公平的偷窃!


答案 2

它使用0来表示“我还没有计算出哈希码”。另一种方法是使用单独的布尔标志,这将占用更多内存。(或者根本不缓存哈希码,当然。

我不希望很多字符串哈希为0;可以说,哈希例程故意避免0是有意义的(例如,将0的哈希转换为1,并缓存它)。这将增加冲突,但避免重新哈希。不过,现在这样做为时已晚,因为字符串哈希码算法已明确记录。

至于这通常是否是一个好主意:它肯定是一种有效的缓存机制,并且可能(请参阅编辑)通过更改来避免重新哈希值(最终以哈希值为0)可能会更好。就我个人而言,我有兴趣看到导致Sun认为这首先值得做的数据 - 它为曾经创建的每个字符串占用额外的4个字节,无论它经常被或很少被散列,唯一的好处是对于多次散列的字符串。

编辑:正如KevinB在其他地方的评论中指出的那样,上面的“避免0”建议很可能有净成本,因为它有助于非常罕见的情况,但需要对每个哈希计算进行额外的比较。