字符串驻留（String Interning）真的有用吗？

Question

字符串驻留（String Interning）真的有用吗？

21

我曾经谈论过字符串和各种编程语言，其中涉及到了字符串内部化。显然，Java和.NET框架会自动对所有字符串进行内部化，同时还有几种脚本语言也是如此。理论上来说，它可以节省内存，因为你不需要多次复制相同的字符串，而且它还可以通过简单的指针比较而不是O(N)遍历每个字符来节省时间，从而实现字符串相等性比较。

但是，我越想越怀疑这个概念的好处。在我看来，优点大都是理论上的：

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

这只是我考虑实现细节的结果。我有什么遗漏吗？在一般情况下，字符串插值是否真的提供了任何重大好处？

编辑2：好吧，显然我从一个错误的前提出发。我谈话的对象从未指出新创建的字符串是可选的字符串插值，并且实际上给人留下了相反的印象。感谢Jon澄清此事。他的另一个答案也被接受。

- Mason Wheeler

2

你为什么认为将新字符串与字符串池表进行比较是O(N)操作？ - Paul Sonier

3

有趣的问题。我不同意O(N)的说法，因为intern表可以是字典。 - Andrey

6

Java 不会对所有字符串执行这个操作——只针对所有的字符串_字面值_ ，这些字面值可以在编译时确定并作为类加载的一部分设置，因此几乎没有运行时成本。新的 String 对象不会被放入常量池中；代码必须显式地调用 intern() 方法才能将它们放入其中。因此，您的代码可以决定是否适合使用常量池，并选择使用或不使用。常量池中的字符串不算强引用，因此不会妨碍垃圾回收。 - Andrew Janke

1

我有一种感觉，很难说出实现interning和immutability哪个是先有的，哪个是后有的。使字符串成为不可变的有其原因，其中一个有用的好处可能是interning，但这可能不是主要原因。 - Andrey

4

“O(N)操作。（编辑：其中N是字符串的大小，而不是表格的大小，因为这让人感到困惑。）”之所以令人困惑，是因为字符串的长度很少适用于字符串池化（interning），因为哈希值只计算一次，与字符串的大小无关。” - S.Lott

显示剩余5条评论

7个回答

6

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

这是真的，在Java中字符串是不可变的。我不确定这是否是一件坏事。不谈论不变性与可变性，我认为这是一个很好的设计，因为缓存和更简单的东西等等。

每次创建新字符串时，都必须检查它是否在字符串驻留表中，这至少是O（N）操作。因此，除非字符串相等比较与新字符串创建的比率相当高，否则节省的净时间可能不是正值。

并不完全是O（n）。您可以使用哈希映射或其他数据结构，将其带到接近恒定的查找。

如果字符串相等性表使用强引用，那么当字符串不再需要时，它们将永远不会被垃圾回收，从而浪费内存。另一方面，如果表使用弱引用，则字符串类需要某种终结器来将字符串从表中删除，从而减慢GC进程。（这可能非常显着，具体取决于字符串intern表的实现方式。最坏情况下，根据特定情况，从哈希表中删除条目可能需要O（N）重建整个表。）

你说得对，我同意你的观点。除了我认为GC处理是微不足道的。从长远来看，好处比垃圾收集器多做一次检查要有用得多。我不确定你所说的从哈希表中删除O（n）的含义。大多数哈希表操作都是O（1）。

因此，总之，我认为你的假设大多数操作是线性的。但查找字符串更接近于恒定时间。因此，这种方法将几乎不会损失性能，但获得巨大的内存优势。我认为这是值得的。

这里有一句很好的引用，解释了Java是如何通过“interning”来节省内存并加快测试相等性的速度。

当在一个String对象上调用intern()方法时，Java会对一个已经被interned的String表进行查找。如果表中已经存在一个内容相同的String对象，则返回该表中的String引用。否则，将该String添加到表中，并返回对它的引用。

- Amir Raminfar

1

问题是“字符串内部化真的有用吗？”。你的回答并没有真正回答这个问题，看起来更像是扩展评论。 - Andrey

我还在编辑，但是我的答案是：牺牲 CPU 损失来换取更大的内存增益。投票结果显示它是有用的。 - Amir Raminfar

不要认为有真正的内存增益。只有字符串字面量才能进入国际表。如果我的代码中有重复的字符串值，我会将它们提升为常量，这基本上是相同的。字符串的不可变性会使堆积满了短暂的对象，因此我认为在性能方面没有真正的好处。 - Andrey

我不确定你的意思，因为如果你进行大量字符串操作，并且虚拟机中只有一个该字符串的副本，那么我认为会有一定的内存收益。此外，维基引用了“将字符串合并使得某些字符串处理任务更加时间或空间高效”。你是不是在说收益没有人们想象的那么多？ - Amir Raminfar

