关键词：1. 数组查找（算法）   2. 字符串查找（算法）   3. C#中的String（源码）   4. 特性Attribute 与内在属性（源码）   5. 字符串的比较（底层原理）   6. C#中的StringComparsion（源码）   7. 字符串与暂存池（底层原理）

【注：本人在写文章时遇到认为有必要或想要展开的点就会将其并入文章中，避免事后遗忘。因此非主题内容可能会比较多，篇幅也可能比较大，各位学者在浏览时可以自行转跳到感兴趣的部分进行阅览，存在相关问题或建议，欢迎留言指导，谢谢！】

查找，大体上可以分为两类：数组查找、字符串查找。其中数组查找以二分为主；字符串查找以BK、BM、KMP三类算法为主。由于二分在之前的文章中已经详细叙述过，在此不再重复论述。故本文主要以有关字符串的查找为重点，附带.NET关于String类型及相关底层逻辑的源码分析为主，进行论述。

【# 请先阅读注意事项】

【注：

（1）文章篇幅较长，可直接转跳至想阅读的部分。

（2）以下提到的复杂度仅为算法本身，不计入算法之外的部分（如，待排序数组的空间占用）且时间复杂度为平均时间复杂度。

（3）除特殊标识外，测试环境与代码均为.NET 6/C# 10。

（4）默认情况下，所有解释与用例的目标数据均为升序。

（5）默认情况下，图片与文字的关系：图片下方，是该幅图片的解释。

