Java 7 String - 子串复杂性

Question

在Java 6之前,我们有一个恒定的时间子串String.在Java 7中,他们为什么决定使用复制char数组 - 并降低线性时间复杂度 - 当这样的东西StringBuilder完全意味着什么？

Answer 1

为什么他们决定在Oracle错误#4513622中讨论:(str)保留字段的子字符串会阻止GC作为对象:

当您在示例中调用String.substring时,不会分配用于存储的新字符数组.它使用原始String的字符数组.因此,支持原始String的字符数组不能进行GC,直到子字符串的引用也可以是GC.这是一种有意的优化,可以防止在常见场景中使用子字符串时过多的分配.不幸的是,有问题的代码遇到了原始数组的开销明显的情况.对于两个边缘情况都难以优化.对空间/大小权衡的任何优化通常都很复杂,并且通常可以是特定于平台的.

还有这个说明,并指出根据测试,曾经的优化已成为一种悲观情绪:

很长一段时间以来,准备和计划一直在从java.lang.String中删除offset和count字段.这两个字段使多个String实例共享相同的后备字符缓冲区.共享字符缓冲区是旧基准测试的重要优化,但使用当前的真实代码和基准测试,实际上最好不共享后备缓冲区.共享字符串数组后备缓冲区仅在使用String.substring时"获胜".受到负面影响的情况可能包括解析器和编译器,但是当前的测试显示整体上这种变化是有益的.

Answer 2

如果你有一个短暂的,大父串长住小串,大的char []备份父字符串直到小串移出范围符合垃圾收集.这意味着子字符串可以占用比人们预期更多的内存.

Java 6方式表现得更好的唯一一次是有人从一个大的父字符串中获取一个大的子字符串,这是一种非常罕见的情况.

显然,他们认为这种变化的微小性能成本被旧方式引起的隐藏内存问题所抵消.决定因素是问题是隐藏的,而不是有解决方法.

Answer 3

这将以相当大的差距影响数据结构(如后缀阵列)的复杂性.Java应该提供一些替代方法来获取原始字符串的一部分.

Answer 4

这只是他们修复某些 JVM 垃圾收集限制的蹩脚方法。

在 Java 7 之前，如果我们想避免垃圾收集不起作用的问题，我们总是可以复制子字符串而不是保留 subString 引用。这只是对复制构造函数的额外调用：

String smallStr = new String(largeStr.substring(0,2));

但现在，我们不能再拥有恒定时间的 subString。这悲剧。