最有效的字符串拼接方法

Question

我原本认为使用StringBuffer是连接字符串最快的方法，但在看了这篇 Stack Overflow 帖子后发现，concat()是最快的方法。我尝试了Java 1.5、1.6和1.7中给出的两个示例，但我从未得到过他们的结果。我的结果与这里几乎相同。

1. 有人能解释一下我不理解的部分吗？在Java中，什么才是真正最快的字符串连接方式？

2. 当连接两个字符串和多个字符串时，是否有不同的答案？

- Derek Noble

---

String 是不可变的，你应该优先使用 StringBuilder 而不是 StringBuffer。 - Elliott Frisch

你可以轻松地通过一个大的for循环来运行测试，并计时每个示例。 - Russell Elfenbein

要连接4个字符串，您只需执行s1 + s2 + s3 + s4即可。如果需要使用循环连接字符串，则应明确使用StringBuilder。 - Paul Boddington

在链接的示例帖子中，concat 更快，因为没有创建 StringBuilder 对象的开销。如果您的目标仅是连接两个字符串，则 concat() 更快。如果您需要连接超过两个字符串，或者在将来的任何时候可能会添加多个连接，则我会怀疑显式的 StringBuilder 更快。 - nickb

进行一些分析，并选择最适合您的特定问题、平台和硬件的方案。 - Xiongbing Jin

@nickb 我的问题是，当我运行相同的示例时，我没有得到concat作为最快的方法。 - Derek Noble

Answer 1

String.concat比起+操作符连接两个字符串时更快... 尽管这个问题可能随时可以解决，甚至在我所知道的Java 8中已经解决了。

在你引用的第一篇文章中，你错过了一个重要细节，那就是作者只是连接了两个字符串，而快速的方法是预先计算新字符数组的大小为str1.length() + str2.length()，这样底层的字符数组只需要分配一次。

使用StringBuilder()时没有指定最终大小，这也是内部+操作符的方式，往往需要做更多的分配和底层数组的复制操作。

如果你需要将一堆字符串连接在一起，那么应该使用StringBuilder。如果可以的话，预先计算最终大小，这样底层的数组只需要分配一次。

- Matt Timmermans

---

很好的解释。但是能否提供一些想法，为什么当我在我的电脑（Windows）上复制并粘贴同样的代码，并执行时，无法像最快的方法那样得到“concat”？我尝试了两个代码，但它们都没有给出他们得到的相同结果。即使我多次尝试也是这样：none: 7 ns plus: 82 ns concat: 72 ns builder1: 46 ns builder2: 33 ns buffer1: 31 ns buffer2: 38 ns - Derek Noble

尝试以相反的顺序运行测试，看看是否得到相同的结果。然后请参阅：https://dev59.com/hHRB5IYBdhLWcg3wz6UK - Matt Timmermans

另外，快速地，尝试连续运行每个程序两次（所有的1000万次迭代），并查看仅第二次运行的时间。 - Matt Timmermans

谢谢您的建议。我都尝试了，但仍然无法让“cancat”标记为获胜者。不过，当我每个都运行两次时，我注意到concat值显着下降，而其他值第二次运行时仍保持不变。 - Derek Noble

Answer 2

我从其他人的回答中了解到以下内容：

如果您需要线程安全，请使用StringBuffer。

如果您不需要线程安全:

如果字符串在编写代码之前已知，并且由于某些原因需要多次运行相同的代码，请使用“+”运算符，因为编译器会在编译时进行优化和处理。

如果只需要连接两个字符串，请使用concat()方法，因为它不需要创建StringBuilder/StringBuffer对象。鸣谢@nickb。

如果需要连接多个字符串，请使用StringBuilder。

- Rusheel Jain

Answer 3

加入非常长的字符串列表，通过从头到尾简单地将它们添加起来是非常慢的：填充缓冲区逐渐增长，并且一遍又一遍地重新分配，导致额外的复制（并且大量使用垃圾回收器）。

连接长列表最有效的方法是始终从所有其他候选对中总长度最小的相邻字符串对开始连接；然而，这将需要进行复杂的查找以找到最佳对（类似于汉诺塔问题），仅为了将副本数量减少到最少会减慢速度。

