77

我在 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.
4

9 回答 9

58

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

假设您有一个应用程序,除了整年都在散列字符串之外什么都不做。假设它需要一千个字符串,全部在内存中,以循环方式重复调用 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、creashaksorganzine、drumwood boulderhead、electroanalytic exercisable 和 favosely nonconstructable。这是大约 2^35 种可能性中的一种,因此在完美分布的情况下,我们预计只会看到 8 种。很明显,当它完成时,我们会有几倍,但不会更多。更重要的是,我现在想出了一些有趣的乐队名/专辑名!偷窃不公平!

于 2010-02-22T18:41:33.013 回答
24

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

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

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

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

于 2010-02-22T11:22:02.480 回答
19

我认为到目前为止缺少其他答案的一些重要的东西:零值存在,因此 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,是特殊的。与 long(64 位值)不同,您可以确定永远不会读取 int(32 位)的部分初始化值。当您在没有同步的情况下读取 int 时,您无法确定您是否会获得最新的设置值,但您可以确定您获得的值是您的线程在某个时间点明确设置的值,或者另一个线程。

java.lang.String 中的 hashCode 缓存机制设置为依赖于上面的第 5 点。通过查看 java.lang.String.hashCode() 的源代码,您可能会更好地理解它。基本上,如果多个线程同时调用 hashCode,hashCode 可能最终会被计算多次(如果计算的值为零,或者多个线程同时调用 hashCode 并且都看到零缓存值),但您可以确定 hashCode () 将始终返回相同的值。所以它很健壮,而且它也很高效(因为在多线程环境中没有同步作为瓶颈)。

就像我说的,我对 Java 内存模型的理解有点粗略,但我很确定我已经掌握了上面的要点。归根结底,这是一个非常聪明的习惯用法,用于缓存 hashCode 而无需同步开销。

于 2010-09-18T18:30:45.933 回答
8

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

关于字符串的哈希码被计算为 0 的概率,我会说概率非常低,并且可能在以下情况下发生:

  • 字符串是空的(尽管每次重新计算这个哈希码实际上是 O(1))。
  • 发生溢出,最终计算的哈希码为 0 ( e.g. Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0)。
  • 该字符串仅包含 Unicode 字符 0。不太可能,因为这是一个除了“纸带世界”(!)之外没有任何意义的控制字符:

来自维基百科

代码 0(ASCII 代码名称 NUL)是一种特殊情况。在纸带中,是没有孔的情况。将其视为填充字符很方便,没有其他意义

于 2010-02-22T11:23:12.123 回答
6

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

“当对字符串进行哈希处理时,Java 还会在哈希属性中缓存哈希值,但前提是结果不为零。因此,目标值零对于攻击者来说特别有趣,因为它可以防止缓存并强制重新哈希。”

于 2012-01-07T08:04:08.223 回答
4

十年后,情况发生了变化。老实说,我不敢相信这一点(但我内心的极客非常快乐)。

正如您已经注意到的那样,某些字符串可能存在String::hashCode某些字符串zero并且缓存(将得到缓存)。很多人争论(包括在这个问答中)为什么没有在java.lang.String: 中添加一个字段,hashAlreadyComputed然后简单地使用它。问题很明显:每个 String 实例都有额外的空间。顺便说一句,引入s 是有原因 的,因为许多基准测试表明,在大多数应用程序中,这是一个相当(过度)使用的类。增加更多空间?决定是:不。特别是因为最小可能的加法本来是,而不是(对于s,额外的空间本来是java-9compact String1 byte1 bit32 bit JMV8 bytes: 1 表示标志,7 表示对齐)。

因此,Compact Strings 出现了java-9,如果您仔细(或关心)他们确实java.lang.String在:中添加了一个字段coder。我刚才不是反对吗?那并没那么简单。似乎紧凑字符串的重要性超过了“额外空间”的论点。同样重要的是要说额外的空间32 bits 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 bytes因此,在添加 时coder1 byte 无需添加额外空间即可。因此, Compact String添加 s 之后,布局发生了变化:

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

coder1 byte了,差距缩小到了3 bytes。所以“伤害”已经造成了jdk-9。因为32 bits JVM有一个增加8 bytes : 1 coder + 7 gap和为64 bit JVM- 没有增加,coder从间隙中占据了一些空间。

而现在,jdk-13他们决定利用它gap,因为它无论如何都存在。让我提醒您,具有零 hashCode 的字符串的概率是 40 亿分之一;还是有人说:那又怎样?让我们解决这个问题!瞧:jdk-13布局java.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

只有在我读完这个之后才有意义。相当棘手,但这一次只写一篇,更多细节在上面的讨论中。

于 2020-09-26T22:11:03.190 回答
0
  • 为什么 String 的 hashCode() 不缓存 0?

零值保留为“不缓存哈希码”。

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

根据 Javadoc,字符串哈希码的公式是:

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

使用int算术运算,其中s[i]是字符串的第 i 个字符,是字符串n的长度。(作为特殊情况,空字符串的哈希值定义为零。)

我的直觉是,上面的 hashcode 函数在值的范围内提供了 String 哈希值的均匀分布int。均匀分布意味着随机生成的字符串散列为零的概率是 2^32 中的 1。

  • 对于散列为 0 的字符串,避免每次重新计算散列值的性能损失的最佳方法是什么?

最好的策略是忽略这个问题。如果您重复地散列相同的字符串值,那么您的算法就会有些奇怪。

  • 这是缓存值的最佳实践方式吗?(即缓存除一个之外的所有内容?)

这是空间与时间的权衡。AFAIK,替代方案是:

  • 为每个 String 对象添加一个cached标志,使每个 Java String 都多出一个单词。

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

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

我认为 Java 设计人员对 Strings 的要求是正确的,而且我确信他们已经进行了广泛的分析,以证实他们的决定是正确的。但是,这并不意味着这始终是处理缓存的最佳方式。

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

于 2010-02-22T14:20:36.020 回答
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) ...
于 2015-04-25T09:16:06.183 回答
0

“避免 0”的建议似乎适合推荐为最佳实践,因为它有助于解决真正的问题(在可以由攻击者提供的可构造案例中严重意外的性能下降),因为在写入之前分支操作的成本微薄。如果唯一的东西进入到特殊调整值的集合散列中,则可以执行一些剩余的“意外性能下降”。但这在最坏的情况下是 2 倍的降级,而不是无限的。

当然,String 的实现是不能改变的,但没有必要让这个问题长期存在。

于 2016-10-28T22:56:38.350 回答