Java 8的字符串去重特性

Question

Java 8的字符串去重特性

80

自Java 8（像其他语言一样）中的String占用大量内存，因为每个字符占用两个字节，因此引入了一个名为String Deduplication的新功能，它利用char数组是字符串内部和final的事实，因此JVM可以与它们搞混。

迄今为止，我已经阅读了这个示例，但由于我不是专业的Java编码人员，我很难掌握这个概念。

以下是其内容：

各种字符串重复的策略都被考虑过，但现在实施的策略遵循以下方法：每当垃圾收集器访问String对象时，它会注意到char数组。它获取它们的哈希值并将其存储在弱引用数组旁边。只要它找到另一个具有相同哈希代码的字符串，它就逐个比较它们。如果它们也匹配，一个字符串将被修改并指向第二个字符串的char数组。那么第一个char数组就不再被引用，可以进行垃圾回收。

当然，整个过程会带来一些额外开销，但由严格的限制控制。例如，如果一段时间内未发现字符串具有重复项，则不再进行检查。 我的第一个问题： 由于它最近添加到Java 8更新20中，因此仍缺乏有关此主题的资源，是否有人可以在此处分享有关如何帮助减少String在Java中消耗的内存的实际示例？ 编辑： 以上链接说：

只要它找到另一个具有相同哈希代码的字符串，就会逐个比较它们 我的第二个问题：如果两个字符串的哈希码相同，则这两个字符串已经相同，那么一旦发现两个字符串具有相同的哈希码，为什么还要逐个比较它们的字符？请保留HTML标记。

- Joe

39

你听说过“哈希碰撞”吗？哈希算法只有2³²种不同的哈希码，但是可以生成几乎无限的不同可能的字符串String，即65536²¹⁴⁷⁴⁸³⁶⁴⁸ == practically infinite。换句话说，具有相同的哈希码并不保证这些String是相等的，你需要检查它们是否相等。相反地，有不同的哈希码则意味着这些String不相等。 - Holger

14

我没有链接，但是很容易找到答案：一个 char 是一个 16 位的值，所以它允许有 2¹⁶ == 65536 种组合。一个 String 是一个有着 int 长度的序列，因此它最多可以有 2³¹ 个字符（2³¹ 而不是 2³² 是因为 Java 中的 int 是有符号的，但是 String 的大小是正数），所以最大的 String 长度是 2³¹ == 2147483648（理论上，实际限制会略小一些）。因此，一个 String 最多可以组合达到 2147483648 个字符，每个字符可以有 65536 种可能的组合方式，这使得总共有 65536²¹⁴⁷⁴⁸³⁶⁴⁸ 种组合方式（实际上可能会稍微多一些，因为一个 String 可能也会更短）。 - Holger

6

这段话的意思是，将一个长度为n的数字分成m个不同的数字，则可以有mⁿ种组合。例如，从000到999的十进制数字可以有10³种组合。对于一个字符串，有65536个不同的字符（也称为char），在2147483648个字符位置上可用，因此其组合数为65536²¹⁴⁷⁴⁸³⁶⁴⁸。这个数值仅比\0和“end-of-String”在Java中不同而已。尽管如此，它太大了，无法想象。 - Holger

3

如果你包含了一个可以更短的“字符串”，那么它应该等于(2¹⁶)^(∑ n=0_31(2^n))。这就是我所说的。这并不是稍微多一点点的意思。 - mbomb007

3

哈希码相等并不意味着字符串相等。参见https://dev59.com/M3VD5IYBdhLWcg3wTJrF。 - Raedwald

显示剩余12条评论

4个回答

71

假设你有一本电话簿，其中包含人名和姓氏，分别为 String firstName 和 String lastName。在你的电话簿中，恰好有 100,000 个人的 firstName = "John"。

由于这些字符串是从数据库或文件中获取的，因此它们没有被interned，在JVM内存中会有 10 万个字符数组 {'J', 'o', 'h', 'n'}，即每个 John 字符串一个数组。假设每个数组占20个字节，那么这 100k 个 John 占用了 2MB 的内存。

通过去重，JVM将意识到“John”出现了很多次，并使得所有这些 John 字符串指向相同的底层字符数组，将内存使用减少从2MB降至20个字节。

您可以在JEP中找到更详细的解释。特别是:

许多大型Java应用程序目前存在内存瓶颈。测量结果显示，这些类型的应用程序中约有25％的Java堆存活数据集由String对象消耗。此外，大约一半的String对象是重复的，其中重复表示 string1.equals(string2) 为 true。在堆上具有重复的String对象，实际上只是浪费内存。

[...]

实际预期收益最终达到了约10％的堆减少。请注意，这个数字是基于各种应用程序的广泛平均计算出来的。特定应用程序的堆减少可能会有很大的变化。

- assylias

5

你需要问JVM设计者 - 字符串池技术已经存在很长时间了，我猜随着JVM/垃圾回收器性能的提高以及每个设备的CPU数量增加，他们可以改进过去会引入太多开销的事情。 - assylias

6

在旧版本中，一个String可以指向数组内的一个范围，使用一个int偏移量和长度。在这种情况下，去重将会更加复杂，但另一方面，对于String.substring的结果不需要去重，因为这些子字符串是指向原始数组的。然而，在Java 7中有所改变，提高了对去重功能的需求。 - Holger

3

在一个字符串中查找一个子串的速度要慢得多（O(n^2)？），而判断两个字符串是否相等的时间复杂度最坏为O(n)，当两个字符串具有不同（已缓存）哈希码时，时间复杂度为O(1)，即大部分时间只需要进行简单的整数比较。 - assylias

3

@Joe，我添加了一个链接，它可能更好地回答了你的问题。 - assylias

4

