在处理大量字符串数据时,性能优化变得尤为重要。字符串池化是提升字符串比较性能的一种有效策略。本文将探讨字符串池化的概念、机制,并展示如何在.NET CLR中实现字符串池化,以及通过实验验证其对字符串搜索性能的提升。
字符串池化是指在字符串池中为每个唯一的字符串保留单一副本。在.NET CLR中,字符串池是通过哈希表实现的,其中键是字符串的哈希值,值是对实际字符串对象的引用。如果一个字符串在程序中出现100次,池化将确保只分配一次该字符串的内存。此外,当需要比较字符串时,如果它们已经被池化,只需要进行引用比较即可。
以下是一个字符串池化的示例,为了演示目的,显式地对字符串字面量进行了池化。
var s1 = string.Intern("stringy");
var s2 = string.Intern("stringy");
var s3 = string.Intern("stringy");
在上述代码中,"stringy"被哈希并查找池中是否存在该哈希值。如果不存在,则创建一个"stringy"对象的副本,并在池化哈希表中创建一个新条目,键是"stringy"的哈希值,值是对"stringy"副本的引用。如果应用程序不再引用原始的"stringy",则GC可以回收该内存。
字符串的不可变性是一个经典的例子。考虑以下代码:
var s1 = "stringy";
s1 += "new string";
当执行第二行代码时,"stringy"对象被取消引用并留给垃圾回收,而s1则指向新的字符串对象"stringy new string"。字符串池化之所以有效,是因为CLR明确知道引用的字符串对象不能改变。
在.NET中,提供了两个静态字符串方法:
尽管字符串字面量(不是在代码中生成的)会自动池化,但CLR版本在这方面的行为有所不同,因此如果期望字符串被池化,最好在代码中显式地进行。
为了提供一些数字来帮助探索字符串池化的潜在收益,在旧i5 Windows 10 PC上运行了一些定时测试。测试设置如下:
测量了填充每个集合所需的时间,以及搜索已知搜索项所需的时间,精确到毫秒。
在下面的图1中,绘制了添加的字符串数量与添加这些随机生成的字符串所需的时间之间的关系。显然,在添加操作中,使用HashSet
当使用字符串池化填充List
图1:使用随机字符串填充List
图2显示了搜索已知字符串所需的时间。对于这些集合大小,所有时间都非常小,但增长趋势是清晰的。
图2:搜索已知字符串所需的时间,该字符串是最后添加的
正如预期的那样,HashSet是O(1),而其他是O(N)。不使用池化的搜索明显在所需时间上增长得更快。
HashSet