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