我不确定你所说的从哈希表中删除的O(n)是什么意思。大多数哈希表操作都是O(1)。是的，大多数操作都是如此。但是，如果您有两个键散列到表中的同一位置，并且冲突解决涉及将其中一个放在其他地方，然后去掉正确位置的那个，查找现在对于另一个就无法正常工作，除非您重新散列它。这通常涉及重建整个表。 - Mason Wheeler

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.

如果你intern()第一个值并且必须intern()一个值来进行比较。

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

打印

The average time for equals() was 258 ns.

这是一个常见情况，你经常有一个你知道是interned的值和一个输入的第二个值，它没有被intern'ed。

如果你只使用intern'ed字符串并对其进行==比较，并且不考虑成本，则会打印

The average time for equals() was 4 ns.

如果你需要进行数百万次比较，那么intern()方法会快得多。然而，对于少量比较而言，虽然可以节省8纳秒的时间，但可能会增加250纳秒的成本。

避免使用intern()方法，改用equals()方法可能更简单。

- Peter Lawrey

1

好观点。必须通过实习来“节省”等于检查是不可行的。仅当您需要具有大量读取并完全控制键的映射时，才明智地进行内部化...在这种情况下，您可能可以直接对它们进行==操作，而无需填充内部表。 - Ajax

如果您的瓶颈是内存，而且有很多重复的字符串。在这种情况下，为了保留工作内存而花费更多的 CPU 资源将会在用户体验方面得到回报...但是，这只是一个边角案例，不应影响一般使用。 - Ajax

3

以下是Python 文档的解释：

sys.intern(string)

将字符串添加到“内部化”字符串表中，并返回该内部化字符串——即字符串本身或其副本。内部化字符串可用于在字典查找时提高一些性能——如果字典中的键和查找键都是内部化的，则在哈希后进行键比较时可以使用指针比较而不是字符串比较。通常，Python程序中使用的名称会自动内部化，并且用于保存模块、类或实例属性的字典具有内部化的键。

内部化字符串并非不朽；您必须保留intern()的返回值的引用才能从中受益。

- Steven Rumbalski

-1

字符串驻留（interning）在一般情况下是否真的提供了任何显著的好处呢？

是的。它非常重要。在Java中尝试一下。

编写简单的测试，比较使用和不使用字符串驻留的数千个半随机字符串的相等性。

a.equals( b )  is slow

a == b is fast.

- S.Lott

是的，但那正是我的观点。有几种字符串操作，其中只有相等比较受益于此。你有多经常使用字符串相等比较？ - Mason Wheeler

@Mason Wheeler：经常使用。事实上，我很少使用其他任何东西。"排序"相对较少，我尽量设计避免使用它。 - S.Lott

@Peter Lawrey：因此建议使用“半随机”字符串。我们进行了一项比较，使用了20,000个金融账户，这些账户有8或9个字符，并且有各种长度的重复模式。“随机”的数据不是用于测试任何东西的现实数据。 - S.Lott

1

@S. Lott，我进行了性能测试，比较了8-9个字符的半随机字符串，使用==与equals相比可以节省15纳秒，但使用intern()会花费250微秒。 - Peter Lawrey

@Peter Lawrey：“要重复比较已经使用intern()的字符串是相当罕见的”。有趣的是，这不是我们的经验。我重写了现有的Java应用程序以使用intern()，并获得了显着的加速效果。看起来你确实有一个问题在心中。这个问题似乎是与interns相关的基准测试问题。由于你一直在重复你的说法，这听起来像是一个问题的基础。 - S.Lott

显示剩余3条评论

-1

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

如果你经常使用哈希映射，那么不可变性非常重要。
字符串组合操作本来就很慢，因为你必须不断重新分配包含字符的数组。
另一方面，subString() 操作非常快。
字符串相等确实经常被使用，你在这里没有失去任何东西。原因是字符串并没有自动地被内部化。事实上，在Java中，如果引用不同，equals() 会回退到逐个字符比较。
显然，对于内部表使用强引用并不是一个好主意。你必须承受GC开销。
Java字符串处理旨在节省空间，特别是对于常量字符串和子字符串操作。

总的来说，在大多数情况下，这是值得的，并且与VM管理的堆概念非常契合。虽然我可以想象一些特殊情况可能会让人非常痛苦。

- biziclop

Java 7上的子字符串速度较慢... Java6及以下版本返回指向原始字符串char[]的字符串对象（从而泄漏内存）。现在，7也会为子字符串创建不可变数组副本；这是一些运行时数据，但可以减少内存使用。Intern()也是同样的道理；让==生效很难（两个字符串都必须被interned），但如果你有2^20个字符串，interning将节省你的堆，并在要求高的情况下具有更高的性能。 - Ajax

-1

当你需要比较来自有限集合的字符串（1）多次时，字符串池化非常有用（2）。

然后，通过能够快速执行 == 而不是 equals（）的好处，超过了池化字符串的开销。

这样做有时比使用依赖于 hashCode（）和 equals（）调用的 HashMap 更快。

- rustyx

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

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

- Jon Skeet · Accepted Answer

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

并不是每次创建新字符串时都会这样做。

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

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

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