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

78
我注意到在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
Microcomputers: the unredeemed lollipop...
Incentively, my dear, I don't tessellate a derangement.
A person who never yodelled an apology, never preened vocalizing transsexuals.

7
LOL!+1 是一个很好的超级极客式的恶搞行为示例! - Mike Nakis
自从这个问题被提出以来,情况已经发生了变化。 - Eugene
9个回答

59
你担心的没有必要。以下是思考此问题的一种方式。
假设你有一个应用程序,它除了一直对字符串进行哈希处理,什么也不做。假设它接收了一千个字符串,全部存储在内存中,以轮流的方式反复调用它们的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、electroanalytic exercisable 和 favosely nonconstruable。这大约是2^35种可能性之一,因此如果分布完美,我们只会看到8个。显然,当它完成时,我们将有多出几倍的数量,但不会夸张。更重要的是,我现在想出了几个有趣的乐队名字/专辑名!不要抄袭!


2
这是一个非常实用的论点。不过,出于好奇,这种缓存机制在其他地方是否也很常见?也就是说,如果尝试缓存所有值都需要一个额外的标志,那么最好的做法是牺牲一个值使其无法缓存吗? - polygenelubricants
2
我确定我已经用过这个技巧一两次了。当然,与大多数类相比,String类的要求非常特殊。顺便说一句,你的用户名很合适 :) - Kevin Bourrillion
20
最近我对String的hashCode()非常着迷,正如我的用户名所示。在2007年7月23日的Google技术讲座视频中,Joshua Bloch说他在10分钟内在(200,000)^2个单词对中发现了"polygenelubricants"。我利用哈希函数的属性,在几秒钟内以O(N)的复杂度完成了同样的工作。例如,下面这个字符串也会被哈希成最小值:“And so my fellow mismanagements: ask not what your newsdealer can sugarcoat for you -- ask what you can sugarcoat for your newsdealer.” - polygenelubricants
6
如果这些字符串来自用户,那么概率接近于1。你知道肯定会有人试一试。 - Antimony
1
我猜对于polygenelubricants来说可能是值得的,因为服务器花费更长时间来回答查询并迫使它们重新计算哈希:)自我提醒:明智地选择用户名。 - jontejj
给予所有可行的怀疑利益。这是每一个可能的怀疑利益吗?该场景测量吞吐量。如果您的用例关心延迟呢?如果被散列的字符串受到攻击者的控制,因此他们可以将“bequirtle zorillo”注入到这个延迟敏感的应用程序中,那该怎么办?我不是说这意味着优化零情况变得值得,但它更像是一个最坏情况,而不是所呈现的那种情况。 - user849827

24

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

我不希望许多字符串的哈希值为0;可以说哈希程序应该有意避免0(例如将哈希值为0转换为1,并缓存它)。这样会增加冲突,但避免了重新哈希。不过现在已经太晚了,因为String hashCode算法已经明确记录。

至于这是否是一个好主意:这绝对是一种有效的缓存机制,并且在避免重新哈希值为0的情况下,可能会更好(见编辑)。个人认为,如果Sun相信这是值得做的事情的数据,我会很感兴趣 - 它为每个创建的字符串额外占用4个字节,无论它被哈希多少次或少次,唯一的好处是对于哈希值超过一次的字符串。

编辑:正如KevinB在其他评论中指出的那样,“避免0”的建议可能会产生净费用,因为它对一个非常罕见的情况有所帮助,但需要为每个哈希计算进行额外的比较。


1
@Stephen C:这是基于完全分布式哈希的假设。我不知道String使用的哈希是否符合此条件。 - Jon Skeet
1
我不指望很多字符串哈希为0。除非这些字符串是故意选择的。 - Tom Hawtin - tackline
1
嗯,除非字符串是故意选择的,不然就不会这样。嗯,""可能是Java世界中最常见的字符串(谁知道有多少个字符串被初始化为""并且从未改变过呢?),而"".hashCode()等于0。我无法想象出很多使用场景,比如将""用作映射键,但我相信这种情况可能会发生,所以这可能会带来不成比例的开销。话虽如此,"".hashCode()基本上只是执行一个从0到0的循环,所以我不认为它会慢...即使它真的慢了,又有谁在乎呢(参见Kevin的回答)? - Cowan
@JonSkeet 但是为什么不使用负数作为标志呢?String哈希码函数似乎没有返回一个。 - Sergio
1
@Sergio:是的,它确实可以。例如,"aaaaaa".hashCode() 返回-1425372064。 - Jon Skeet
显示剩余10条评论

