字符串驻留真的有用吗？

Question

我之前和别人聊到字符串和各种编程语言的时候，提到了一个叫做字符串驻留的概念。听说Java和.NET框架会自动处理所有字符串，还有一些脚本语言也是这样。理论上，这样做可以节省内存，因为不会出现多个相同字符串的副本，同时也能节省时间，因为比较字符串是否相等只需要比较指针，而不是逐个字符地比对，这样效率更高。

不过我越想越觉得这个概念的好处并没有那么明显。我的感觉是，这些好处大多只是理论上的：

• 首先，要使用自动字符串驻留，所有字符串都必须是不可变的，这样会让很多字符串处理的任务变得比必要的要复杂。（我知道关于不可变性的各种论点，但这不是重点。）
• 每次创建一个新字符串时，都需要检查这个字符串是否在驻留表中，这至少是一个O(N)的操作。（编辑：这里的N是字符串的大小，而不是表的大小，因为这个容易让人混淆。）所以，除非字符串相等比较的次数远远高于新字符串的创建次数，否则节省的时间可能是负值。
• 如果字符串驻留表使用强引用，那么当这些字符串不再需要时，它们就不会被垃圾回收，这样会浪费内存。另一方面，如果表使用弱引用，那么字符串类就需要某种方式来移除表中的字符串，这样会拖慢垃圾回收的过程。（这可能会很严重，具体取决于字符串驻留表的实现方式。在最坏的情况下，从哈希表中删除一个项目可能需要O(N)的时间来重建整个表。）

这些只是我对实现细节的思考。难道我遗漏了什么吗？在一般情况下，字符串驻留真的能带来显著的好处吗？

编辑 2：好吧，看来我之前的理解有误。我和对方聊天时，他并没有指出字符串驻留对于新创建的字符串是可选的，反而给人一种相反的印象。感谢Jon帮我澄清了这个问题。又一个被接受的答案给他。

Answer 1

这里是关于python的一个文档的内容：

sys.intern(string)

这个函数的作用是把一个字符串放进一个叫“interned”的字符串表里，并返回这个字符串本身或者它的一个副本。把字符串进行“interning”处理可以让字典查找变得更快——如果字典里的键都是经过intern处理的，而你要查找的键也是经过intern处理的，那么在比较这些键的时候，可以通过指针比较来完成，而不是逐个字符比较。通常，Python程序中使用的名字会自动进行intern处理，而用来存放模块、类或实例属性的字典也会使用intern处理过的键。

不过，intern处理过的字符串并不是永远存在的；你需要保留对intern()返回值的引用，才能真正享受到它带来的好处。

Answer 2

首先，要使用自动字符串驻留，所有字符串必须是不可变的，这使得很多字符串处理任务变得比需要的更复杂。（没错，我听过关于不可变性的各种论点，但这不是重点。）

这是真的，Java中的字符串是不可变的。我不确定这是不是坏事。不讨论不可变和可变的区别，我觉得这是个很好的设计，因为它能缓存数据，还能简化很多事情，我就不详细说了。

每次创建一个新字符串时，都必须检查它是否在字符串驻留表中，这至少是一个O(N)的操作。所以，除非字符串相等比较和新字符串创建的比例很高，否则节省的时间不太可能是正值。

其实不完全是O(N)。你可以使用哈希表或其他数据结构，这样查找的时间几乎是常数级别的。

如果字符串相等表使用强引用，那么当字符串不再需要时，它们永远不会被垃圾回收，这样就浪费了内存。另一方面，如果表使用弱引用，那么字符串类就需要某种终结器来从表中移除字符串，这样会减慢垃圾回收的过程。（这可能会很显著，具体取决于字符串驻留表的实现。在某些情况下，从哈希表中删除一个项目可能需要O(N)的时间来重建整个表。）

你说得对，我同意你的看法。不过我觉得垃圾回收的处理影响不大。从长远来看，带来的好处远远超过了垃圾回收器多做一次检查的影响。我不太明白你说的从哈希表中删除是O(N)是什么意思。大多数哈希表的操作都是O(1)。

所以总结一下，我认为你假设大多数操作是线性的，但查找字符串更接近常数时间。因此，这种方法的性能损失可以忽略不计，但内存的节省却是巨大的。我认为这是值得的。

这里有一个不错的引用，讲述了实际发生了什么，以及它是如何节省内存的。

为了节省内存（并加快相等性测试），Java支持字符串的“驻留”。当对一个字符串调用intern()方法时，会在一个驻留字符串的表中进行查找。如果表中已经有一个内容相同的字符串对象，就返回表中该字符串的引用。否则，就将这个字符串添加到表中，并返回它的引用。

Answer 3

不，Java和.NET并不是“自动对所有字符串”这样做的。它们（其实是Java和C#）只对在字节码/IL中表示的常量字符串表达式这样做，或者通过String.intern和String.Intern（.NET）方法按需进行处理。在.NET中的具体情况很有趣，但基本上C#编译器会确保在一个程序集内对相同字符串常量的每次引用都指向同一个字符串对象。这可以在类型初始化时高效完成，从而节省大量内存。

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

（关于字符串不可变性，我个人非常高兴字符串是不可变的。我不想每次接收到参数时都要复制一份，谢谢你。我也没发现这让字符串处理变得更难……）

而且正如其他人指出的，在哈希表中查找字符串通常不是O(n)的操作，除非你在哈希碰撞上非常不幸运……

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