你的意思是：「不，两个字符串...」吗？我对这句话的理解与你不同。 - Sotirios Delimanolis

显示剩余9条评论

6

由于你的第一个问题已经得到了回答，我将回答你的第二个问题。

String对象必须逐个字符比较，因为虽然相等的Object意味着相等的哈希值，反之则不一定成立。

正如Holger在他的评论中所说，这代表着哈希碰撞（hash collision）。

适用于hashcode()方法的规范如下：

如果两个对象根据equals(Object)方法是相等的，则对这两个对象调用hashCode方法必须产生相同的整数结果。

如果两个对象根据equals(java.lang.Object)方法是不相等的，则对这两个对象调用hashCode方法不要求产生不同的整数结果。......

这意味着为了保证它们是相等的，必须逐个字符进行比较以确认两个对象的相等性。由于它们使用哈希表来引用，因此它们首先比较hashCode而不是使用equals，这可以提高性能。

- mbomb007

2

他没有回答你的第二个问题，因此我添加了一些信息，希望对阅读者有所帮助和启发。 - mbomb007

1

哦，很抱歉，但我的意思是我从未真正编辑过主要问题...此外，仅通过阅读最后一段来回答问题并不是一个好方法。 - Joe

2

我已经阅读了所有内容，但是由于我已经看到了被接受的答案，所以我只想提供新信息。 - mbomb007

3

谢谢您的反馈。请问您能否编辑您的答案并添加一句话说明这是对第二个问题的回答？我认为这对未来的读者会有所帮助。 :) 另外，谢谢点赞。 - Joe

2

另外，解释哈希码的一个好方法是哈希值是有限大小的“整数”。这些整数中的每一个都可以表示为“字符串”。由此可见，字符串比哈希值多得多。由于字符串比可能的哈希值多很多倍，因此显然许多字符串必须共享相同的哈希值。 - Peter

显示剩余5条评论

1

他们描述的策略是简单地重用一个字符串内部字符数组，可能用于许多相等的字符串。如果它们相等，则无需每个字符串都有自己的副本。

为了更快地确定2个字符串是否相等，哈希码被用作第一步，因为它是一种快速确定字符串可能相等的方法。因此他们说:

一旦它找到另一个具有相同哈希码的字符串，它就会逐个比较它们的字符

这是为了在使用哈希码确定可能相等性之后进行确定性（但较慢）的相等性比较。

最终，相等的字符串将共享单个基础字符数组。

Java长期以来一直有String.intern()，可以做更或多或少相同的事情（即通过去重相等的字符串来节省内存）。这里的新颖之处在于它发生在垃圾收集时间，并且可以由外部控制。

- geert3

你只是复制了那个示例链接中的内容。 - Joe

@Joe，我在引用他们的陈述的一部分，同时试图解释为什么哈希码在所有这些中都很重要。编辑答案以尝试使其更明显。 - geert3

1

如果你要引用其他文档的一部分，应该使用块引用样式并提供某种归属证明。 - ssube

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Robert Niestroj · Accepted Answer

@assylias的回答基本上告诉了您它是如何工作的，并且是非常好的答案。我已经测试了一个使用了String Deduplication的生产应用，并获得了一些结果。这个Web应用程序大量使用字符串，因此我认为优势非常明显。

要启用String Deduplication，您需要添加以下JVM参数（至少需要Java 8u20）：

-XX:+UseG1GC -XX:+UseStringDeduplication -XX:+PrintStringDeduplicationStatistics

最后一个是可选的，但正如其名称所示，它显示了字符串去重的统计信息。这是我的：

[GC concurrent-string-deduplication, 2893.3K->2672.0B(2890.7K), avg 97.3%, 0.0175148 secs]
   [Last Exec: 0.0175148 secs, Idle: 3.2029081 secs, Blocked: 0/0.0000000 secs]
      [Inspected:           96613]
         [Skipped:              0(  0.0%)]
         [Hashed:           96598(100.0%)]
         [Known:                2(  0.0%)]
         [New:              96611(100.0%)   2893.3K]
      [Deduplicated:        96536( 99.9%)   2890.7K( 99.9%)]
         [Young:                0(  0.0%)      0.0B(  0.0%)]
         [Old:              96536(100.0%)   2890.7K(100.0%)]
   [Total Exec: 452/7.6109490 secs, Idle: 452/776.3032184 secs, Blocked: 11/0.0258406 secs]
      [Inspected:        27108398]
         [Skipped:              0(  0.0%)]
         [Hashed:        26828486( 99.0%)]
         [Known:            19025(  0.1%)]
         [New:           27089373( 99.9%)    823.9M]
      [Deduplicated:     26853964( 99.1%)    801.6M( 97.3%)]
         [Young:             4732(  0.0%)    171.3K(  0.0%)]
         [Old:           26849232(100.0%)    801.4M(100.0%)]
   [Table]
      [Memory Usage: 2834.7K]
      [Size: 65536, Min: 1024, Max: 16777216]
      [Entries: 98687, Load: 150.6%, Cached: 415, Added: 252375, Removed: 153688]
      [Resize Count: 6, Shrink Threshold: 43690(66.7%), Grow Threshold: 131072(200.0%)]
      [Rehash Count: 0, Rehash Threshold: 120, Hash Seed: 0x0]
      [Age Threshold: 3]
   [Queue]
      [Dropped: 0]

这是在应用程序运行10分钟后的结果。您可以看到String Deduplication被执行452次，并且"deduplicated"801.6 MB的字符串。String Deduplication检查了27 000 000个字符串。当我将Java 7和标准Parallel GC与启用String Deduplication的Java 8u20和G1 GC进行比较时，堆大约下降了50％: Java 7 Parallel GC

Java 8 G1 GC with String Deduplication