21

前段时间我正在讨论字符串和各种语言，字符串实习的话题出现了。显然，Java 和 .NET 框架会自动对所有字符串以及几种脚本语言执行此操作。从理论上讲，它可以节省内存，因为您最终不会得到同一个字符串的多个副本，并且它可以节省时间，因为字符串相等比较是一个简单的指针比较，而不是 O(N) 遍历字符串的每个字符。

但我想得越多，我就越怀疑这个概念的好处。在我看来，优势主要是理论上的：

  • 首先，要使用自动字符串暂留，所有字符串都必须是不可变的，这使得很多字符串处理任务比它们需要的更难。（是的，我听过所有关于不变性的论点。这不是重点。）
  • 每次创建新字符串时，都必须根据字符串实习表检查它，这至少是一个 O(N) 操作。（编辑：其中 N 是字符串的大小，而不是表的大小，因为这让人们感到困惑。）因此，除非字符串相等比较与新字符串创建的比率非常高，否则节省的净时间不太可能是一个正值。
  • 如果字符串相等表使用强引用，则字符串在不再需要时将永远不会被垃圾回收，从而浪费内存。另一方面，如果表使用弱引用，则字符串类需要某种终结器来从表中删除字符串，从而减慢 GC 过程。（这可能非常重要，具体取决于字符串实习生表的实现方式。在最坏的情况下，从哈希表中删除一个项目可能需要在某些情况下对整个表进行 O(N) 重建。）

这只是我思考实现细节的结果。有什么我错过的吗？在一般情况下，字符串实习是否真的提供了任何显着的好处？

编辑 2：好吧，显然我是在错误的前提下进行操作的。与我交谈的人从未指出弦乐实习对于新创建的弦乐是可选的，实际上给人的强烈印象是相反的情况。感谢 Jon 把事情弄清楚了。另一个接受他的答案。

4

7 回答 7

26

不，Java 和 .NET 不会“自动处理所有字符串”。他们（好吧，Java 和 C#）使用以字节码/IL 表示的常量String.intern字符串表达式，并通过和String.Intern（.NET）方法按需执行。.NET 中的确切情况很有趣，但基本上 C# 编译器将保证程序集中对相等字符串常量的每个引用最终都引用相同的字符串对象。这可以在类型初始化时有效地完成，并且可以节省大量内存。

并非每次创建新字符串时都会发生这种情况。

（在字符串不变性方面，我非常高兴字符串是不可变的。我不想每次收到参数时都复制一份，非常感谢。我还没有看到它制作字符串处理任务更难，要么......）

正如其他人所指出的那样，在哈希表中查找字符串通常不是 O(n) 操作，除非您对哈希冲突非常不走运......

就我个人而言，我不在用户区代码中使用字符串实习；如果我想要某种字符串缓存，我会创建一个HashSet<string>或类似的东西。这在您希望多次遇到相同字符串（例如 XML 元素名称）但使用简单集合不会污染系统范围的缓存的各种情况下很有用。

于 2011-07-11T17:31:08.710 回答
6

首先，要使用自动字符串暂留，所有字符串都必须是不可变的，这使得很多字符串处理任务比它们需要的更难。（是的，我听过所有关于不变性的论点。这不是重点。）

这是真的，字符串在 Java 中是不可变的。我不确定这是否是一件坏事。在不涉及不可变与可变的情况下，我喜欢认为这是一个很棒的设计，因为缓存和更多的简单性，我不会进入。

每次创建新字符串时，都必须根据字符串实习表检查它，这至少是一个 O(N) 操作。因此，除非字符串相等比较与新字符串创建的比率相当高，否则节省的净时间不太可能是正值。

不完全是 O(n)。你可以做哈希图和/或其他数据结构，这将使它接近于不断的查找。

如果字符串相等表使用强引用，则字符串在不再需要时将永远不会被垃圾回收，从而浪费内存。另一方面，如果表使用弱引用，则字符串类需要某种终结器来从表中删除字符串，从而减慢 GC 过程。（这可能非常重要，具体取决于字符串实习生表的实现方式。在最坏的情况下，从哈希表中删除一个项目可能需要在某些情况下对整个表进行 O(N) 重建。）

