SortedListTKey,TValue雙數(shù)組有序映射的源碼模型與選型邊界系列C# 與常用數(shù)據(jù)結(jié)構(gòu)源碼剖析 · 排序集合篇閱讀時(shí)間約 55 分鐘前置知識(shí)二分查找、動(dòng)態(tài)數(shù)組、比較器與 SortedDictionary版本邊界以現(xiàn)代System.Collections.Generic.SortedListTKey,TValue的共同形狀為主。私有字段、容量增長(zhǎng)和便利 API 會(huì)隨 TFM/tag 變化使用前應(yīng)查目標(biāo) reference assembly 與固定源碼 tag。一、名字像 List語(yǔ)義卻是按鍵排序的 DictionarySortedList 實(shí)現(xiàn)鍵到值的唯一映射并按IComparerTKey定義的順序保存鍵。它不是可以容納重復(fù)鍵的排序條目 List也不是哈希表。當(dāng) comparer 返回零時(shí)兩個(gè)鍵屬于同一映射位置即使它們的Equals返回 false。它的核心實(shí)現(xiàn)是兩個(gè)平行數(shù)組一個(gè)保存按比較器升序排列的 key另一個(gè)在相同索引保存 value。這種布局用連續(xù)存儲(chǔ)換取了二分查找和緊湊遍歷代價(jià)是中間插入/刪除需要搬移后綴。SortedDictionary 則通常使用平衡樹(shù)存儲(chǔ)節(jié)點(diǎn)插入與刪除無(wú)需搬移大段連續(xù)元素但逐節(jié)點(diǎn)對(duì)象、左右引用和指針追蹤增加內(nèi)存與緩存成本。選型不是“數(shù)組比樹(shù)快”而是更新頻率、規(guī)模、順序訪(fǎng)問(wèn)、內(nèi)存與比較器成本的組合。二、核心字段與不變式下面是教學(xué)模型不是可替換目標(biāo) runtime 的逐字源碼public class SortedListTKey, TValue { private TKey[] _keys; private TValue[] _values; private int _size; private int _version; private IComparerTKey _comparer; }任何公開(kāi)操作前后都必須維護(hù)_keys.Length _values.Length容量在兩個(gè)數(shù)組上一致。0 _size Capacity有效區(qū)間恰好是[0, _size)。對(duì)每個(gè)有效索引 i_keys[i]與_values[i]組成一個(gè)鍵值對(duì)。相鄰有效鍵滿(mǎn)足Compare(_keys[i], _keys[i1]) 0零比較的重復(fù)鍵不能同時(shí)存在。有效區(qū)間外的槽不是公開(kāi)數(shù)據(jù)對(duì)含引用類(lèi)型刪除/清空時(shí)應(yīng)斷開(kāi)無(wú)效槽對(duì)對(duì)象的?；睢＿@些不變式解釋了為什么 key 和 value 必須同步搬移也解釋了為什么不能為了微優(yōu)化只對(duì) key 數(shù)組排序。一旦平行索引錯(cuò)位查找仍可能命中正確鍵卻返回另一個(gè)鍵的值這是比排序錯(cuò)誤更難發(fā)現(xiàn)的數(shù)據(jù)損壞。三、二分查找同時(shí)回答“存在嗎”和“應(yīng)插在哪”按鍵查找只訪(fǎng)問(wèn)_keys[0.._size)。當(dāng)命中時(shí)返回非負(fù)索引未命中時(shí)Array.BinarySearch類(lèi) API 會(huì)返回插入點(diǎn)的按位取反調(diào)用方使用~result恢復(fù)索引。int index Array.BinarySearch(_keys, 0, _size, key, _comparer); if (index 0) { // comparer 認(rèn)為等價(jià)的鍵已存在 } else { int insertionIndex ~index; // [0, insertionIndex) key [insertionIndex, _size) }使用mid lo ((hi - lo) 1)而不是(lo hi) / 2可避免兩個(gè)大正數(shù)先相加的溢出形狀但實(shí)際 runtime helper 的寫(xiě)法應(yīng)按 tag 查閱。二分查找的比較次數(shù)為 O(log n)不代表總時(shí)間與鍵無(wú)關(guān)。字符串文化比較、復(fù)合鍵逐字段比較或有副作用的 comparer 都會(huì)放大每次比較成本。四、Add 與索引器 setter重復(fù)鍵的語(yǔ)義不同Add(key,value)發(fā)現(xiàn) comparer 等價(jià)鍵時(shí)拋出重復(fù)鍵異常索引器 setter 在鍵已存在時(shí)更新對(duì)應(yīng) value未存在時(shí)才插入。不要用 setter 靜默吞掉本應(yīng)暴露的配置 ID 重復(fù)也不要在“最后寫(xiě)入勝出”就是業(yè)務(wù)規(guī)則時(shí)用異常做正常分支。插入的教學(xué)步驟是拒絕不符合類(lèi)型/API 契約的空 key。二分查找命中時(shí)按 Add 或 setter 語(yǔ)義處理。若未命中恢復(fù)插入位置并確保兩個(gè)數(shù)組容量足夠。將 key 和 value 數(shù)組在插入點(diǎn)之后的有效后綴各后移一位。在相同索引寫(xiě)入 key/value最后增加_size并更新版本。// 教學(xué)偽代碼忽略了具體拋錯(cuò) helper 和增長(zhǎng)策略。 void Insert(int index, TKey key, TValue value) { EnsureCapacityForOneMore(); int move _size - index; if (move 0) { Array.Copy(_keys, index, _keys, index 1, move); Array.Copy(_values, index, _values, index 1, move); } _keys[index] key; _values[index] value; _size; _version; }二分查找是 O(log n)后綴搬移是 O(n)所以中間插入總復(fù)雜度是 O(n)。在末尾插入時(shí)無(wú)后綴搬移如果容量足夠該次寫(xiě)入只有查找和常數(shù)寫(xiě)入。因此按 comparer 升序批量插入可比隨機(jī)順序減少搬移但仍要支付每次查找和 API 調(diào)用。若數(shù)據(jù)本就來(lái)自無(wú)序大批量“先收集后一次排序并驗(yàn)重”的自定義構(gòu)建管線(xiàn)可能更合適但要與直接 Add 做可復(fù)現(xiàn)對(duì)照。五、刪除、Clear 與引用清理按鍵刪除先二分查找索引再將其后 key/value 同步左移一位。搬移后原有最后一個(gè)有效槽會(huì)留下重復(fù)引用實(shí)現(xiàn)應(yīng)在 TKey/TValue 是引用或含引用時(shí)將尾槽置為 default避免已刪對(duì)象被后備數(shù)組繼續(xù)?；?。Clear()將 Count 歸零并清理原有效區(qū)間中必要的引用但通常保留 keys/values 數(shù)組容量以便復(fù)用。它不等于立即歸還所有內(nèi)存。將 Capacity 縮小或調(diào)用 TrimExcess 類(lèi) API 則要分配新數(shù)組和復(fù)制有效數(shù)據(jù)應(yīng)放在長(zhǎng)期低水位或加載邊界不放在每次刪除或每幀路徑。一個(gè)曾經(jīng)容納數(shù)十萬(wàn)配置項(xiàng)的 SortedList即使 Clear 后邏輯為空也可能保留大數(shù)組。這不是鍵值對(duì)引用泄漏而是容器容量駐留。要區(qū)分“對(duì)象因舊引用?；睢焙汀皵?shù)組自身仍然很大”分別用 GC root 分析與容量監(jiān)控證明。六、按鍵訪(fǎng)問(wèn)、按索引訪(fǎng)問(wèn)與 API 版本按鍵讀取需要二分查找是 O(log n)。但雙數(shù)組讓“已知索引取第 i 個(gè) key/value”的內(nèi)部操作成為 O(1)。不應(yīng)因此直接在文中虛構(gòu)一個(gè)GetAt并宣稱(chēng)所有 .NET 版本都有該公開(kāi) API。不同 TFM 可能通過(guò)Keys[index]、Values[index]、GetKeyAtIndex/GetValueAtIndex或其他形狀暴露能力必須查目標(biāo) reference assembly。如果業(yè)務(wù)需要按排名索引取值還要定義更新時(shí)索引是否允許變化。在中間插入一個(gè)新鍵會(huì)使其后所有元素索引 1所以索引是查詢(xún)時(shí)的位置不是穩(wěn)定實(shí)體 ID。不能將它持久化后在集合變化后繼續(xù)當(dāng)鍵使用。TryGetValue在一次查找中表達(dá)“可能缺失”ContainsKey后再用索引器會(huì)做兩次二分查找。但若第一次檢查和第二次使用有獨(dú)立業(yè)務(wù)語(yǔ)義可讀性可以比微小重復(fù)更重要。不應(yīng)給出脫離鍵類(lèi)型、數(shù)量和運(yùn)行時(shí)的固定速度倍數(shù)。七、比較器是鍵空間的唯一性規(guī)則SortedList 不用EqualityComparerTKey判斷重復(fù)而使用IComparerTKey.Compare(x,y)0。因此 comparer 必須提供穩(wěn)定、自洽的全序或至少滿(mǎn)足集合操作所需的嚴(yán)格弱序性質(zhì)。若它一會(huì)兒認(rèn)為 ab一會(huì)兒又認(rèn)為 ba二分查找的前提就被破壞。下面的 comparer 只按玩家分?jǐn)?shù)降序比較會(huì)把所有同分玩家當(dāng)成同一鍵// 錯(cuò)誤缺少唯一破平字段 int Compare(PlayerRank x, PlayerRank y) y.Score.CompareTo(x.Score);應(yīng)把穩(wěn)定唯一 ID 納入破平并用安全的CompareTo或顯式分支不直接相減避免溢出int Compare(PlayerRank x, PlayerRank y) { int byScore y.Score.CompareTo(x.Score); return byScore ! 0 ? byScore : x.PlayerId.CompareTo(y.PlayerId); }鍵進(jìn)入集合后參與比較的狀態(tài)不能原地改變。如果PlayerRank.Score可變且對(duì)象作為 key改分后數(shù)組不會(huì)自動(dòng)重排查找結(jié)果就不再可信。排行榜更新應(yīng)刪除舊的不變排名鍵再插入新鍵若更新頻繁應(yīng)重新評(píng)估數(shù)組搬移成本與數(shù)據(jù)結(jié)構(gòu)選型。八、枚舉、Keys/Values 視圖與版本號(hào)枚舉必須按 key comparer 順序從索引 0 走到_size-1每次用同一索引組成鍵值對(duì)。這是連續(xù)數(shù)組布局的長(zhǎng)處。Keys和Values是對(duì)原集合的只讀視圖通常不是每次將內(nèi)容復(fù)制成新集合底層 SortedList 變化后視圖觀(guān)察的數(shù)據(jù)也隨之變化。枚舉器通常捕獲_version結(jié)構(gòu)修改后繼續(xù) MoveNext 會(huì)盡早失敗。版本號(hào)不是鎖也不保證并發(fā)修改安全。普通 SortedList 不應(yīng)在一個(gè)線(xiàn)程插入/刪除時(shí)由另一個(gè)線(xiàn)程枚舉。需要跨線(xiàn)程只讀時(shí)應(yīng)在同步邊界完成構(gòu)建并安全發(fā)布之后不再變更或發(fā)布不可變快照。有序枚舉不等于存檔可以忽略 comparer。如果寫(xiě)出順序用當(dāng)前文化比較在另一文化下重建可能得到不同順序甚至出現(xiàn)新的比較等價(jià)沖突。持久化應(yīng)寫(xiě)出 schema 與穩(wěn)定鍵字段重建時(shí)明確使用相同業(yè)務(wù)規(guī)則或執(zhí)行遷移。九、復(fù)雜度、常數(shù)與內(nèi)存賬本操作SortedListSortedDictionary決定成本的主要因素按鍵查找O(log n)O(log n)二分隨機(jī)訪(fǎng)問(wèn) vs 樹(shù)節(jié)點(diǎn)追蹤comparer 成本中間插入O(n)O(log n)雙數(shù)組后綴搬移 vs 樹(shù)搜索/修復(fù)刪除O(n)O(log n)雙數(shù)組左移 vs 樹(shù)摘鏈/修復(fù)按已知索引訪(fǎng)問(wèn)內(nèi)部 O(1)通常無(wú)排名索引公開(kāi) API 需按 TFM 核對(duì)順序枚舉O(n)O(n)連續(xù)掃描 vs 樹(shù)遍歷棧大 O 不告訴轉(zhuǎn)折點(diǎn)。小型集合中連續(xù)數(shù)組、較少對(duì)象和直接遍歷可能抵消 O(n) 搬移大型高頻中間更新中搬移很快成為主導(dǎo)。元素大小也重要移動(dòng)大值類(lèi)型 value 數(shù)組比移動(dòng)引用更多字節(jié)而樹(shù)節(jié)點(diǎn)又要為每條數(shù)據(jù)支付對(duì)象頭與引用。不應(yīng)寫(xiě)“一百萬(wàn) int/string 固定占 16 MB vs 44 MB”這類(lèi)無(wú)環(huán)境數(shù)字。字符串對(duì)象的內(nèi)存是否計(jì)入引用寬度、對(duì)齊、數(shù)組頭、容量余量、節(jié)點(diǎn)布局與 runtime 都會(huì)改變結(jié)果。應(yīng)用相同鍵值對(duì)、相同數(shù)量和相同運(yùn)行時(shí)做堆快照分開(kāi)容器自身、鍵值對(duì)象與臨時(shí)構(gòu)建分配。十、實(shí)戰(zhàn)場(chǎng)景配置索引和時(shí)間切片配置表在加載后基本不變又需按 ID 查詢(xún)和順序?qū)С鍪?SortedList 的候選。但若只需精確 ID 查詢(xún)不需有序遍歷Dictionary 的期望 O(1) 查找可能更直接。選 SortedList 必須有“有序”帶來(lái)的真實(shí)功能不是因?yàn)槊Q(chēng)看起來(lái)更整齊。時(shí)間切片例如按時(shí)間戳查找最近快照。二分查找得到精確鍵或插入點(diǎn)由插入點(diǎn)可找前驅(qū)/后繼未命中時(shí)~index是第一個(gè)大于查詢(xún)鍵的位置前一個(gè)就是小于查詢(xún)鍵的最大鍵。但公開(kāi) API 不一定直接暴露插入點(diǎn)不應(yīng)用反射取私有 key 數(shù)組。如果前驅(qū)/范圍查詢(xún)是核心需求可選用直接暴露 lower-bound 的專(zhuān)用結(jié)構(gòu)或封裝自有排序數(shù)組。定期熱更配置時(shí)不建議在正被游戲系統(tǒng)遍歷的 SortedList 上逐項(xiàng)修改?？稍诤笈_(tái)或加載階段構(gòu)建新實(shí)例完成完整性、重復(fù)鍵和引用校驗(yàn)后在同步邊界一次替換快照。這同時(shí)避免了枚舉失效、半更新?tīng)顟B(tài)與長(zhǎng)時(shí)間持鎖。十一、并發(fā)、序列化與 Unity 邊界SortedList 不保證多線(xiàn)程并發(fā)寫(xiě)安全。一個(gè)線(xiàn)程正在擴(kuò)容或搬移兩個(gè)數(shù)組時(shí)另一個(gè)線(xiàn)程讀取可以觀(guān)察到未定義的中間狀態(tài)。鎖必須保護(hù)完整操作和所有訪(fǎng)問(wèn)不是只鎖 key 數(shù)組寫(xiě)入。讀多寫(xiě)少的配置更適合構(gòu)建后安全發(fā)布不再修改的實(shí)例。序列化應(yīng)保存鍵值數(shù)據(jù)、schema 和必要的順序語(yǔ)義不保存私有數(shù)組容量、版本號(hào)或 comparer 對(duì)象圖。反序列化后應(yīng)在明確 comparer 下重建并檢測(cè)新規(guī)則下的重復(fù)鍵。JSON object 屬性名只是字符串復(fù)合 key 通常更適合序列化為條目數(shù)組 DTO而不是拼接成難以遷移的文本鍵。Unity 內(nèi)置序列化/JsonUtility 的容器支持不能根據(jù)桌面System.Text.Json推斷。常用做法是將按鍵排序的條目列表作為資產(chǎn)/存檔模型在加載邊界驗(yàn)證并建立運(yùn)行時(shí) SortedList。是否選 SortedList 作運(yùn)行時(shí)索引取決于更新/查詢(xún)模式不應(yīng)受 Inspector 能否直接顯示私有實(shí)現(xiàn)影響。十二、可復(fù)現(xiàn)基準(zhǔn)與測(cè)試設(shè)計(jì)比較 SortedList 和 SortedDictionary 時(shí)至少使用以下工作負(fù)載從空容器隨機(jī)順序構(gòu)建在已知最終數(shù)量時(shí)預(yù)留容量構(gòu)建按已排序 key 順序構(gòu)建按 key 的命中/未命中混合查詢(xún)順序枚舉所有條目頭部、中部、尾部和隨機(jī)刪除穩(wěn)態(tài)查詢(xún)中穿插少量更新。參數(shù)要來(lái)自業(yè)務(wù)規(guī)模鍵不能只用順序 int 代表所有復(fù)合/string comparer。報(bào)告記錄 TFM、runtime、CPU、構(gòu)建配置、數(shù)量、插入順序、命中率、分配和駐留內(nèi)存。微基準(zhǔn)只回答局部問(wèn)題Unity 最終選型還需在目標(biāo) Player 的完整配置加載/查詢(xún)場(chǎng)景中復(fù)測(cè)。正確性可使用參考模型做差分測(cè)試用普通 Dictionary 保存鍵值唯一性每步后將其 key 按相同 comparer 排序與 SortedList 枚舉結(jié)果對(duì)比。隨機(jī)生成 Add、setter、Remove、Clear 和查詢(xún)序列每步檢查 Count、鍵順序、鍵值對(duì)應(yīng)和重復(fù)鍵行為。十三、審查清單業(yè)務(wù)需要的是有序映射還是只需精確查找的哈希映射comparer 是否定義了穩(wěn)定順序零比較是否真的表示同一鍵key 在集合中是否不可變排行榜分?jǐn)?shù)等可變屬性是否被誤用為 key構(gòu)建是一次性還是持續(xù)隨機(jī)插入是否存在 O(n) 后綴搬移熱點(diǎn)是否能合理預(yù)留容量還是因過(guò)度估計(jì)浪費(fèi)兩個(gè)大數(shù)組是否依賴(lài)某個(gè)并不存在于目標(biāo) TFM 的按索引 API是否把排名索引當(dāng)成穩(wěn)定 ID忽略了中間插入會(huì)移動(dòng)后續(xù)位置Clear 后的大容量是有意復(fù)用還是未受控駐留縮容時(shí)機(jī)是否避開(kāi)熱路徑枚舉期間是否修改集合Keys/Values 是否被誤當(dāng)作獨(dú)立快照序列化是否保存 schema 和鍵語(yǔ)義重建時(shí)是否檢測(cè)新 comparer 下的沖突是否用無(wú)環(huán)境的固定 MB/倍數(shù)代替了真實(shí)堆快照與工作負(fù)載基準(zhǔn)跨線(xiàn)程讀寫(xiě)是否受同一同步協(xié)議保護(hù)或已改為構(gòu)建后不變快照十四、本篇結(jié)論SortedList 用兩個(gè)平行數(shù)組維護(hù)有序鍵值映射。二分查找使按鍵查詢(xún)?yōu)?O(log n)連續(xù)布局使枚舉和已知索引訪(fǎng)問(wèn)緊湊中間插入/刪除則因雙數(shù)組搬移為 O(n)。這些都是可從布局推導(dǎo)的成本不需要依賴(lài)無(wú)條件倍數(shù)。它的真正優(yōu)勢(shì)場(chǎng)景是更新少、查詢(xún)/有序遍歷多、容量可估且希望減少逐節(jié)點(diǎn)對(duì)象的映射。它的劣勢(shì)是持續(xù)隨機(jī)中間更新、大值搬移和索引不穩(wěn)定。如果核心需求是大量動(dòng)態(tài)插刪SortedDictionary 或?qū)Ｓ媒Y(jié)構(gòu)可能更合適如果不需有序Dictionary 可能更直接。最容易被忽略的仍然是 comparer它既定義順序也定義鍵的唯一性。只有在 comparer 穩(wěn)定、key 不變、平行數(shù)組不變式得到保護(hù)且工作負(fù)載經(jīng)目標(biāo)運(yùn)行時(shí)驗(yàn)證時(shí)這個(gè)緊湊的雙數(shù)組設(shè)計(jì)才會(huì)成為優(yōu)勢(shì)。建議實(shí)驗(yàn)對(duì)同一批鍵值分別以排序順序和隨機(jī)順序構(gòu)建 SortedList記錄構(gòu)建、查詢(xún)、枚舉、分配與駐留容量再與 SortedDictionary 做功能等價(jià)對(duì)照找到屬于你的更新比例與規(guī)模轉(zhuǎn)折點(diǎn)。下一篇SortedSet、SortedDictionary 與 SortedList 綜合選型。