为什么String的hashCode（）缓存0？

Question

我在弦乐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()); 
    } 
} 

Running this in ideone.com给出以下输出：

Took 1470 ms. 
Took 58 ms. 

所以我的问题是：

• 为什么不串的hashCode（）方法缓存0？
• Java字符串散列为0的概率是多少？
• 什么是避免每次散列值为0的字符串重新计算散列值的性能损失的最佳方法？
• 这是缓存值的最佳实践方式吗？ （？IE缓存所有除一个）

---

为了您的娱乐，在这里每一行是一个字符串散列为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. 

Answer 1

你只是在担心什么。这是思考这个问题的一种方法。

假设你有一个应用程序除了散列字符串外，整年都不做任何事情。假设它需要一千个字符串，全部在内存中，以循环方式重复调用hashCode（），一百万遍，然后再获取另外一千个新字符串并再次执行。

并且假设字符串散列码为零的可能性实际上远大于1/2^32。我相信它是有点大于1/2^32，但让我们说它比这更糟糕，比如1/2^16（平方根！现在更糟！）。

在这种情况下，您将从Oracle的工程师中获益更多，从而改善这些字符串的哈希码的缓存方式。所以你写信给他们，并要求他们修复它。他们使用魔法，只要s.hashCode（）为零，它立刻返回（甚至是第一次！100％的改进！）。假设他们在不降低任何其他情况下的性能的情况下这样做。

Hooray！现在你的应用程序是...让我们看看...快0.0015％！

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

并且记住，我们设定了一个场景，让每一个可能的好处都带给怀疑，通常是荒谬的程度。

这看起来是否值得吗？

编辑：自从几个小时前发布这个版本以来，我让我的一个处理器疯狂地寻找具有零散列码的双字短语。到目前为止，它已经提出：bequirtle zorillo，chronogrammic schtoff，contusive cloisterlike，creashaks organzine，drumwood boulderhead，电分析可锻炼，并且非常不易折叠。这大约有2^35种可能性，所以我们期望只能看到8种完美的分布。很明显，当它完成的时候，我们会有很多次，但不会奇怪的多。更重要的是，我现在想出了一些有趣的乐队名称/专辑名称！没有公平的窃取！

Answer 2

它使用0，表示“我没有工作out hashcode yet“。另一种方法是使用单独的布尔标志，这会花费更多的内存。 （或者当然不会缓存哈希码。）

我不希望很多字符串散列为0;可以说散列例程有意避免0（例如，将0的散列翻译为1并缓存）是有意义的。这会增加碰撞，但避免重蹈覆辙。现在要做到这一点已经太迟了，因为String hashCode算法是明确记录的。

至于这是否是在一般一个好主意：这是一个绝对高效的缓存机制，威力（见编辑）甚至更好的改变，以避免换汤不换药它结了0个人的哈希值我希望看到Sun首先相信这值得做的数据 - 对于创建的每个字符串，它都占用了额外的4个字节，但是经常或很少被散列，并且唯一的好处是对于字符串不止一次散列。

编辑：由于KevinB在评论所指出的其他地方一样，“避0”的建议上面可能有一个净成本，因为它有助于一个非常罕见情况，但需要每哈希额外的比较计算。

Answer 3

由于实现将缓存值0解释为“缓存值尚未初始化”，因此不缓存0。另一种方法是使用java.lang.Integer，其中null表示该值尚未被缓存。但是，这意味着额外的存储开销。

关于字符串的散列码的概率被计算为0我想说的概率是相当低的，可在下列情况下发生：

• 字符串为空（虽然每次重新计算这个哈希码实际上是O（1））。
• 发生溢出，由此最终计算出的散列码为0（e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0）。
• 字符串中包含唯一的Unicode字符0非常不可能，因为这是没有意义除了在“纸带世界”的控制字符（！）：

从Wikipedia：

代码0（ASCII代码名称NUL）是一个 特殊情况。在纸带中，没有孔时就是 。这是 方便把这个作为填充 字符没有意义，否则。

Answer 4

• 为什么不串的hashCode（）方法缓存0？

将零值保留为意思是“散列码未被高速缓存”。

• Java字符串散列为0的概率是多少？

据的Javadoc，对于字符串的哈希码的计算公式为：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] 

使用int算术，其中s[i]是字符串的第i个字符和n是字符串的长度。 （作为特殊情况，空字符串的散列被定义为零）。

我的直觉是上面的散列码函数给出了字符串散列值在int值范围内的统一散布。均匀分布意味着随机生成的字符串散列为零的概率在2^32中为1。

• 什么，以避免散列为0的字符串每次重新计算哈希值的性能损失的最好方法？

最好的策略是忽略这个问题。如果你反复散列相同的字符串值，那么你的算法有一些奇怪的地方。

• 这是缓存值的最佳实践方法是什么？ （即缓存除一个以外的所有内容？）

