字符串实习真的很有用吗？

Question

我不久前正在谈论字符串和各种语言,并且出现了字符串实习的主题.显然,Java和.NET框架会自动执行所有字符串以及多种脚本语言.从理论上讲,因为你不相同的字符串的多个副本,最终可以节省内存,这样可以节省时间,因为字符串相等比较是一个简单的指针比较,而不是一个O(N)通过串的每个字符运行.

但是我越是想到它,我越是怀疑这个概念的好处.在我看来,优势主要是理论上的:

• 首先,要使用自动字符串实习,所有字符串必须是不可变的,这使得许多字符串处理任务比它们需要的更难.(是的,我听说过所有关于不变性的论点.这不是重点.)
• 每次创建新字符串时,都必须根据字符串实习表检查它,这至少是O(N)操作.(编辑:.其中N是字符串的大小,表的不是大小,因为这是令人困惑的人)所以,除非字符串相等比较,新的字符串创建的比例是相当高的,这是不可能的,节省的净时间正值.
• 如果字符串相等表使用强引用,那么当不再需要字符串时,它们将永远不会被垃圾收集,从而浪费内存.另一方面,如果表使用弱引用,则字符串类需要某种终结器来从表中删除字符串,从而减慢GC进程的速度.(这可能是相当显著,取决于字符串实习生表是如何实现的.最坏的情况下,删除从哈希表中的项目可能需要的O(N)的重建在某些情况下整个表的.)

这只是我思考实现细节的结果.有没有我错过的东西？在一般情况下,字符串实习是否实际上提供了任何显着的好处？

编辑2:好吧,显然我是在错误的前提下操作的.我正在谈话的人从未指出字符串实习对于新创建的字符串是可选的,事实上给人的印象是相反的情况是正确的.感谢Jon直接解决问题.另一个接受他的答案.

Answer 1

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

它不会发生在每次创建一个新的字符串的时间.

(在字符串不变性方面,我非常高兴字符串是不可变的.我不希望每次收到参数等都要复制一份,非常感谢.我还没有看到它制作字符串处理任务更难,要么...)

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

我个人不在用户土地代码中使用字符串实习; 如果我想要某种字符串缓存,我会创建一个HashSet<string>或类似的东西.这对于您希望多次遇到相同字符串的各种情况(例如XML元素名称)非常有用,但是使用简单集合时您不会污染系统范围的缓存.

Answer 2

首先,要使用自动字符串实习,所有字符串必须是不可变的,这使得许多字符串处理任务比它们需要的更难.(是的,我听说过所有关于不变性的论点.这不是重点.)

这是真的,字符串在Java中是不可变的.我不确定这是不是坏事.没有进入不可变对可变,我喜欢认为这是一个伟大的设计,因为缓存和更多的简单,我不会接受.

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

不完全是O(n).您可以使用哈希映射和/或其他数据结构来实现近乎不变的查找.

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

你是对的,我同意你的意见.除了我觉得GC处理而且可以忽略不计.从长远来看,这些好处比让垃圾收集器进行额外检查更有用.我不确定你从哈希表中删除O(n)的意思.哈希表上的大多数操作都是O(1)

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

这是关于实际发生的事情以及如何节省内存的一个很好的引用.

为了节省内存(并加快测试是否相等),Java支持字符串的"实习".在String上调用intern()方法时,将对实习字符串表执行查找.如果表中已存在具有相同内容的String对象,则返回对表中String的引用.否则,将String添加到表中,并返回对它的引用.