19

我认为其他回答缺少重要内容:零值的存在是为了在多线程环境下使hashCode缓存机制更加稳健。

如果您有两个变量,例如cachedHashCode本身和一个isHashCodeCalculated布尔变量来指示是否已经计算了cachedHashCode,则需要线程同步才能在多线程环境中正常工作。而同步会影响性能,特别是由于String经常在多个线程中复用。

我对Java内存模型的理解还不太全面,但大致上是这样的:

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

  2. 从多个线程访问共享值(不使用同步)中存在另一个问题-可能会尝试使用只有部分初始化的对象(构造对象不是原子过程)。64位基元类型(如long和double)的多线程读写也不一定是原子的,因此如果两个线程尝试读取和更改long或double的值,则一个线程可能会看到奇怪的部分设置。或者类似的问题。如果尝试一起使用两个变量,例如cachedHashCode和isHashCodeCalculated,则线程很容易会看到其中一个变量的最新版本,但是另一个变量的旧版本。

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

  4. 但是,同步会减慢速度。对于像字符串hashCode这样的东西来说,这是个坏主意。String经常用作HashMap中的键,因此需要hashCode方法在性能上表现良好,包括在多线程环境中。

  • Java中32位或更小的基本数据类型,例如int,是特殊的。与64位值long不同,您可以确保永远不会读取到部分初始化的int(32位)。当您在没有同步的情况下读取int时,您不能确保您会获得最新设置的值,但是您可以确信您获得的值是由您的线程或其他线程明确设置过的值。

  • java.lang.String中的hashCode缓存机制建立在上述第5点的基础上。通过查看java.lang.String.hashCode()的源代码,您可能会更好地理解它。基本上,如果多个线程同时调用hashCode,并且已经缓存的值为零,则hashCode可能会被计算多次(无论是计算出的值为零还是多个线程同时调用hashCode并且都看到了一个零的缓存值),但是您可以确信hashCode()始终将返回相同的值。因此它具有鲁棒性,并且在多线程环境中也非常高效(因为没有同步作为瓶颈)。

    正如我所说,我对Java内存模型的理解有些含糊,但我相当确定我已经正确理解了上述内容的要点。这最终是一种非常聪明的惯用语,用于在没有同步开销的情况下缓存hashCode。


    您不一定需要同步 - 正如您所提到的,有像volatile这样的东西。虽然确实需要小心处理volatile,但我认为可以放心地说String类的作者可能知道如何正确使用它,或者有适当的人来咨询。我理解您的观点...但我仍然不太相信缓存所有内容是值得的,而且系统中每个字符串都存在内存成本:( - Jon Skeet
    1
    据我所知,volatile是一种同步形式,只是它比synchronized关键字的开销更小。我在这个链接http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html中发现了一些内容,其中部分解释了String的hashcode中使用的习惯用法。我自己非常喜欢它 - 实际上我想我会开始更多地使用它 :) 尽管我很欣赏你提到的内存问题 - 对于某些事情来说,这可能是一个问题。顺便说一下,String.intern()是为什么多线程性能对于字符串很重要的原因 - 它们可以被JVM内部重新使用。 - MB.
    1
    这可能是将零视为特殊值的一个好理由,但这并不足以让哈希函数返回一个不可缓存的值。在哈希函数中包含类似下面的内容是否会有任何困难:if (computedHash != 0) return computedHash; else return «some other function»;?即使其他函数只是获取字符串中第一个字符的ASCII值,加上最后字符的991倍,并加上1234567890,也不会太影响分布。 - supercat
    如果(computedHash != 0)返回computedHash;否则返回«some other function»;实际上就是在hashCode函数中的应用,只是对多线程调用时发生的情况进行了处理。您可以查看源代码。除了多线程之外,这意味着如果计算出的哈希码为零(这本来就很不可能),每次调用函数时都会重新计算哈希码。 - MB.
    我同意第一点。@supercat,花了相当长的时间,但他们修复了这个问题。 - Eugene

    8

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

    关于计算字符串哈希码为0的概率,我认为概率很低,并可能发生以下情况:

    • 字符串为空(虽然每次重新计算此哈希码实际上是O(1))。
    • 溢出发生,在这种情况下,最终计算的哈希码为0(例如:Integer.MAX_VALUE + h(c1) + h(c2) + ... +h(cn) == 0)。
    • 字符串仅包含Unicode字符0。这非常不可能,因为这是一个控制字符,在“纸带世界”以外没有任何意义!

    来自维基百科

    代码0(ASCII代码名称NUL)是一个特殊情况。在纸带中,当没有孔时,它就是这种情况。将其视为“无意义”的填充字符是很方便的。


    如果您与本地代码进行接口,则\u0000仍然存在,例如在我的Windows机器上,new File("C:\CONFIG.SYS\u0000ignored").isFile() == true。这是各种安全问题的根源。对于大多数应用程序,请过滤此字符! - Thomas Jung
    @Thomas Jung 如果你必须查看文件路径,首先要进行规范化(当然是白名单字符而不是黑名单)。即使这样也无法防止符号链接的攻击。 - Tom Hawtin - tackline
    1
    请注意,如果您的字符串中有非 NUL 字符,则该字符串在具有零哈希码之前必须为六或七个字符长。 - Tom Hawtin - tackline

    6

    这其实是一个很好的问题,与安全漏洞有关。

    当Java对字符串进行哈希处理时,只有在结果与零不同时它才会将哈希值缓存到哈希属性中。因此,对于攻击者来说,目标值为零尤其有趣,因为它可以防止缓存并强制重新哈希。


    仅返回翻译的文本:no more - Eugene
    @Eugene,非常好的跟进!感谢您在您的回答中提供的所有细节。 - cdunn2001

    5

    十年后,一切都变了。我真的不敢相信这一点(但是内心的极客非常开心)。

    正如您所注意到的那样,有些字符串的String :: hashCode0,而这个值之前没有被缓存(稍后会涉及到)。许多人争论(包括在这个问题的问答中)为什么没有在java.lang.String中增加一个字段,比如说:hashAlreadyComputed,然后直接使用它。问题很明显:每个String实例需要额外的空间。顺便说一下,java-9引入了compact String,有原因的,因为许多基准测试表明,这是一个相当(过度)使用的类,在大多数应用程序中都是如此。再添加更多的空间?决策是:不要。特别是最小可能的添加将是1字节,而不是1位(对于32位JMV,额外空间将是8字节:1个标志位,7个对齐位)。

    因此,在java-9中出现了Compact String,如果您仔细观察(或关心),他们确实在java.lang.String中添加了一个字段:coder。我不是刚反对过这个吗?事情并没有那么简单。似乎紧凑字符串的重要性超过了“额外空间”的论点。还要说的是,额外空间只对32位VM有影响(因为对齐没有空隙)。相比之下,在jdk-8中,java.lang.String的布局如下:

    java.lang.String object internals:
     OFFSET  SIZE     TYPE DESCRIPTION                           VALUE
      0    12          (object header)                           N/A
     12     4   char[] String.value                              N/A
     16     4      int String.hash                               N/A
     20     4          (loss due to the next object alignment)
     Instance size: 24 bytes
     Space losses: 0 bytes internal + 4 bytes external = 4 bytes total
    

    注意这里的一个重要事项:

    Space losses : ... 4 bytes total.
    

    因为每个Java对象都是对齐的(这取决于JVM和一些启动标志,例如UseCompressedOops),所以在 String 中存在未使用的 4字节 间隙。当添加 coder 时,它只需要使用1字节而不需要额外的空间。因此,在添加了Compact String之后,布局发生了变化:
    java.lang.String object internals:
     OFFSET  SIZE     TYPE DESCRIPTION                           VALUE
      0    12          (object header)                           N/A
     12     4   byte[] String.value                              N/A
     16     4      int String.hash                               N/A
     20     1     byte String.coder                              N/A
     21     3          (loss due to the next object alignment)
     Instance size: 24 bytes
     Space losses: 0 bytes internal + 3 bytes external = 3 bytes total
    
    coder 占用 1个字节,间隙缩小到了 3个字节,这个“损坏”已经在 jdk-9 中发生了。对于 32位JVM,增加了 8个字节:1 coder + 7个间隙,而对于 64位JVM,没有增加,coder 占用了一些空间来填补间隙。

    现在,在 jdk-13 中他们决定利用这个 间隙,既然它已经存在了。让我提醒你,具有零 hashCode 的字符串的概率是 40 亿分之一;但仍有人说:那又怎样?我们来解决一下!于是乎:jdk-13java.lang.String 的布局改变为:

    java.lang.String object internals:
    OFFSET  SIZE      TYPE DESCRIPTION                            VALUE
      0    12           (object header)                           N/A
     12     4    byte[] String.value                              N/A
     16     4       int String.hash                               N/A
     20     1      byte String.coder                              N/A
     21     1   boolean String.hashIsZero                         N/A
     22     2           (loss due to the next object alignment)
     Instance size: 24 bytes
     Space losses: 0 bytes internal + 2 bytes external = 2 bytes total
    

    这就是它:boolean String.hashIsZero。这是在代码库中的样子:

    public int hashCode() {
        int h = hash;
        if (h == 0 && !hashIsZero) {
            h = isLatin1() ? StringLatin1.hashCode(value)
                           : StringUTF16.hashCode(value);
            if (h == 0) {
                hashIsZero = true;
            } else {
                hash = h;
            }
        }
        return h;
    }
    

    等等!h == 0 并且 hashIsZero 字段?这不应该被命名为像:hashAlreadyComputed 吗?为什么实现不是类似于:

        @Override
        public int hashCode(){
            if(!hashCodeComputed){
                // or any other sane computation
                hash = 42;
                hashCodeComputed = true;
            }
    
            return hash;
        }
    

    即使我读了源代码下的注释:
        // The hash or hashIsZero fields are subject to a benign data race,
        // making it crucial to ensure that any observable result of the
        // calculation in this method stays correct under any possible read of
        // these fields. Necessary restrictions to allow this to be correct
        // without explicit memory fences or similar concurrency primitives is
        // that we can ever only write to one of these two fields for a given
        // String instance, and that the computation is idempotent and derived
        // from immutable state
    

    只有在阅读了这篇文章之后,它才变得有意义。这很棘手,但只能一次写入一条,以上讨论中有更多细节。

    0

    各位,如果长度为零,它将最终变成零,因此它保持为0。

    而且很快就会发现len为零,因此哈希码也必须为零。

    所以,为了您的代码审查!这是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) ...
    

    0
    为什么String的hashCode()不缓存0?
    值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标志,使得每个Java字符串需要多占用一个字。

    • 使用hash成员的最高位作为缓存标志。这样你就可以缓存所有哈希值,但是你只有一半的可能性获得字符串哈希值。

    • 根本不要在字符串上缓存哈希码。

    我认为Java设计者对于字符串做出了正确的决定,并且我相信他们已经进行了广泛的分析来证实他们的决策的合理性。然而,这并不意味着这总是处理缓存的最佳方式。

    (请注意,有两个“常见”的字符串值哈希为零;空字符串和仅由NUL字符组成的字符串。然而,与计算典型字符串值的哈希码的成本相比,计算这些值的哈希码的成本很小。)


    我不相信1在2的32次方中是正确的:对于较短的字符串,哈希码将在范围[0,Integer.MAX_VALUE]内,而对于任何足够长以导致溢出的字符串,哈希码将在范围[Integer.MIN_VALUE,Integer.MAX_VALUE]内。因此,对于随机生成的字符串(并假设使用均匀分布的哈希算法),分布不完全均匀;正数或零哈希码的概率比负数更高。 - Adamski
    hashCode算法很快会导致整数溢出,Adamski。随机取几个例子,6个字符似乎已经足够了 - 但我认为你的推理是正确的,这确实会导致哈希值偏向正值(随着字符串变长而降低)。 - oxbow_lakes
    你忽略了我在答案中列出的选项:在算法末尾添加一个 "if (hash == 0) hash = 1;"。这样你就不会丢失一半的正常哈希值,只会减少一个。 - Jon Skeet
    @Jon Skeet,您的想法源于一种非常普遍的谬误。一个常见的、出于善意的“优化”是从A组中拿走1美元,每个B组人分配100美元……而没意识到A组有10,000倍的人口规模。这是净损失。 - Kevin Bourrillion
    @KevinBourrillion: 字符串哈希函数返回不可缓存值的事实意味着,将许多长字符串相互比较的程序可能因某些输入而以确定性方式比其他输入慢数个数量级。为了防止每次执行都有独立随机的四十亿分之一的机会取决于额外毫秒时长,使哈希代码函数需要花费更长时间可能不是一个好的交易,但这不是面临的选择。如果一个字符串未能缓存其哈希码,它将每次都失败。 - supercat
    显示剩余4条评论

    0

    “避免0”的建议似乎适合作为最佳实践推荐,因为它可以帮助解决一个真正的问题(在可构造情况下严重意外的性能降级,可能是攻击者提供的),而成本很小,只需要在写入之前进行分支操作。如果进入集合的唯一元素都散列到特殊调整的值,则仍然存在一些“意外的性能降级”。但这最多只会导致2倍的降级,而不是无限制的。

    当然,String的实现无法更改,但没有必要使问题永久存在。


    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文,
    原文链接