这是一个空间与时间的权衡。据我所知，其他的选择：

• 添加cached标志，每个String对象，使每一个Java的String采取额外的字。

• 使用hash成员的最高位作为缓存标志。这样你可以缓存所有的散列值，但是你只有尽可能多的String散列值的一半。

• 请勿在所有字符串上缓存哈希码。

我认为Java设计师已经对Strings做出了正确的呼叫，并且我确信他们已经做了大量的分析，证实了他们的决定的正确性。不过，它不是跟着说，这个会总是是处理缓存的最好方法。 （注意，有两个“常见”字符串值散列为零;空字符串和只包含NUL字符的字符串）然而，计算这些值的哈希码的代价与计算典型字符串值的散列码的代价）。

Answer 5

我认为有一件重要的事情，至今还没有其他答案：零值存在，以便hashCode-缓存机制在多线程环境中稳健工作。

如果你有两个变量，像cachedHashCode本身和一个isHashCodeCalculated布尔值来指示是否计算了cachedHashCode，那么你需要线程同步才能在多线程环境中工作。同步会对性能造成影响，特别是因为字符串在多个线程中非常常用。

我的Java存储模型的理解是一个有点粗略，但这里的大概是怎么回事：

1. 当多个线程访问变量（如缓存的hashCode），也不能保证每个线程都看最新的价值。如果变量从零开始，那么A更新它（将其设置为非零值），然后线程B在之后不久读取它，线程B仍然可以看到零值。

2. 从多线程（无同步）访问共享值还有另一个问题 - 您最终可能会尝试使用仅部分初始化的对象（构建对象不是原子进程）。多线程读取和写入64位基元（如long和double）不一定是原子，所以如果两个线程试图读取和更改long或double的值，则一个线程最终会看到奇怪的和部分设置的东西。或者无论如何。如果您尝试同时使用两个变量，例如cachedHashCode和isHashCodeCalculated，则会出现类似的问题 - 线程可以轻松前来查看其中一个变量的最新版本，但可以看到其中一个变量的最新版本。

3. 解决这些多线程问题的常用方法是使用同步。例如，你可以将所有对缓存hashCode的访问放在一个同步块中，或者你可以使用volatile关键字（尽管要小心，因为语义有点混乱）。

4. 但是，同步会降低速度。对于像字符串hashCode这样的错误想法。字符串通常用作HashMaps中的键，所以您需要hashCode方法才能正常运行，包括在多线程环境中。

5. 32位或更少的Java原语（如int）是特殊的。与长时间（64位值）不同，您可以确定永远不会读取int的部分初始化值（32位）。当你读取一个没有同步的int时，你不能确定你会得到最新的设置值，但是你可以确定你得到的值是你的线程明确设置了某个值的值，或者另一个线程。

java.lang.String中的hashCode缓存机制被设置为依赖于上面的第5点。您可以通过查看java.lang.String.hashCode（）的源代码来更好地理解它。基本上，多线程一次调用hashCode，hashCode可能最终会被多次计算（如果计算值为零或者多个线程同时调用hashCode并且都看到一个零缓存值），但您可以确定hashCode （）将始终返回相同的值。所以它非常强大，而且性能也很好（因为没有同步在多线程环境中充当瓶颈）。就像我说的，我对Java内存模型的理解有点粗略，但我确信我已经掌握了上述权利的要点。最终，这是一个非常聪明的习惯用于缓存hashCode而不需要同步的开销。

Answer 6

这原来是一个很好的问题，与security vulnerability有关。

“当散列字符串，Java也缓存中的散列属性 散列值，但仅当结果是不同于零。 因此，目标零值是特别令人感兴趣的攻击者，因为它防止缓存 并强制重新哈希。“

Answer 7

好的人，它保持0，因为如果它是零长度，它将最终为零反正。

并且不需要太长时间才能发现len是零，所以hashcode必须是。

因此，为您的代码reviewz！这是在所有它的Java 8荣耀：

public int hashCode() { 
     int h = hash; 
     if (h == 0 && value.length > 0) { 
      char val[] = value; 

      for (int i = 0; i < value.length; i++) { 
       h = 31 * h + val[i]; 
      } 
      hash = h; 
     } 
     return h; 
    } 

正如你所看到的，这将始终返回快速零，如果字符串为空：

if (h == 0 && value.length > 0) ... 

Answer 8

的“避免0”的建议似乎是恰当的作为最佳实践推荐，因为它有助于解决真正的问题（在可供攻击者提供的可构建案例中严重意外的性能下降），因为写入之前的分支操作的成本微不足道。如果唯一的东西进入到特殊调整值的集合散列中，那么可以执行一些剩余的“意外的性能下降”。但是这最糟糕的是2倍的降低，而不是无限的。

当然，字符串的实现不能改变，但没有必要延续这个问题。