相关疑难解决方法(0)

我注意到在Java 6的String源代码中,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 …

有时可以使用关联性来消除数据依赖性,我很好奇它可以提供多少帮助.我很惊讶地发现,通过手动展开一个简单的循环,我几乎可以获得4的加速因子,无论是在Java(build 1.7.0_51-b13)还是在C(gcc 4.4.3)中.

所以要么我做了一些非常愚蠢的事情,要么编译器忽略了一个强大的工具.我开始了

int a = 0;
for (int i=0; i<N; ++i) a = M1 * a + t[i];

它计算接近String.hashCode()(设置M1=31和使用a char[])的东西.计算非常简单,t.length=1000我的i5-2400 @ 3.10GHz(Java和C)都需要大约1.2微秒.

观察每两个步骤a乘以M2 = M1*M1并添加一些东西.这导致了这段代码

int a = 0;
for (int i=0; i<N; i+=2) {
    a = M2 * a + (M1 * t[i] + t[i+1]); // <-- note the parentheses!
}
if (i < len) a = M1 * a + t[i]; …