您需要一个聪明的算法，使用“分而治之”的递归算法和一个很好的启发式算法，它非常接近于这个最优解。

1. 如果没有字符串需要连接，则返回空字符串。
2. 如果只有一个字符串需要连接，就直接返回它。
3. 否则，如果只有两个字符串需要连接，则将它们连接起来并返回结果。
4. 计算最终结果的总长度。
5. 然后确定要从左边连接多少个字符串，直到达到总长度的一半，以确定“分割点”，将字符串集分成两个非空部分（每个部分必须包含至少一个字符串，分割点不能是要连接的字符串集中的第一个或最后一个字符串）。
6. 如果最小部分包含至少两个字符串，则连接最小部分，否则连接其他部分（使用此算法递归地进行连接）。
7. 回到开始（1.）以完成其他连接。

请注意，集合中的空字符串必须被忽略，就像它们不是集合的一部分一样。

许多库中默认的String.join（字符串表，可选分隔符）实现是缓慢的，因为它们使用从左到右的单调增连接。当你需要连接许多小字符串以生成一个非常大的字符串时，以上的分治算法会更快。

这种情况并不罕见，它发生在文本预处理器、生成器或HTML处理中（例如在“Element.getInnerText()”中，当元素是包含许多由许多命名元素分隔或包含的文本元素的大型文档时）。

以上策略适用于源字符串全部（或几乎全部）都要被垃圾收集以仅保留最终结果的情况。如果结果与源字符串列表一样长，则最佳选择是仅为其总长度分配一次最终大缓冲区，然后从左到右复制源字符串。

在两种情况下，这都需要对所有字符串进行第一遍扫描以计算它们的总长度。

如果使用可重新分配的“字符串缓冲区”，则如果“字符串缓冲区”不断重新分配，则无法很好地工作。但是，在执行第一遍扫描时，字符串缓冲区可能很有用，可以将一些短字符串预连接到其中，其合理（中等）大小为4KB（一页内存）：一旦它满了，请将子集的字符串替换为字符串缓冲区的内容，并分配一个新的字符串缓冲区。

这可以显著减少源集中小字符串的数量。第一遍后，您将得到为结果分配的总长度，其中您将逐步复制第一遍收集到的所有剩余中等大小的字符串。当源字符串列表来自解析器函数或生成器时，此方法非常有效，因为在解析/生成结束之前，总长度是未知的：您只会使用中等大小的中间字符串缓冲区，最终生成最终缓冲区，而无需重新解析输入（以获取许多增量片段）或反复调用生成器（这将很慢，或者对于某些生成器或如果从解析器的输入消耗并且不能从头开始恢复，则无法正常工作）。

请注意，这个备注不仅适用于连接字符串，也适用于文件I/O：逐步写入文件也会受到重新分配或碎片化的影响：您应该能够预计生成的文件的总最终长度。否则，您需要一个经典的缓冲区（在大多数文件I/O库中实现，通常在内存中大小约为4KB的一页，但您应该分配更多，因为文件I/O速度较慢，并且当文件片段以过小的单位“簇”的形式递增分配时，碎片化变成了后续文件访问的性能问题；使用约1MB的缓冲区将避免由文件系统上的碎片化分配引起的大多数性能问题，因为片段将变得相当大；像NTFS这样的文件系统被优化为支持高达64MB的片段，超过这个大小，碎片化不再是一个明显的问题；对于Unix/Linux文件系统也是如此，它们倾向于仅对最大片段大小进行碎片整理，并且可以使用按2的幂组织的自由簇池有效地处理小片段的分配，例如1个簇、2个簇、4个簇、8个簇...，因此整理这些池是简单直接且成本不高的，并且可以在后台异步完成，当有低水平的I/O活动时进行。

在所有现代操作系统中，内存管理与磁盘存储管理相关联，使用内存映射文件来处理缓存：内存由存储支持，由虚拟内存管理器管理（这意味着您可以分配比物理RAM更多的动态内存，其余部分将在需要时分页到磁盘）：您用于管理非常大的缓冲区的策略往往与页面的I/O性能有关：使用内存映射文件是一个好的解决方案，并且现在可以在非常大的（虚拟）内存中完成所有与文件I/O相关的工作。

- verdy_p