在《算法（第4版）》第 129 页说到：

第1章 基础

1.4 算法分析

1.4.9 内存

1.4.9.5 字符串的值和子字符串

一个长度为 N 的 String 对象一般需要使用 40 字节（String 对象本身）加上（24 + 2N ）字节（字符数组），总共（64 + 2N ）字节。但字符串处理经常会和子字符串打交道，所以 Java 对字符串的表示希望能够避免复制字符串中的字符。当你调用 substring() 方法时，就创建了一个新的 String 对象（40 字节），但它仍然重用了相同的 value[] 数组，因此该字符串的子字符串只会使用 40 字节的内存。含有原始字符串的字符数组的别名存在于子字符串中，子字符串对象的偏移量和长度域标记了子字符串的位置。换句话说，一个子字符串所需的额外内存是一个常数，构造一个子字符串所需的时间也是常数，即使字符串和子字符串的长度极大也是这样。某些简陋的字符串表示方法在创建子字符串时需要复制其中的字符，这将需要线性的时间和空间。确保子字符串的创建所需的空间（以及时间）和其长度无关是许多基础字符串处理算法的效率的关键所在。字符串的值与子字符串示例如图 1.4.10 所示。

这段话对应于《算法（英文版 第4版）》第 202 至 204 页：

1 Fundamentals

1.4 Analysis of Algorithms

Memory

String values and substrings. A String of length N typically uses 40 bytes (for the String object) plus 24 + 2N bytes (for the array that contains the characters) for a total of 64 + 2N bytes. But it is typical in string processing to work with substrings, and Java’s representation is meant to allow us to do so without having to make copies of the string’s characters. When you use the substring() method, you create a new String object (40 bytes) but reuse the same value[] array, so a substring of an existing string takes just 40 bytes. The character array containing the original string is aliased in the object for the substring; the offset and length fields identify the substring. In other words, a substring takes constant extra memory and forming a substring takes constant time, even when the lengths of the string and the substring are huge. A naive representation that requires copying characters to make substrings would take linear time and space. The ability to create a substring using space (and time) independent of its length is the key to efficiency in many basic string-processing algorithms.

我当时读到这里，就觉得 Java 的字符串和子串的实现和 .NET Framework 中的很不一样。后者正是如 Sedgewick 所说的：

某些简陋的字符串表示方法在创建子字符串时需要复制其中的字符，这将需要线性的时间和空间。

我到 网站下载了 OpenJDK 8 的源代码：

$ hg clone https://hg.openjdk.java.net/jdk8/jdk8 openjdk8
$ cd openjdk8 && sh ./get_source.sh

然后阅读了 的源代码，觉得实现方法和 .NET Framework 中的一样，也是在创建子字符串时需要复制其中的字符。后来看到的一篇文章：，知道了以下几点：

1. 在 .NET Framework 中创建子字符串确实需要复制其中的字符：

   从中可以看出，无论是字符串连接还是取部分字符串，CPU和内存的消耗都与目标字符串的长度线性相关。换句话说，字符串越长，代价越高，假如要反复大量地操作一个大型的字符串，则会对性能产生很大影响。

   这些应该都是每个.NET程序员都了若指掌的基础。

2. 在 Open JDK 7 中字符串和子串的实现确如 Sedgewick 所说：

   严格来说，“Java”是一个标准，而没有限制特定的实现方式，我们这里分析的是使用最广泛的OpenJDK实现。

   这里我们可以看出OpenJDK 7与.NET的不同，后者是直接包含字符序列的内容，而前者则是保留一个字符数组，并记录起始位置及其偏移量。这么做最大的好处是substring方法无需复制内存，而完全可以重用内部的字符数组。

3. 但是这样很容易造成内存泄露：

   共享字符数组的优势显而易见，而劣势便是成为了Java程序中最常见的内存泄露原因之一。说起来我到十八摸以后写的第一个程序便遇到了这个问题：从服务器端得到一个长长的字符串形式的数据，经过一个内部解析类库获得一小个片段（可能只是记录个ID）并保存在内存中。不过后来发现内存的占用量上升的很快，且稳定后比预想地要高的多，通过Memory Profiling发现原来是这一小段字符串还持有原来完整的内容。

4. 在 OpenJDK 8 中 String 类的实现改为和 .NET Framework 一致了：

   有意思的是，在未来的OpenJDK 8里，String类的这方面表现已经改变了。

   OpenJDK 8放弃了保留了近二十年的设计，让String对象使用各自独立的字符数组，就跟.NET一贯以来的做法一样。这样，它的相关方法如substring也有了相应改变。

   这里直接调用的已经是之前列举过的，会复制字符数组内容的公有构造函数了。所以说，“Java”只是一个标准，可以有各种实现。从外部表现看来，OpenJDK 8的String类相对于之前没有任何变化。

前面 Sedgewick 说过：

确保子字符串的创建所需的空间（以及时间）和其长度无关是许多基础字符串处理算法的效率的关键所在。

那么，在 Java 语言的未来版本中，《算法（第4版）》一书中的许多基础字符串处理算法的效率将大有问题。而且在 C# 语言的当前版本中，也会大有问题。

《算法（第4版）》第 VII 页：

前言

作为教材

虽然本书使用 Java 实现算法和数据结构，但其代码风格使得熟悉其他现代编程语言的人也能看懂。我们充分利用了 Java 的抽象性（包括泛型），但不会依赖这门语言的独门特性。

这里前半部说得不错，我就是熟悉 C# 语言，对 Java 语言仅是表面上的了解，但理解这本书的内容也非常容易。后半部说“不会依赖这门语言的独门特性”就有问题了：

一个子字符串所需的额外内存是一个常数，构造一个子字符串所需的时间也是常数

这个就是 Java 语言的独门特性，而且是 Java 语言当前版本的独门特性，在 Java 语言的未来版本中也会取消这个独门特性。

不知道《算法》这本书再版时，Sedgewick 会不会就此作些改进？