你是对的，我同意你的看法。除了我觉得GC处理和微不足道。从长远来看，这比让垃圾收集器进行额外检查更有用。我不确定从哈希表中删除 O(n) 是什么意思。哈希表上的大多数操作都是 O(1)

总而言之，我认为您假设大多数操作都是线性的。但是查找字符串更接近于一个恒定的时间。因此，这种方法的性能损失可以忽略不计，但内存增益很大。我认为这是值得的。

这是关于实际发生的事情以及它如何节省内存的一个很好的报价。

为了节省内存（并加快相等性测试），Java 支持字符串的“实习”。当对 String 调用 intern() 方法时，会在 interned Strings 表上执行查找。如果表中已存在具有相同内容的 String 对象，则返回对表中 String 的引用。否则，将字符串添加到表中并返回对它的引用。

于 2011-07-11T17:30:14.773 回答
3

这是python文档的看法：

sys.intern(string)

在“interned”字符串表中输入 string 并返回 interned string - 它是字符串本身或副本。留置字符串对于在字典查找中获得一点性能很有用——如果字典中的键被留存，并且查找键被留存，则键比较（在散列之后）可以通过指针比较而不是字符串比较来完成。通常，Python 程序中使用的名称是自动实习的，用于保存模块、类或实例属性的字典具有实习键。

实习字符串不是不朽的；您必须保留对 intern() 的返回值的引用才能从中受益。

于 2011-07-11T17:36:08.793 回答
3

a.equals(b) 对于随机字符串非常快。它仅对于长且相同（或几乎相同）的字符串很慢

Random rand = new Random(1);
String[] list = new String[2000];
for(int i=0;i<list.length;i++)
    list[i] = "1234567"+Long.toString(rand.nextInt(36*37), 36); // semi random
int count = 0;
long start = System.nanoTime();
for(int i=0;i<list.length;i++)
    for(int j=0;j<list.length;j++)
        if (list[i].equals(list[j]))
            count++;
long time = System.nanoTime() - start;
System.out.printf("The average time for equals() was %,d ns.%n", time/list.length/list.length);

在 2.3 GHz 笔记本电脑上打印

The average time for equals() was 19 ns.

如果您实习（）第一个值并且必须实习（）一个值来进行比较

       if (list[i] == list[j].intern())

印刷

The average time for equals() was 258 ns.

这是一种常见的情况，因为您经常有一个您知道是已实习的值，而另一个是输入但未实习的值。

如果您只使用实习字符串和 == 它，并且不计算成本，则打印

The average time for equals() was 4 ns.

如果您进行数百万次比较，这会快很多倍。但是，对于少数比较，您节省了 8 ns，但可能会多花费 250 ns。

避免 intern() 并使用 equals() 可能更简单。

于 2011-07-11T18:14:32.493 回答
0

你列出的点在一定程度上都是有效的。但也有重要的反驳论点。

  1. 不变性非常重要，特别是如果您使用哈希映射，并且它们被大量使用。
  2. 无论如何，字符串组合操作都非常慢，因为您必须不断地重新分配包含字符的数组。
  3. 另一方面，subString()操作非常快。
  4. 字符串相等确实被大量使用，而且你不会在那里丢失任何东西。原因是字符串不会自动实习。事实上，在 Java 中，如果引用不同，则equals()回退到逐字符比较。
  5. 显然，对实习生表使用强引用并不是一个好主意。您必须忍受 GC 开销。
  6. Java 字符串处理旨在节省空间，尤其是在常量字符串和子字符串操作上。

总的来说，我会说在大多数情况下它是值得的，并且非常适合 VM 管理的堆概念。我可以想象一些特殊的场景，但它可能是一个真正的痛苦。

于 2011-07-11T17:42:49.823 回答
0

在一般情况下，字符串实习是否真的提供了任何显着的好处？

是的。它超大。在java中尝试一下。

编写简单的测试，比较 1,000 个半随机字符串的相等性（有无实习）。 

a.equals( b )  is slow

a == b is fast.
于 2011-07-11T17:46:21.373 回答
0

当您需要多次比较有限集 (2) 中的字符串 (1) 时，字符串实习很有用。

然后，能够执行快速==而不是equals().

这样做有时会比使用 a 更快HashMap，后者依赖于hashCode()andequals()调用。

于 2015-04-25T11:56:01.523 回答