（6）文末“ [ # … ] ”的部分仅作补充说明，非主题（算法）内容，该部分属于 .NET 底层运行逻辑，有兴趣可自行参阅。

（7）本文内容基本为本人理解所得，可能存在较多错误，欢迎指出并提出意见，谢谢。】

一、有关数组

(一) 二分查找及相关优化

关于二分的相关内容，在本人的这篇文章中（LC T668笔记 & 有关二分查找、第K小数、BFPRT算法 - PaperHammer - 博客园 (cnblogs.com)）有较为详细地论述，详情请参阅。

在此，仅总结一下二分的要点：

1. 二分集合须保证有序。有序是二分的前提，在二分前须明确二分的对象，该对象必须具有有序性。

2. 确定搜索区间形式（闭区间、左闭右开、左开右闭）。不同区间形式，循环条件与终返回值不同；同时也应用于不同的场景。

3. 尽量写或想清楚所有的if…else…，清楚地展现出所有细节，避免不必要的纰漏与麻烦。

(二) 有关方法BinarySearch()的源码

该方法的主要实现形式是双指针或折半查找，详细内容在本人之前的文章（[数据结构1.2-线性表] 动态数组ArrayList（.NET源码学习） - PaperHammer - 博客园 (cnblogs.com)）中，详情请参阅。

二、有关字符串

(一) .NET中的String与C#中的string

1. C#是区分大小写的语言，所以string与String理论上是不同的，但在编译器的定义导航中，却将这两个类型均导航至同一个类——类String。

2. 据现有资料可知，String是.NET（以前称为.NET Framework）中的类，string是C#中的类。在C#中使用string时，编译器会将string自动映射到.NET中的String，同时调用的方法也是.NET中类String内部的方法。据该原理，使用String可以在一定程度上减少编译器的工作量，但微软官方不建议这样，依旧建议使用string以符合相关规范。其他基本数据类型也是如此，如short映射Int16，int映射Int32，long映射Int64，double映射Double等。

3. 这样做的原因个人猜测可能如下：.NET是一套底层运行规范，其需要对所有支持的语言定义一个通用的规则（CLS通用语言规范Common Language Specification）不同语言语法的不同，.NET通过CLS提供了公共的语法，不同语言经过IL的翻译生成对应的.NET语法。如F#中的let赋值语句（let str = “.NET”;;）；VB中的String（Dim 变量名 As String = “.NET”）；加上现在C#中的string。它们都是基于.NET运行的，所以需要有一个总纲来规范化，使得每个语言具有独特性的同时，可以实现相同或相近的功能。因此在.NET中定义了类String，无论时哪种语言，只要编译时需要使用.NET，均须遵守其相关规范，将独特的风格转换为统一且通用的规范化表达。

4. 因此，String不是C#中的关键字，可以将其用作变量名。

(二) 有关类String

String类位于命名空间System中，是一个公共密封类，继承了许多接口，其中“的”有：IComparable用于字符串间的比较；IEnumerable用于迭代器的遍历。其内部包含2个属性，3个字段，1个结构（体），3种运算符的重载方法，9个构造方法和一堆其他方法（真的太多了）。

1. 两个属性

首先是索引器，可以发现这是一个以int为索引，char为返回值的只读索引器。对比其他数据类型的索引器，如之前文章提到的动态数组ArrayList

不难发现，String中的索引器只读不能写，因此经常头昏会写出这样的代码：

同时，String类中的索引器还是一个extern属性，说明其支持在外部根据不同的需求重新定义新的索引器。

第二个数Length属性，其内部包含了一个get_Length()方法，用于返回字符串的长度（调用的时候，不用在后面加括号，且个字母大写）。

可以看到，这里都出现了Intrinsic和MethodImpl及其相关内容，这两个内容会在文末进行补充说明。

2. 三个字段

string.Empty用于初始化字符串为空。这里对四种初始化方式：（省略前缀string）str = null；str = “”；str = string.Empty；str = new()进行分析。

（1）对于str = null，理论上这种方式不能称之为常规意义上的初始化，因为赋值为null并没有在堆上分配，仅是在栈上分配了空间，依然不可直接使用，因为变量不引用内存中的任何对象。这种方式，相当于只定义了一个变量并未对其赋值，在使用前必须先赋值。

（2）对于str = “”与str = string.Empty，其初始化并在内存空间堆与栈上都进行分配，将其赋值为空。其在基本用法和性能上并没有较大差异。

据测试后可知，即使已存在一个空字符串，用以上两种方法继续进行定义变量，均不会重新申请新的内存空间，而是每次去指向固定的静态只读内存区域。

据CLR中的相关信息及本人的理解，二者仅仅在优化方面稍有差别，string.Empty是C#对""在语法级别的优化。也就是说，""是通过CLR（Common Language Runtime公共语言运行库）进行优化的，CLR会维护一个字符串池，以防在堆中创建重复的字符串。而string.Empty是一种C#语法级别的优化，是在C#编译器将代码编译为IL(即MSIL)时进行了优化，即所有对string类的静态字段Empty的访问都会被指向同一引用，以节省内存空间。

还有两外两个字段。这两字段从命名来看，一个变量存储的是字符串的长度；另一个存储的是个字符。有关二者的应用及更多内容，会在之后的某些方法中进一步解释。

3. 一个结构（体）

该结构体派生自类object下的类ValueType，从父类来看应该是用于存储某些数据类型间的映射关系。（下方翻译来自Microsoft Bing）

4. 三种运算符重载

首先是运算符“==”和“!=”。对于两个字符串的比较，类String内部从新定义了比较规则，即重载了判断运算符，使用判断运算符就相当于调用类String内部的Equals()方法。因此，对于字符串而言，使用“==”和方法Equals()进行比较，是完全等价的。

一般地，对于运算符“==”和Equals()方法，在比较方式上还是有所差异。

（1）对于值类型和字符串，这两种方式均只比较内容；

（2）对于除字符串以外的引用类型，运算符”==”比较的是在栈中的引用（是否指向同一个对象）；方法Equals()比较的是在堆中的内容（是否是同一个对象的引用）。

但这样就有一个问题，我们知道C#对于字符串有某些优化。一般地，内容相同的字符串不会开辟新的堆空间，而是指向储存在暂存池（堆的一部分，Java中称为常量池）中的对象。但以某些方式创建的字符串对象，并不会检查暂存池，而是直接在堆中开辟新空间，导致内容相同的字符串，栈和堆的地址均不同。那么这样是否会导致判断运算符和方法Equals()出现问题呢？有关该部分的详细内容请转到文末的 [# 有关字符串的比较与暂存池]

其次是ReadOnlySpan<T>。这是一种较为特殊的运算符重载，其中关键字implicit用于声明隐式的自定义类型转换运算符。它可以实现2个不同类型的隐式转换，提高代码的可读性。但是使用隐式转换操作符之后，在编译时会跳过异常检查，所以在使用隐式转换运算符前，应当在一定程度上确保其不会引发异常并且不会丢失信息，否则在运行时会出现一些意外的问题。该隐式转换，是将string类型转换成ReadOnlySpan<char>类型。

先简单介绍一下类型Span<T>

该类型被微软官方称为“新增的重要组成部分“，其主要作用是提供任意内存连续区域的类型安全与内存安全表示形式。即，此数据类型可以实现对任意内存的相邻区域进行操作，无论相应内存是与托管对象相关联，还是通过互操作由本机代码提供，亦或是位于堆栈上。解决了在不使用不安全代码（指针等直接对内存进行的操作）的情况下，实现了在内存上，对数据进行修改的操作。更多详细信息请参阅（C# - Span 全面介绍：探索 .NET 新增的重要组成部分 | Microsoft Docs）。

ReadOnlySpan<T>亦是如此，只是被附上了对内部元素只读的属性，以满足字符串不可修改的基本性质。

其将传入的字符串首字符作为指针的起始位置，length为字符串的长度，通过指针+偏移量的方式（类似于C++中通过指针ptr访问数组个位置，ptr++实现向后偏移），实现对数据的访问。

5. 九个构造方法

与其他类型的构造方法不同，这九个构造方法均为外部方法extern，需要从外部从新定义其实现形式。个人猜测，外部定义可能在.NET库中。其功能均是将所给数据集，按照一定条件转化为字符串。详细信息参考下表：

(三) 有关String的查找与匹配

1. BF算法（Brute Force）

Brute Force，一种暴力匹配算法，其思想是对于两个字符串 s 与 ，在s（主串）中查找/匹配pat（模式串）。若s[i] == pat[j]，则i++且j++；否则i++且j = 0。此时 i 即为模式串 pat 在主串 s 中次匹配的起始下标位置。

复杂度分析：

• 时间复杂度：O( nm )（快O( n+ m )，pat 在 s 的开头就匹配完成；慢O( nm )，每次都是在 pat 的末尾匹配失败）

• 空间复杂度：O( 1 )

我们找个题目测试一下其运行效率（题目：kmp算法_牛客题霸_牛客网 (nowcoder.com)）

实测运行时间：

【注：由于牛客上的本题无法获取该超时样例，因此此处及之后选用某一衰减测试样例进行实测计时，仅用于观察算法时间复杂度。样例：主串字符全为 ‘A’，长度为500000；模式串字符全为 ‘A’，长度为100】

毫无疑问，对于这样的时间复杂度， 10⁵ 及以上量级的数据是比较慢的。虽然理论上BF算法时间复杂度较高，但其在实际开发中比较常用原因主要有以下2点：

（1）实际开发中，多数情况下主串与模式串长度不会很长。对于小规模数据，其时间复杂度并不能代表其执行时间，某些情况下，可能比其他优化后的算法更快。因此，尽管理论坏时间复杂度为 O( nm )，但从概率统计上看，多数情况下其效率还是可观的。（打比赛另说）

（2）BF 算法思想简单，实现简单。简单意味着不容易出错，出错也很容易查找修改。工程应用中，在满足性能的前提下，简单是我们的。这也符合 KISS (Keep It Simple and Stupid) 设计原则。

【思考】如果要返回所有匹配的字串首地址，该如何实现？

【参考如下】

2. RK算法（Rabin-Karp）

该算法算是对BF算法的优化，既然比较字符效率不高，那不如换一种比较对象。要转换那就需要保证按照某种规则进行转换，且转换后需要保证性。对于每个字符串，除了它本身外有一种一般情况下的表示方式，哈希值。并且数字的比较效率要比字符高上不少；而且字符要一个一个比较，而哈希值可以代表一个串，所以比较的时候时间复杂度为 O( n )。

简单来说其方法思想是，在主串中每次截取和模式串一样长的字符串，获取二者的哈希值进行比较。

【注：有关.NET/C#中的哈希及其冲突的问题，会在今后的文章的提到，以下均默认不会发生哈希冲突】

获取哈希值有两种方法：

（1）遍历字串中每个字符。这样就会有许多操作：截取、遍历、计算。但反复直接截取并没有优化时间复杂度，反而在一定程度上增加了时间复杂度，因为截取字符串也是一个O(n)级的操作，因此总时间复杂度依旧是O(n²)级。我们好不容易将复杂度降低了一个量级，结果算个哈希又把量级升了回来，得不偿失。

（2）滑动窗口。

根据滑动窗口的原理，获取个串后，之后串的哈希值，可以根据移除前一个，加入后一个来实现，从而将O(n)的时间复杂度降为O(1)。具体实现如下：

复杂度分析：

现在，该算法次计算t的哈希值时，时间复杂度为O( n )；后续计算哈希值因为利用了滑窗的优化只有O( 1 )；比较字符串的Equals()方法，一般地，可以视为O( 1 )。

• 总时间复杂度为O( n )

• 空间复杂度为O( 1 )

这里解释一下为什么两串求得的哈希值相同还要对字符串本身进行比较。当两个串字符类型与数量相同时（如 “aaab”，”abaa” ）以这样的方式进行哈希计算，会得出相同的值，但两个字符串本身并不相同。这也是其缺点：不稳定，过于简单的计算方式或较大的数据量很容易产生哈希冲突。同时，在极端情况下，如果存在大量哈希冲突（哈希值相同，字符串本身并不相同），每次都要比较主串某一部分与模式串，那么RK算法就会退化为BF算法，时间复杂度重回 O( nm )。

同样，再测一下刚才的题

实测时间：

可以发现，RK算法在一定程度上确实比纯暴力得BF算法效率要高，尤其是当主串长度越长时，提升越明显。

【思考】假设有两个以行为优先主序列二维矩阵，如果要返回所有匹配的字串首地址，该如何实现？

【参考如下】

RK算法比较的是字符串的哈希值，那只要获取了对应位置的哈希值，进行比较即可。对于一维，在哈希值转移时只需减去前一个、加上后一个；而二维的转移需根据模式串的规格而定。