为什么不String的hashCode（）caching0？
我注意到在String 6的Java源代码中，hashCode只caching了除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（）caching0？
- Javastring散列为0的概率是多less？
- 每次散列为0的string，避免重新计算散列值的性能损失的最佳方法是什么？
- 这是caching值的最佳实践方式吗？ （即caching所有除了一个？）
为了您的娱乐，这里的每一行都是一个散列为0的string：
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.
你什么也不担心。 这是一个思考这个问题的方法。
假设你有一个应用程序，除了哈希string，整年都不做任何事情。 比方说，需要一千个string，全部在内存中，以循环方式重复调用hashCode（），一百万遍，然后再获得另外一千个新string。
假设string散列码为零的可能性实际上比1/2 ^ 32大得多。 我相信它比1/2 ^ 32还要大一些，但是比1/2 ^ 16（平方根！现在差很多！）要糟糕得多。
在这种情况下，您将从Oracle的工程师中受益匪浅，从而改善这些string的哈希码如何被caching。 所以你写信给他们，并要求他们修复它。 而且他们使用他们的魔法，以便每当s.hashCode（）为零时，它立即返回（即使是第一次！100％的改进！）。 而且让我们说，他们这样做，而没有任何其他情况下性能退化。
万岁！ 现在你的应用程序是…让我们看看…快0.0015％！
以前需要一整天的时间只需要23小时57分48秒！
记住，我们build立了一个场景，让每一个可能的怀疑的利益，往往是一个荒谬的程度。
这看起来是否值得吗？
编辑：自发布这几个小时前，我已经让我的一个处理器疯狂寻找与零散列码两个词的短语。 到目前为止，它提出了：bequirtle zorillo，chronogrammic schtoff，contusive cloisterlike，creashaks organzine，drumwood boulderhead，electroanalytic exercisable，以及非常nonconstruable。 这大约有2 ^ 35个可能性，所以我们期望只看到8个完美的分配。很明显，到了这个时候，我们会有很多次，但不会超过这个。 更重要的是，我现在想出了一些有趣的乐队名称/专辑名称！ 不公平的偷窃！
它使用0来表示“我还没有制定哈希码”。 另一种方法是使用一个单独的布尔标志，这将花费更多的内存。 （当然，或者不要caching哈希码。）
我不希望很多string散列为0; 可以说散列例程有意义地避免0（例如，将0的散列翻译为1并caching）是有意义的。 这会增加碰撞，但避免重蹈覆辙。 现在要做到这一点已经太迟了，因为String hashCodealgorithm是明确logging的。
至于这是否是一个好主意：这是一个肯定有效的caching机制， 可能 （见编辑）更好地改变，以避免重新哈希值为0的散列。就个人而言，我会有兴趣看到Sun认为这样做的数据首先是值得的 – 对于创build的每个string，它占用了额外的4个字节，但是经常或很less被散列，唯一的好处是不止一次散列的string。
编辑：正如KevinB在其他地方的评论中指出的那样，上面的“避免0”build议可能有一个净成本，因为它帮助一个非常罕见的情况，但是需要对每个散列计算进行额外的比较。
我认为有一件重要的事情是迄今为止的其他答案都不存在：零值存在，以便hashCode-caching机制在multithreading环境中稳健工作。
如果你有两个variables，比如cachedHashCode本身和一个isHashCodeCalculated布尔值来指示是否计算了cachedHashCode，那么你需要线程同步才能在multithreading环境中工作。 同步会对性能造成影响，特别是因为string在多个线程中被重用。
我对Java内存模型的理解有点粗略，但大概是这样的：
-
当多个线程访问variables（如caching的hashCode）时，不能保证每个线程都能看到最新的值。 如果一个variables从零开始，则A更新它（将其设置为非零值），然后线程B在之后不久读取它，线程B仍然可以看到零值。
-
还有一个问题是从多个线程访问共享值（没有同步） – 你可能会试图使用一个只被部分初始化的对象（构造一个对象不是一个primefaces进程）。 multithreading读取和写入64位基元（如long和double）不一定是primefaces，所以如果两个线程试图读取和更改long或double的值，则一个线程最终会看到奇怪的和部分设置的。 或者无论如何。 如果您尝试同时使用两个variables（如cachedHashCode和isHashCodeCalculated），也会出现类似的问题 – 线程可以轻松地查看其中一个variables的最新版本，但可以看到其中一个variables的最新版本。
-
解决这些multithreading问题的常用方法是使用同步。 例如，您可以将所有对cachinghashCode的访问放在一个同步块中，或者可以使用volatile关键字（尽pipe要小心，因为语义有点混乱）。
-
但是，同步会降低速度。 糟糕的想法，像一个stringhashCode。 string经常用作HashMaps中的键，所以您需要使用hashCode方法来执行，包括在multithreading环境中。
-
诸如int之类的32位或更less的Java原语是特殊的。 与长时间（64位值）不同，您可以确定您永远不会读取int的部分初始化值（32位）。 当你读取一个没有同步的int时，你不能确定你会得到最新的设定值，但是你可以确定你得到的值是你的线程明确设置的值，或者另一个线程。
java.lang.String中的hashCodecaching机制被设置为依赖于上面的第5点。 您可以通过查看java.lang.String.hashCode（）的源代码来更好地理解它。 基本上，multithreading一次调用hashCode，hashCode可能会被多次计算（如果计算的值为零，或者多个线程同时调用hashCode，并且都看到一个零caching的值），但是可以确定hashCode （）将始终返回相同的值。 所以它是健壮的，也是高性能的（因为在multithreading环境中没有同步行为的瓶颈）。
就像我说的，我对Java内存模型的理解有点粗略，但是我确信我已经掌握了上面的要点。 最终，这是一个非常聪明的习惯用于cachinghashCode而不需要同步的开销。
0不被caching，因为实现将caching值0解释为“caching值尚未初始化”。 另一种方法是使用java.lang.Integer ，其中null表示该值尚未被caching。 但是，这意味着额外的存储开销。
关于一个string的哈希码被计算为0的概率，我会说这个概率是相当低的，可能发生在下列情况：
- string是空的（虽然每次重新计算这个哈希码实际上是O（1））。
- 发生溢出，由此最终计算的散列码是0（
eg Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0）。 - string只包含Unicode字符0.非常不可能，因为除了“纸带世界”（！）之外，这是一个无意义的控制字符：
维基百科 ：
代码0（ASCII代码名称NUL）是一个特例。 在纸带上，没有孔时就是这种情况。 把这个视为一个填充字符是没有意义的，否则就很方便 。
事实certificate，这是一个很好的问题，与安全漏洞有关 。
“当对一个string进行散列处理时，Java也会将散列值存储在散列属性中，但前提是结果不是零，因此，对于攻击者来说，目标值零特别有趣，因为它可以防止caching和强制重新散列。
- 为什么不String的hashCode（）caching0？
值零被保留，意思是“散列码未被高速caching”。
- Javastring散列为0的概率是多less？
根据Javadoc，string哈希码的公式是：
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
使用int算术，其中s[i]是string的第i个字符， n是string的长度。 （空string的散列值被定义为零作为特殊情况。）
我的直觉是，上面的散列码函数给出了整个int值范围内String散列值的统一分布。 均匀分布意味着随机生成的string散列为零的概率在2 ^ 32中为1。
- 每次散列为0的string，避免重新计算散列值的性能损失的最佳方法是什么？
最好的策略是忽略这个问题。 如果你重复哈希相同的string值，那么你的algorithm有一些奇怪的东西。
- 这是caching值的最佳实践方式吗？ （即caching所有除了一个？）
这是一个空间与时间的权衡。 AFAIK，替代scheme是：
-
为每个String对象添加一个
cached标志，使每个Javastring都占用一个额外的单词。 -
使用
hash成员的最高位作为caching标志。 这样你可以caching所有的散列值，但是你只有一半的可能的String散列值。 -
不要在string上caching哈希码。
我认为Javadevise师已经对Strings做出了正确的要求，我相信他们已经做了大量的分析，证实了他们的决定是正确的。 然而，这并不意味着这将永远是处理caching的最佳方式。
（请注意，有两个“常见”的string值散列为零，空string和只包含NUL字符的string，但是计算这些值的哈希码的代价与计算哈希码为一个典型的string值。）
好的人，它保持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; }
正如你所看到的，如果string为空，这将总是返回一个快速的零：
if (h == 0 && value.length > 0) ...
“避免0”的build议似乎是适当的build议作为最佳实践，因为它有助于一个真正的问题（严重意外的性能下降，在可供攻击者提供的可构造的情况下）的写作之前的分支操作微不足道的成本。 还有一些“意想不到的性能下降”，如果唯一的东西进入到特定的调整值的集合哈希值，可以行使。 但最坏的情况是2倍的降低，而不是无限的。
当然，String的实现是不能改变的，但是没有必要延续这个问题。
