[演算法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）默認情況下，圖片與文字的關系：圖片下方，是該幅圖片的解釋，
（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】
毫無疑問，對于這樣的時間復雜度， 105 及以上量級的資料是比較慢的，雖然理論上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(n2)級，我們好不容易將復雜度降低了一個量級，結果算個哈希又把量級升了回來，得不償失，
（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演算法比較的是字串的哈希值，那只要獲取了對應位置的哈希值，進行比較即可，對于一維，在哈希值轉移時只需減去前一個、加上后一個；而二維的轉移需根據模式串的規格而定，
using System; using System.Collections; using System.Collections.Generic; using System.Linq; using System.Text; using System.Numerics; using System.Diagnostics; using System.Runtime.CompilerServices; namespace Common { internal class Program { static IList<int[]> pos = new List<int[]>(); static int m, n; static int p, q; static void Main(string[] args) { Program pg = new(); char[][] s = { new char[]{ 'c', 'a', 'b', 'c' }, new char[]{ 'e', 'f', 'a', 'd' }, new char[]{ 'c', 'c', 'a', 'f' }, new char[]{ 'd', 'e', 'f', 'c' } }; char[][] pat = { new char[]{ 'c', 'a' }, new char[]{ 'e', 'f' } }; m = s.Length; n = s[0].Length; p = pat.Length; q = pat[0].Length; pg.RK(s, pat); foreach (int[] arr in pos) Console.WriteLine("{ " + arr[0] + ", " + arr[1] + " }"); } void RK(char[][] s, char[][] pat) { int patCode = GetHash(pat, 0, 0); int sCode = GetHash(s, 0, 0); for (int row = 0; row <= m - p; row++) { for (int col = 0; col <= n - q; col++) { if (patCode == sCode && ComString(s, pat, row, col)) pos.Add(new int[] { row, col }); if (row < m - p || col < n - q) sCode = NextHash(s, sCode, row, col); } } } int GetHash(char[][] tmp, int row, int col) { int hash = 0; for (int i = row, cntR = 0; cntR < p; i++, cntR++) for (int j = col, cntC = 0; cntC < q; j++, cntC++) hash += tmp[i][j] - 'a'; return hash; } int NextHash(char[][] s, int hash, int row, int col) { if (row < m - p && col == n - q) return GetHash(s, row + 1, 0); for (int i = row, cntR = 0; cntR < p; i++, cntR++) { hash -= s[i][col] - 'a'; hash += s[i][col + q] - 'a'; } return hash; } bool ComString(char[][] s, char[][] pat, int row, int col) { for (int i = row, cntR = 0; cntR < p; i++, cntR++) for (int j = col, cntC = 0; cntC < q; j++, cntC++) if (s[i][j] != pat[cntR][cntC]) return false; return true; } } }
3. KMP演算法（Knuth-Morris-Pratt）
【參考文章：漫畫：什么是KMP演算法？；KMP演算法—終于全部弄懂了_June·D的博客-CSDN博客】
回顧一下前兩種演算法效率不高的原因：在不匹配時，從待匹配串的起始位置重新全部開始匹配；反復計算哈希值，且需要處理哈希沖突的問題，這兩種方式可以看作每次將字串向后一位一位滑動，這樣的方式導致了中間存在大量無意義的比較，以及不得不完成的比較，使得效率低下，而KMP就針對這一點進行了優化，其核心在于：在匹配程序中，當不匹配時，對于已匹配好的部分，找到一種規律，將模式串一次性向后滑動很多位，從而提高效率，其中，記不匹配的字符為 “壞字符”，已匹配的部分為 “好前綴”，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 于是現在的問題就：如何制定滑動策略？
思考一個應用場景：在一篇文章中匹配某個字串，那么對于不同的主串，總是用同一個模式串去匹配，如果每針對一個新匹配的主串都要制定新的策略，那么時間復雜度依舊是 n2 級，甚至超過該級數，因此，制定的滑動策略不應該依賴于主串，對于同一個模式串，應當嘗試制定同一個滑動策略，即，滑動的策略只與模式串有關，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 接下來進一步思考滑動策略的細節：不匹配時，應當滑動到哪里？
舉個例子：
首先，把主串和模式串的首位對齊，從左到右對逐個字符進行比較，
第一輪，發現前5個字符都是匹配的，第6個字符不匹配，將其標記為壞字符 ‘A’，
【重難點】
可以發現，在好前綴 “GTGTG” 當中，主串的好前綴的后三個字符 “GTG” 和模式串的前三位字符 “GTG” 是相同的，我們分別把這兩部分記作可匹配后綴子串與可匹配前綴子串，在之后的比較中，這兩部分一定能夠匹配上，并且在這兩個部分匹配上之前，一定沒有其他可能使得模式串成功匹配的情況，這也為選擇最長的子串進行滑動提供了保障，因此，我們直接將模式串后移兩位，使得這兩部分對齊，并開始下一次比較，省去了中間的無效比較，
同理，如果在好前綴中如果存在多個可匹配后綴子串，那么為了能省區更多的無效比較，我們選擇找到最長的子串進行滑動，因此，我們的滑動策略為：在主串的好前綴中，找到最長可匹配后綴子串；在模式串中，找到對應的最長可匹配前綴子串，
第二輪，我們直接把模式串向后移動兩位，讓兩個 “GTG” 對齊，繼續從剛才主串的壞字符 ‘A’ 開始進行比較，
此時，主串的字符 ‘A’ 仍然是壞字符，這時候的匹配前綴縮短成了 “GTG”，
按照第一輪的思路，我們來重新確定最長可匹配后綴子串和最長可匹配前綴子串，此時，剩下字串 “G”，
第三輪，我們再次把模式串向后移動兩位，讓兩個“G”對齊，繼續從剛才主串的壞字符A開始進行比較，
……
小結：整體思路是，在主串的好前綴中尋找最長可匹配后綴子串（在好前綴中，從后往前找），在模式串中尋找對應的最長可匹配前綴子串（在已匹配串中，從前往后找），直接把兩者對齊，從而實作模式串的快速滑動，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 知道了退回到哪里，現在的關鍵在于如何實作退回？【重難點】
我們肯定不能每次都從頭遍歷一遍去尋找前后綴子串，前文提到找到某種規律，在每次失配后，都不會從頭重新開始列舉，而是根據這種規律，從某個特定的位置開始匹配；而對于模式串的每一位，都具有唯一的規律，這種規律可以幫助我們利用已有的資料不用從頭匹配，從而節約時間，
注意到，對于主串中的某一最長可匹配后綴子串，在當前狀態下是已經匹配上的，如果在模式串中找到了另一個合法的最長可匹配前綴子串，那我們就將其進行滑動，說明，如果可以滑動，那么在模式串中，一定存在兩個不同起始位置的子串，且這兩個子串的內容是相同的，因此我們可以用這個資訊，在只依賴模式串的情況下完成規律的查找與構建，
數學化表達：對于模式串 t 的每個元素 t[j]，都存在一個實數 k ，使得模式串 t 開頭的 k 個字符（ t[ 0 ], t[ 1 ],…, t[ k-1 ] ）依次與 t[ j ] 前面的 k 個字符（ t[ j-k ], t[ j-k+1 ],…, t[ j-1 ] ） 相同（其中，字符 t[ j-k ] 最少從 t[ 1 ] 開始，須保證不重復，所以 k < j ），，如果這樣的 k 有多個，則取最大的一個，以此保證最長，模式串 t 中每個位置 j 的字符都適配這種規律，定義一個 next 陣列存盤這種規律，即 next[ j ] = MAX{ k }，
對于 next 陣列，其索引表示當前比較的兩個字符的位置 ‘j’ ；索引對應值表示 k ，若當前字符為壞字符，則可以滑動 j – k 位，即下一次的比較位置，
（1） 當模式串的第一個字符和主串不匹配時，并不存在已匹配前綴子串，更不存在最長可匹配前綴子串，因此next陣列下標是0，next[ 0 ]的元素值也是0，
（2） 如果已匹配前綴是 “G”、“GT”、“GTGTGC”，但其并不存在最長可匹配前綴子串，所以對應的next陣列元素值（next[ 1 ]，next[ 2 ]，next[ 6 ]）同樣是0，
（3） 對于好前綴 “GTG”，此時比較位置為索引 j = 3，從該位置向前找最長可匹配前綴子串；從開頭找最長可匹配后綴子串，得出最長可匹配前綴是 ‘G’，即 k = 1（此時滑動 j – k = 2 位），因此，對應陣列中的next[ 3 ]，元素值是k = 1（即，下一次的比較位置），以此類推，“GTGT” 對應 next[ 4 ]，元素值是2；“GTGTG“ 對應 next[ 5 ]，元素值是3，
小結：用一個陣列保存每個字符的資訊，當在該字符處不匹配時，通過陣列保存的資訊，退回到相應位置，其中，陣列的下標表示“當前比較兩個字符的位置 j”，元素的值則是“最長可匹配前綴子串的下一個位置 《=》 最長可匹配前綴子串的長度 《=》 MAX{ k }”，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 如何構建next陣列？【重難點】
這個問題其實剛剛已經基本講述清楚了，現在按照例子再過一遍，掌握這個構建方法，就掌握了KMP的核心，
由于已匹配前后綴子串僅在模式串中查找，與主串無關，所以僅依據模式串，即可生成next陣列，
最簡單的方法是從最長的前綴子串開始，把每一種可能情況都做一次判斷，假設模式串的長度是m，生成next陣列所需的最大總判斷次數是1+2+3+4+......+m-2 次，
顯然，這種方法的效率非常低，整體近似 n2 的量級，因此，可以采用類似“動態規劃”的方法，首先next[ 0 ]和next[ 1 ]的值肯定是0，因為不存在前后綴字串；從next[ 2 ]開始，next陣列的每一個元素都可以由上一個元素推導而來，
設定兩個變數i和j，其中i表示“當前比較兩字符的位置”，也就是待填充的陣列下標；j表示“最長可匹配前綴子串的下一個位置”，即轉跳回來的下一次比較位置，也就是待填充的元素值，分析可知，此時最長可匹配前綴子串不存在，所以當 i = 0 時，j = 0，next[ 0 ] = 0，
繼續向后移動當前比較的位置，此時存在字串 “G“，由于只有一個字符，不滿足 k < j 的條件，因此，同樣不存在最長可匹配前綴子串，所以當 i = 1 時，j = 0，next[ 1 ] = 0，
此時的已匹配前綴是 “GT”，由于模式串當中 pat[ j ] != pat [ i-1 ]，即’G’ != ‘T’，最長可匹配前綴子串仍然不存在，所以當 i = 2 時，j = 0，next[ 2 ] = 0，
繼續后移，此時的可匹配前綴是 “GTG“，此時模式串中 pat [ j ] == pat [ i-1 ]，即 ‘G‘ = ’G‘，最長可匹配前綴子串出現了，是 ”G“，
所以當i=3時，j=1，next[ 3 ] = next[ 2 ] + 1 = 1，
繼續后移，此時的已匹配前綴是 “GTGT“，由于模式串中 pat [j] == pat [i-1]，即 ‘T’ = ‘T’，最長可匹配前綴子串又增加了一位，是 ”GT“，
所以當i=4時，j=2，next[ 4 ] = next[ 3 ] + 1 = 2，
此時的已匹配前綴是 “GTGTG“，由于模式串當中 pat [ j ] == pat [ i-1 ]，即 ‘G’ = ‘G’，最長可匹配前綴子串又增加了一位，是 ”GTG“，
所以當i=5時，j=3，next[ 5 ] = next[ 4 ] + 1 = 3，
此時的已匹配前綴是 “GTGTGC“，此時，模式串中 pat [ j ] != pat [ i-1 ]，即 ‘T’ != ‘C’，此時無法從next[ 5 ]的值推匯出next[ 6 ]，而字符 ‘C’ 的前面又有兩段重復的子串“GTG”，
【重難點】
我們要找的是最長公共前后綴子串，在之前的判斷中，我們已經獲得了兩組滿足條件的公共字串 “GT“ 與 ”GTG“，既然在當前 ”GTG “ 找不到滿足的前綴，那就到上一個前綴 “GT” 去找，
相當于把變數j回溯到了next[ j ]，也就是j = 1的局面，在之前的前綴中尋找滿足的前后綴子串，
回溯后，情況仍然是 pat [ j ] != pat[ i-1 ]，即 ’T’ != ‘C’，那就繼續回溯，
相當于再一次把變數 j 退回到了next[ j ]，也就是 j = 0 的局面，
情況仍然是 pat [ j ] != pat[ i-1 ]，即 ‘G’ != ‘C’，j 已經不能再回溯了，所以得出結論：i=6時，j=0，next[ 6 ] = 0，
小結：
1. 對模式串預處理，生成next陣列
1.1 從next[ 2 ]開始，利用動態規劃 + 雙指標推推出跳轉陣列，
2. 進入主回圈，遍歷主串
2.1. 比較主串和模式串的字符，
2.2. 如果發現壞字符，查詢next陣列，得到匹配前綴所對應的最長可匹配前綴子串，移動模式串到對應位置，
2.3.如果當前字符匹配，繼續回圈，
【注：有關 Line 88 行的分析，僅為個人推斷，可能錯在錯誤或解釋不清的地方，望各位有想法的大佬及學者留言評論，謝謝！】
- Line 88：為什么要加這一句呢？如果是找第一次匹配的位置，那直接 return 結果就好，但是，我們需要找到模式串在主串中所有出現過的位置，這就使得我們需要保證，在找到一次匹配后，需要滑動到某一特定位置，再次開始匹配，且滑動后的位置需要保證不會漏掉任何一種情況，
據之前的分析，j = next[ j ] 表示將 j 回溯到上一個滿足的前綴子串的下一次比較位置； j 表示的是當前應滑動到的比較位置，同理 j = next[ j – 1 ] 的含義肯定也是回溯到某一位置上，那為什么是 j – 1 呢？這里個人推斷應該有如下兩個方面：
（1）越界問題，進入到這個 if 內部的前提是 j == m，而 next 陣列的最大索引位 m – 1，因此，為了防止越界，傳入 next 中的值應當在 [0, m – 1] 之內，
（2）合理轉化，
這是當前的狀態，我們可以將當前 j 的位置補一個空白字符，其不與任何一個字符相匹配，因此需要回溯，那么對于當前前綴子串 “ABA#” 其不存在對應的可匹配前后綴子串，根據上面的規則，需要在之前找到一組可匹配的前后綴子串，重新進行判斷，而如何滑動到之前的可匹配子串呢？我們可以把 j 的前一位視作當前的比較位置，假設該位置的字符是不匹配的，這樣就可以直接回溯到之前的可匹配子串的下一次比較位置，因此，此處位 j = next[ j – 1 ]，
復雜度分析：
現在，該演算法第一次計算t的哈希值時，時間復雜度為O(n)；后續計算哈希值因為利用了滑窗的優化只有O(1)；比較字串的Equals()方法，一般地，可以視為O(1)，
- 總時間復雜度為O( m + n )，其中計算 next 陣列的時間為 O( m )；匹配時 時間為 O( n )，
- 空間復雜度為O( m )，使用了一個 next 陣列，其中 m 為模式串的長度，
照例，測一下剛才的題
可以發現，即使面對很高數量級的資料，其效率是RK演算法的兩倍，
【注意：用此代碼提交洛谷的題目（P3375 【模板】KMP字串匹配 - 洛谷）會存在兩個點超時，另一位使用C#提交的Coder也發生了同樣的問題，推測可能是運行環境的原因，洛谷上的C#運行環境為C# MONO，其優化與相關底層邏輯并不如現行的 .NET ，力扣和牛客使用的運行環境分別是 .NET 6/C# 10 與 mcs5.4 ，因此一般不會出現卡語言的情況】
4. BM演算法（Boyer-Moore）
【參考文章：字串匹配演算法：KMP與BM - AD_milk - 博客園 (cnblogs.com) 參考書籍：《資料結構與演算法之美》】
雖然KMP比較出名，但在效率上有很多的演算法都比它要好，如BM演算法，其效率要比KMP好上3到4倍，當模式串長度較短時，二者效率基本相近；隨著模式串 pat 的長度增大，BM的優勢也逐漸凸顯出來，原因可能在于，BM屬于貪心演算法，適應于實際應用，同時，貪心也是思考問題最直接的方式；KMP是穩定演算法，中規中矩，按規矩辦事，不在乎特例，
首先拋出兩個定義：
（1）壞字符規則：指待匹配串和主串當中不匹配的字符，將主串的的該字符定義為壞字符，
BM演算法與我們平常接觸的字串比較方法不同，它是按模式串從大到小的順序，倒著比的，這樣做也是有好處的，起碼直觀上是這樣感覺的，貪心也是憑感覺嘛，就像做選擇題，出卷老師為了讓你花的時間久一點，故意把正確答案放到C跟D上，所以根據統計規律聰明點的做法應該是先算C跟D，
舉個例子：
從模式串的末尾開始比較，當前主串的字符 ‘C’ 與模式串的字符 ’D’，將其定義為“壞字符”，有該字符存在，則無論之前匹不匹配，模式串均不可能在包含該壞字符的字串內被匹配，
俗話說：“三十六計走為上計“，既然你不滿足我那我就開溜，直接向后移動6位，從沒有壞字符的地方開始匹配，配著配著，發現又不滿足了，定義壞字符為 ‘T‘ ，所以繼續后移，
據此我們可以發現一個規律：當不匹配時，設壞字符對應的模式串中的字符，在模式串中的下標為 si （相對下標），若壞字符在模式串中存在，則把這個壞字符在模式串中的下標記為 xi；不存在，則把 xi 記為 -1，且這樣的壞字符在模式串中若存在多個，則總是選擇最靠后的一個下標，以此保證不會因滑動過多而略過某些情況，那么，模式串向后滑動的位數 k = si – xi，圖解參閱如下：
（2） 好后綴規則：指待匹配串和主串當中相匹配的后綴，
利用壞字符規則，BM在最優情況下的時間復雜度為 O( n / m )，例如主串為 aaabaaabaaabaaab，模式串為 aaaa，每次均可向后滑動四位，但只有這一個規則還不夠，因為 k 可能為負數，如主串為 aaaaaaaaaaaa，模式串為 baaa，因此，我們又引入一個規則：好后綴規則，
依舊來舉例說明：
將已經匹配的 “BC” 稱為好后綴，記作 { u }，我們用它在模式串中尋找另一個與好后綴匹配的字串 { u* }，
如果存在，則將模式串滑動到子串 { u* } 與好后綴 { u } 上下對齊的位置，
如果不存在，則直接滑動到好后綴 { u } 的后面，
此外，若在模式串中若存在多個與好后綴匹配的相同字串或與好后綴的后綴字串相同的模式串中的前綴子串，則選擇最長且靠后的串并記為 { v }，按規則滑動，
以上就是BM演算法的兩個核心規則，在使用中可以分別計算好使用兩用規則的滑動位數，取較大的一個 max( k1, k2 )，作為向后滑動的位數，這樣既能使得時間復雜度接近最優的O( n / m )，也能避免滑動位數出現負數的情況，
具體實作如下：
（1）對于壞字符規則的計算，如果每次都去遍歷那效率會很低，可以利用一個哈希表，存盤每個字符在模式串中的位置，如果有多個相同字符，則取下標最大的一個，如圖：
（2）對于好后綴規則，其核心在于：在模式串中查找與好后綴匹配的子串；在好后綴的所有后綴字串中，查找能與模式串前綴子串匹配的最長子串，
- 先來解決第一個問題，如何表示模式串中不同的后綴字串以及如何滑動到對應位置？
分析可知，后綴子串的最后一個字符的位置是固定且唯一的，因此只需通過后綴子串的長度即可進行唯一標識，然后引入一個陣列suffix，陣列下標表示后綴子串的長度（下標唯一且不變，子串最后一個字符的位置唯一且不變），對應陣列值表示與其匹配的另一個子串的起始下標，如圖：
如果存在多個合法的子串，則取下標最大的一個，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 找完了模式串中的所有子串，還有一個問題：查找在好后綴的所有后綴子串中，能與模式串前綴子串匹配的最長的一個后綴子串（以下記為 “最長可匹配后綴子串”）
同樣，為了避免每次遍歷帶來的時間消耗問題，我們對其也進行預處理，因為已經用陣列 suffix 記錄了滑動的規則，因此現在只需記錄是否需要滑動即可，定義一個bool型別的陣列 prefix，記錄模式串的每個后綴子串是否能匹配模式串的前綴子串，如圖：
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 接下來，理解并推導一下這兩個陣列的值
用模式串的前綴子串，即下標為 [ 0, i ] （ 0 <= i <= m – 2 ）的子串，與整個模式串求公共后綴子串，若公共后綴字串的長度為 k ，在前綴子串中的起始下標為 j ，則記錄 suffix[ k ] = j ，若 j = 0，說明公共后綴子串是模式串的前子串，那就記錄prefix[ k ] = true，相當于將字串分為兩部分，若存在兩部分完全相同，則記錄為 true，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
- 最后來看一下，如何根據這兩個陣列計算出滑動的位數
設好后綴長度為 k，用好后綴 { u } 在陣列 suffix 中查找可匹配子串，若 suffix[ k ] ≠ -1，說明存在可匹配字串，則將模式串往后移動 j – suffix[ k ] + 1 位，其中 j 表示壞字符對應模式串中的下標位置，如圖：
如果 suffix[ k ] = -1，說明模式串中不存在與好后綴匹配的子串，此時，使用好后綴的另一條規則：查找好后綴中，所有后綴子串中，能與模式串前綴子串匹配的，最長的那一個后綴子串，好后綴 pat[ j + 1, m – 1 ]的后綴子串 pat[ r, m – 1]（ j + 2 <= r <= m – 1 ）記作 { v }，其長度 k = m – r，若 prefix[ k ] = true，表示長度為 k 的后綴子串，存在可匹配的前綴子串 { v* }，則將模式串移動 r 位，如圖：
如果在模式串中沒有找到與好后綴可以匹配的前綴子串，也沒有找到好后綴中可匹配模式串中前綴子串的，后綴子串，則將整個模式串后移 m 位，如圖：
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
代碼實作：【注：考慮到時間成本與篇幅問題，在此不做BM演算法的同意主串多次匹配問題，如有興趣歡迎自行研究，本人也可能會在今后放出可對同一主串多次匹配的代碼】
復雜度分析：
- 時間復雜度為O( n ) 若模式串中包含大量重復字符，則計算兩個陣列的時間將會達到 O( m2 )，但一般不會出現這樣的極端情況，
- 空間復雜度為O( m )
這就是一種極端情況，存在大量重復字符，導致其效率嚴重下降，
總結
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
至此，四種匹配方法全部介紹完畢，總結一下：
1. BF純暴力演算法，一位以為比較，遇到不匹配的從模式串開頭在此一位一位比較，時間復雜度較高，但簡潔明了思路清晰，因此在實際應用中最為常用，
2. RK演算法，基于BF的比較字符的思想，轉化為比較子串的哈希值，數值間的比較確實比字符比較快，而且利用滑窗的思想將計算哈希的時間復雜度將為 O( n )，但容易存在哈希沖突的問題，沖突后需要對 兩部分子串進行完整比較，計算哈希方式越簡單、字串越長，沖突的概率越高，復雜度也會接近 O( n2 )，
3. KMP演算法，利用某一特殊的規律，減少在不匹配時向后退回的位數，以達到降低時間復雜度的目的，
4. BM演算法，結合貪心思想，進一步對KMP進行優化，但這兩種方法過于復雜，掌握很不容易，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
[附 BF演算法代碼]
void BF(string s, int n, string pat, int m) { for (int i = 0; i <= n - m; i++) { int j = 0; while (j < m) { if (s[i + j] != pat[j]) break; j++; } if (j == m) pos.Add(i); } }
[附 RK演算法代碼]
void RK(string s, int n, string pat, int m) { int patCode = GetHash(pat); int sCode = GetHash(s.Substring(0, m)); for (int i = 0; i <= n - m; i++) { if (patCode == sCode && ComString(i, s, pat)) pos.Add(i); if (i < n - m) sCode = NextHash(s, sCode, i, m); } } int GetHash(string str) { int hash = 0, n = str.Length; for (int i = 0; i < n; i++) hash += str[i] - 'a'; return hash; } int NextHash(string str, int hash, int idx, int len) { hash -= str[idx] - 'a'; hash += str[idx + len] - 'a'; return hash; } bool ComString(int idx, string s, string pat) { return pat == s.Substring(idx, pat.Length); }
[附 KMP演算法代碼]
void KMP(string s, int n, string pat, int m) { next = GetNext(pat, m); int j = 0; for (int i = 0; i < n; i++) { while (j > 0 && s[i] != pat[j]) j = next[j]; if (s[i] == pat[j]) j++; if (j == m) { pos.Add(i - m + 1); j = next[j - 1]; } } } int[] GetNext(string pat, int m) { next = new int[m]; int j = 0; for (int i = 1; i < m; i++) { while (j != 0 && pat[j] != pat[i]) j = next[j]; if (pat[j] == pat[i]) j++; next[i] = j; } foreach (int i in next) Console.Write(i + " "); return next; }
[附 BM演算法代碼]
static int SIZE = 26; void GenerateGS(string pat, int m, int[] suffix, bool[] prefix) // 預處理 { suffix = new int[m]; prefix = new bool[m]; Array.Fill(suffix, -1); Array.Fill(prefix, false); for (int i = 0; i < m - 1; i++) { int j = i, k = 0; // k 為公共子串的長度 while (j >= 0 && pat[j] == pat[m - k - 1]) // 與 b[ 0, m - 1 ]求公共后綴子串 { j--; k++; suffix[k] = j + 1; // j + 1 表示公共后綴子串在 pat[ 0, i ] 中的起始下標 } if (j == -1) prefix[k] = true; // 公共后綴子串也就是模式串的前綴子串 } } void GenerateBC(string pat, int m, int[] table) // 建立哈希表 { for (int i = 0; i < SIZE; i++) table[i] = -1; for (int i = 0; i < m; i++) table[pat[i] - 'a'] = i; } int MoveByGS(int j, int m, int[] suffix, bool[] prefix) { int k = m - j - 1; if (suffix[k] != -1) return j - suffix[k] + 1; for (int r = j + 2; r < m; r++) if (prefix[m - r] == true) return r; return m; } int BM(string s, int n, string pat, int m) { s = s.ToLower(); pat = pat.ToLower(); int[] table = new int[SIZE]; GenerateBC(pat, m, table); // 構建壞字符哈希表 int[] suffix = new int[m]; bool[] prefix = new bool[m]; GenerateGS(pat, m, suffix, prefix); int i = 0; // i 表示主串與模式串上下對齊的第一個字符 while (i <= n - m) { int j; for (j = m - 1; j >= 0; j--) // 從后向前匹配 if (s[i + j] != pat[j]) break; // 壞字符對應下標為 j if (j < 0) return i; // 匹配成功 int x = j - table[s[i + j] - 'a']; // 向后滑動 int y = 0; if (j < m - 1) y = MoveByGS(j, m, suffix, prefix); i += Math.Max(x, y); } return -1; }
[# 有關Intrinsic、Attribute與“內在屬性”]
[Intrinsic] 被稱為內在屬性，我們把形如 [xxxx] 的運算式稱為內在屬性，如 [Serializable]、[IndexerName("Chars")]、[MethodImpl(MethodImplOptions.InternalCall)]等，
通過追蹤發現其派生于類Attribute，在分析該內在屬性前，先來看看什么是 Attribute，
1. 類 Attritube
這里要注意，屬性和特性的區別，在微軟翻譯器上，Arrtibute 被翻譯為屬性，這個翻譯在 C# 中并不準確，
- 屬性：又叫智能欄位，是類的成員，是面向物件編程語言的一個基本概念，提供了安全和靈活的資料訪問封裝，不存盤資料，
- 特性：特性本質上是一個類，用來為目標元素提供附加資訊，并在運行時通過反射機制來獲取這些資訊以影響或控制應用程式運行時的行為，目標元素可以是程式集、類、建構式、委托、列舉、事件、欄位、介面、方法、可移植可執行檔案模塊、引數、屬性、回傳值、結構或其他特性，
限于篇幅，在此就簡單描述一下這個類的基本資訊與功能，一般地，我們并不直接使用這個類，而是較多的使用其派生出的類
此處僅展示部分，派生的類有很多，每個類之下有不同的內容，其內容用于規定被修飾的物件應當怎樣做或只能怎樣做，如：AttributeUsage(AttributeTargets.Method) ，其中，AttributeTargets 用于指定對哪些程式元素使用；而 AttributeTargets.Method 表示被修飾的物件只能被方法體使用，
在 .NET 中，提供了三種預定義的特性：AttributeUsage、Conditional 與 Obsolete，
- AttributeUsage：描述了如何使用一個自定義特性類，
- Conditional：標記了一個條件方法，其執行依賴于指定的預處理識別符號，它會引起方法呼叫的條件編譯，取決于指定的值，比如 Debug 或 Trace，
如，我們在方法上附加一個 Conditional 特性，使得其只在 DEGUB 模式下運行，
- Obsolete：用于標記不應被使用的程式物體，它可以讓通知編譯器丟棄某個特定的目標元素，如，當一個新方法被用在一個類中，但是仍然想要保留類中的舊方法，可以把它標記為 Obsolete（過時的）并輸出輸出資訊，
2. 類 IntrinsicAttribute
關于特性 Intrinsic，在 dotnet/corefx 中找到其相關注釋如下：
- Calls to methods or references to fields marked with this attribute may be replaced at ome call sites with jit intrinsic expansions. 微軟翻譯：某些呼叫站點中，對使用此屬性標記的方法的呼叫或對使用此屬性標記的欄位的參考可能會替換為 JIT擴展，說人話就是，被該屬性標記的方法或欄位，可能會被 JIT 替換/優化成功能相同的方法或欄位，
- Types marked with this attribute may be specially treated by the runtime/compiler. 微軟翻譯：運行時/編譯器可能會專門處理使用此屬性標記的型別，也就是說，被該內在屬性標記的物件確實會進行專門的處理，
舉個粗略的例子：JIT-optimizer 可以代替 Enum.HasFlag 在某些情況下進行簡單的按位比較，而在其他情況下則不然，為此，它需要將方法標識為 Enum.HasFlag ，檢查一些條件并將其替換為更優化的實作，雖然優化器可以通過名稱識別方法，但出于性能原因，最好在執行字串比較之前通過簡單的標志過濾掉方法，即在編譯階段就將要優化的部分識別出來，而不是將其交給優化器來進行識別作業，
下面，簡單解釋一下其運行流程：
- 關于方法的定義
【注：訪問以下超鏈接可能需要已決議好的 DNS】
在 donet/coreclr/vm 下的 wellknownattributes.h 檔案內，定義了一個列舉類 WellKnownAttribute，其派生于 DWORD，
還定義了一個回傳值為 char* 的常量方法體（注意，此處的語言并不是 C#，眾多周知，C#/.NET 的底基本上是用 C/C++ 撰寫的，C# 并不支持 inline，也不能用 const 修飾方法體，不過 JIT 支持自動 inline 將IL轉成真正機器碼時，會自動將某些函式進行inline展開）
其中，定義了當傳入特性為 Attribute 的情況，回傳這個命名空間，
- VM 決議它并設定 IsJitIntrinsic 方法的標志為真（
methodtablebuilder.cpp）
- 此標志用于在方法屬性（
jitinterface.cpp）中設定另一個標志
- 此標志用于過濾掉明顯不是內在的方法（
importer.cpp）
- impIntrinsic然后利用 lookupNamedIntrinsic 識別（主要是通過名稱）真正（不僅僅是可能）應該優化的方法；
- 畢竟，importer可以根據方法進行優化，例如，優化 Enum.HasFlag（ importer.cpp ）
以上是根據現有的遠古資料推斷出的運行方式，因為資料實在有限，本人目前對 CLR 了解并不是很深，如果存在錯誤或其他見解還請留言！
[# 有關MethodImpl]
還是這個例子，有了剛才的分析，那很快得出結論：MethodImpl 也是一個內在屬性，其中，Impl 是 implement 的縮寫，直譯為“實作”，
（1）作用：字面翻譯可以初步得出，這是一個對方法進行特定優化的特性，優化的方式是內部呼叫，
（2）作用域：可以在方法以及建構式上使用，可以影響 JIT 編譯器的行為，
- Line 10、16：兩個建構式，讀入傳進來的具體優化機制，
- Line 28：一個只讀屬性，用于存盤具體的優化機制，
其中的列舉值與功能對應參見下圖：
- Line 31：用于存盤并標記不同的運行環境（IL、Native、OPTIL、Runtime），
[# 有關字串的比較與暫存池]
1. 字串的比較 與 StringComparsion
String類里的字串比較方法，面對簡單的比較時，直接使用關系運算子（“==”，“<=”，”>=“）；面對較為復雜的比較操作時，會呼叫在類CompareInfo下的Compare()方法，
首先來看最簡單也是最常用的Compare()方法，兩個字串的直接比較、帶有自定義比較器的字串比較，
這兩個方法均會進入到String內部的一個多載方法中，如下圖所示：
- Line 213：strA與strB為待比較的兩個字串；comparisonType為比較器型別，
- Line 215~229：直接利用關系運算子，只判斷是否相等，對于關系運算子，默認情況下，判斷字串大小規則如下：
（1）比較長度，長度越長字串值越大，
（2）長度相同，依次比較每個字符，按照ASCII碼大小進行比較，字符ASCII碼越大，則字串值越大，
【注：Comapre()方法的比較規則與關系運算子不同】
如果字串不相等且沒有任何一個字串為null，則進入之后的判斷，通過對傳入的比較規則comparsinType進行不同的處理，
再分析這些列舉項的作用前，先解釋一下幾個概念：
（1）區域性：字面意思，某一區域所具有的性質，
（2）當前區域性：當前系統所在的區域所執行的規則，
（3）固定區域性：不依賴于任何區域性（固定的），可以理解為公共區域性，任何情況下無論身在何處都遵守該規則，一般地，這個屬于國際通用標準，
對于列舉集StringComparsion內部包含6個屬性，每個屬性的值用十六進制表示，從0到5，用于呼叫不同的比較器，存在的意義是對字串的比較進行優化，如，當比較的字串存在大小寫字母，但不需要區分大小寫時，使用轉換的方式統一大小寫會造成一定的性能消耗，此時就可使用該列舉集中的屬性進行標記，以提升性能，
- Line 9：CurrentCulture屬性，使用區磁區域性的排序規則和當前區域性比較字串，即，在當前的區域資訊下進行比較，這是String.Compare在沒有指定StringComparison的時候，進行的默認比較方式，對于當前的區域資訊，指的是當前所使用的官方字典，不同地區的字典規則不同，因此會造成同一個比較結果不同的情況，舉例如下：
其中 Thread 在這里的作用是，當呼叫該方法時，啟動一個具有特殊屬性的執行緒，執行緒有效性直到方法結束，在該執行緒生命期內，所有關于該執行緒的屬性都將被強制應用，
在瑞典官方字典中，某些我們熟知的字符存在不同的含義，對應值也不同，
- Line 13：InvaiantCulture屬性，在任何系統中的（即，不同的culture）比較都將得到相同的結果，即，忽略地域性的影響，使用國際通用的默認字典進行比較，
- Line 17：Ordinal屬性，按照 ASCII 碼的數值進行比較，
- Line 11、15、19：忽略大小寫字符的差異.
小結一下，經過多次嘗試，發現大多數國家應該都是遵守國際比較標準的，只是在格式上可能會有所不同，支持多種CultureInfo使得 .NET 在跨區域上更加人性化，因為這可以使同一個資料適應不同地區和文化，滿足處于不同地區和文化的用戶，但前提是資料給“人”看，如果這些資料用于計算機之間的傳輸，給“機器”看，這樣的多文化處理反而不妥，會造成同一個資料的不同展現形式，尤其是讀寫兩方的文化地區不同時，資料可能根本無法被正常讀取或者產生潛在bug，因此這里，這也正是InvariantCulture的用武之地，強制規定一個國際通用標準，就像 .NET 中的 CLR 一樣，指定了一個規范，
2. 字串的記憶體分配與字串暫存池
這個暫存池有好多稱法：常量池，緩沖池等，.NET/C# 在編譯階段就能確定相同的字串，在運行期間使用的都是相同的實體，暫存池的引入避免分配大量的字串物件造成的過多的記憶體空間浪費，本次主要解決以下三個問題：對于所有的初始化方式，是否都會進行判斷，將多個相同字串的參考指向暫存池的一個實體？對于存在運算的字串，在編譯階段是否會進行判斷，將運算結果相同字串的參考指向暫存池？為什么要針對字串專門建立一個暫存池這樣的機制，而值型別和其他參考型別沒有這樣的機制？同時，String 提供了一個方法 IsInterned() 來判斷字串是否在暫存池中，如果存在則回傳其參考；不存在回傳 null，可以利用這個方法具體分析每種情況，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
下面來解決兩個問題：
（1）對于所有的初始化方式，是否都會進行判斷，將相同參考指向暫存池？
（2）對于存在運算的字串，在編譯階段是否會進行判斷，將運算結果相同字串的參考指向暫存池？
- 直接完整初始化
即，直接對字串變數進行完整賦值，種植情況，毫無疑問是遵循字串暫存池檢查的，
- 用運算子 ‘+’ 連接
和 Java 一樣，對于字串在編譯期間具有字串優化機制，會在運行前計算出完整的字串，
- 用 String.Join 連接
對于方法的運算，需要在運行時才能完成，而變數指向的參考是在編譯階段確定的，s2 這種方式，在編譯階段無法得出結果，因此只能先開辟一個新的記憶體，在運行時確定其值，
并且，無法再暫存池中查找到 s2 的參考，據此推斷在編譯階段不能確定值得字串不會被寫入暫存池，
- StringBuilder 構建
同理，對于 StringBuilder 的構建，依舊無法在編譯階段確定其值，也就沒有寫入暫存池，
- 占位符
由于占位符需要呼叫方法體，因此無法在編譯階段確定 s2 的值，
- 字串的內插
先簡單介紹一下什么是字串內插，由于占位符需要我們在字串中先用數字標記位置，再到字串結束后寫下對應的值，程序較為繁瑣，因此引入內插操作，
使用符號 ‘$’ 代表被標記的字串將實行內插操作，可看到，雖然內插操作看似不執行方法體，但依舊不指向暫存池中的物件，說明內插操作的值是在運行階段完成的，
不過，對于此處 s2 的定義方式，當 c1 與 c2 是常量時，其在編譯階段即可被確定，會被寫入暫存池，
小結
對于暫存池的寫入，在此得出的結論是：
（1）只有在編譯階段可以確定的字串，才會被查找或寫入暫存池中，如何判斷一個字串是在編譯階段被確定的？只需要在之前加上關鍵字 const 即可，報錯則表示不能在編譯階段確定，
（2）除了直接完整初始化和使用運算子這兩種方式以外（注：不排除有其他方式），其余方式均不會再暫存池中進行查找或寫入，
（3）對于存在于暫存池中的字串，即使之后不會再被使用，也不會被 GC 回收，
（4）若不想要讓字串池化，可加上特性標記 [assembly: CompilationRelaxations(CompilationRelaxations.NoStringInterning)]，即使加上后也不會被 GC 回收，
—— —— —— —— —— —— —— —— —— —— —— —— —— ——
下面解決剩下的問題：為什么要針對字串專門建立一個暫存池這樣的機制，而值型別和其他參考型別沒有這樣的機制？
結合資料，個人推斷，應該是因為字串的不可變性，
（1）字串是參考型別，在創建時不斷地在堆上開辟新空間，會占用較高記憶體，產生較大的消耗，而值型別是在堆疊上存盤，相比于堆來說，不是那么消耗記憶體，
（2）字串的不可變性，使得其在確定之后就不可更改，此處的不可更改指的是，只要賦值，該值就會一直保留在記憶體中直到程式結束，為了避免出現大量重復物件，而創建大量重復實體占用大量記憶體的問題，引入了暫存機制，而其他參考型別不具有不可變性，一般地可以在運行時隨意修改，相對而言不需要這樣的暫存機制，
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/509801.html
標籤：.NET技术