1. 首頁 > 生活百科 > >

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

生活百科

[算法2-數組與字符串的查找與匹配] （.NET源碼學習）關鍵詞：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）默認情況下，圖片與文字的關系：圖片下方，是該幅圖片的解釋 。
【.NET源碼學習 [算法2-數組與字符串的查找與匹配]】（6）文末“ [ # … ] ”的部分僅作補充說明，非主題（算法）內容，該部分屬于 .NET 底層運行邏輯，有興趣可自行參閱 。
（7）本文內容基本為本人理解所得 ， 可能存在較多錯誤 ， 歡迎指出并提出意見，謝謝 ?！?br /> 一、有關數組(一) 二分查找及相關優化關于二分的相關內容，在本人的這篇文章中（LC T668筆記 & 有關二分查找、第K小數、BFPRT算法 - PaperHammer - 博客園 (cnblogs.com)）有較為詳細地論述 ， 詳情請參閱 。
在此，僅總結一下二分的要點：
1. 二分集合須保證有序 。有序是二分的前提 ， 在二分前須明確二分的對象 ， 該對象必須具有有序性 。
2. 確定搜索區間形式（閉區間、左閉右開、左開右閉） 。不同區間形式，循環條件與最終返回值不同；同時也應用于不同的場景 。
3. 盡量寫或想清楚所有的if…else… ， 清楚地展現出所有細節，避免不必要的紕漏與麻煩 。
(二) 有關方法BinarySearch()的源碼該方法的主要實現形式是雙指針或折半查找，詳細內容在本人之前的文章（[數據結構1.2-線性表] 動態數組ArrayList（.NET源碼學習） - PaperHammer - 博客園 (cnblogs.com)）中，詳情請參閱 。
二、有關字符串(一) .NET中的String與C#中的string1. 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#中的關鍵字 ， 可以將其用作變量名 。

.NET源碼學習 [算法2-數組與字符串的查找與匹配]

推薦閱讀