C#集合

有兩種主要的集合類型：泛型集合和非泛型集合。 泛型集合被添加在 .NET Framework 2.0 中，并提供編譯時(shí)類型安全的集合。 因此，泛型集合通常能提供更好的性能。 構(gòu)造泛型集合時(shí)，它們接受類型形參；并在向該集合添加項(xiàng)或從該集合刪除項(xiàng)時(shí)無(wú)需在Object類型間來(lái)回轉(zhuǎn)換。

集合接口和類型

• System.Array ：用于數(shù)組，提供創(chuàng)建，操作，搜索和排序數(shù)組的方法，是所有數(shù)組的基類。
• System.Collections ：是ArrayList、Queue、Hashtable等基類，包含定義對(duì)象的各種集合。
• System.Collections.Concurrent ：提供了線程安全的集合類。
• System.Collections.Generic ：包含接口和定義泛型集合，它允許用戶創(chuàng)建強(qiáng)類型集合能提供比非泛型強(qiáng)類型集合更好的類型安全和性能等級(jí)。
• System.Collections.Specialized：包含強(qiáng)類型集合。專用于特定類型的集合類。
• System.Collections.Immutable ：包含了定義不可變的集合接口和類 。

列表List<T>

該類派生自如下接口和類：

public class List<T> : System.Collections.Generic.ICollection<T>, 
System.Collections.Generic.IEnumerable<T>, System.Collections.Generic.IList<T>, 
System.Collections.Generic.IReadOnlyCollection<T>, System.Collections.Generic.IReadOnlyList<T>, 
System.Collections.IList,System.Collections.IEnumerable,System.Collections.ICollection

創(chuàng)建列表

可以調(diào)用默認(rèn)的構(gòu)造函數(shù)創(chuàng)建列表對(duì)象。

List<int> intList = new List<int>();

使用構(gòu)造函數(shù)創(chuàng)建一個(gè)空列表，當(dāng)元素添加到列表中后，列表的容量就會(huì)擴(kuò)大為可接納4個(gè)元素，當(dāng)添加第5個(gè)元素時(shí)，列表的容量大小就會(huì)被重新設(shè)置為包含8個(gè)元素，如果8個(gè)元素還不夠 ，列表的容量大小就會(huì)被設(shè)置為16個(gè)元素，每次超出已有的容量大小后，都會(huì)將列表的容量重新設(shè)置為原來(lái)的2倍。

使用Capacity屬性可以獲取該列表的容量大小。下面將使用一個(gè)示例來(lái)說(shuō)明添加元素后，Capacity的值是如何變化的。

List<int> intList = new List<int>();
//獲取初始容量大小
Console.WriteLine("初始容量大小：" + intList.Capacity);
intList.Add(1);
Console.WriteLine($"添加了一個(gè)元素后，容量大小為：{intList.Capacity}");
//獲取或設(shè)置該內(nèi)部數(shù)據(jù)結(jié)構(gòu)在不調(diào)整大小的情況下能夠容納的元素總數(shù)
intList.Capacity = 5;
Console.WriteLine("設(shè)置了指定的容量大小為5后：" + intList.Capacity);
intList.AddRange(new[] { 2, 3, 4, 5, 6 });
Console.WriteLine($"添加了{(lán)intList.Count}個(gè)元素后，容量大小為：{intList.Capacity}");

上述的輸出結(jié)果依次為：

初始容量大?。?
添加了一個(gè)元素后，容量大小為：4
設(shè)置了指定的容量大小為5后：5
添加了6個(gè)元素后，容量大小為：10
>

如果元素添加到列表后，還有多余的容量大小，可以調(diào)用TrimExcess()方法，去除不需要的容量。

注意：如果未使用的容量小于總?cè)萘康?0％，則列表不會(huì)調(diào)整大小 。

接著上述示例執(zhí)行下述代碼：

Console.WriteLine($"原來(lái)的元素個(gè)數(shù)為：{intList.Count} 容量大小為：" + intList.Capacity);
intList.TrimExcess();
Console.WriteLine("調(diào)用了TrimExcess()方法后，容量大小為：" + intList.Capacity);
//重新調(diào)整容量大小，未使用容量小于總?cè)萘?0%
intList.Capacity = 7;
intList.TrimExcess();
Console.WriteLine($"最終元素個(gè)數(shù)為：{intList.Count} 容量大小為：" + intList.Capacity);

輸出結(jié)果為：

原來(lái)的元素個(gè)數(shù)為：6 容量大小為：10
調(diào)用了TrimExcess()方法后，容量大小為：6
最終元素個(gè)數(shù)為：6 容量大小為：7

初始化集合并設(shè)定值

intList = new List<int>() { 1, 2, 3 };
intList = new List<int> { 4, 5, 6 };

添加或插入元素

使用Add()方法可以給列表添加一個(gè)元素，使用AddRange()方法可以一次給集合添加多個(gè)元素。使用Insert()方法可以在指定位置插入元素：

intList.Add(7);
intList.AddRange(new int [] { 7, 8, 9 });
intList.Insert(2, 0);
//4  5  0   6   7   7   8   9   

訪問(wèn)元素

實(shí)現(xiàn)了IList和IList<T>接口的所有類都提供了一個(gè)索引器，因此可以使用索引下標(biāo)的形式進(jìn)行訪問(wèn)指定索引位置的元素。索引下標(biāo)從0開(kāi)始。

> Console.Write(intList[2]);
0

因?yàn)?code>List<T>集合類實(shí)現(xiàn)了IEnumerate接口，所以可以使用foreach語(yǔ)句進(jìn)行遍歷集合中的元素。

刪除元素

使用RemoveAt()方法移除指定索引位置的元素，使用Remove()方法移除指定元素。使用RemoveRange()方法可以從集合中刪除多個(gè)元素。使用RemoveAll()方法可以刪除集合中的所有的元素。

注意：推薦使用RemoveAt()方法按索引刪除元素，因?yàn)樗?code>Remove()方法執(zhí)行的要快，Remove()方法會(huì)先在集合中搜索元素，搜索的過(guò)程中會(huì)調(diào)用Equals()方法，然后使用IndexOf()方法獲取元素的索引，再使用該索引刪除元素。

intList.RemoveAt(2);//刪除索引2的元素
intList.Remove(7);//刪除元素7
intList.RemoveRange(4, 2);//刪除索引為4及之后的2個(gè)元素
intList.RemoveAll(a => a > 5); //刪除值大于5的元素

搜索元素

可以通過(guò)索引或元素本身搜索元素?？梢允褂玫姆椒ㄓ校?code>IndexOf()、LastIndexOf()、FindIndex()、FindLastIndex()、Find()、FindLast()等。判斷元素是否存在可以使用Exists()方法。除了這些方法，實(shí)際應(yīng)用中還包括Linq可以使用的方法。具體使用，請(qǐng)查看官方文檔。

排序

List<T>類可以使用Sort()方法對(duì)元素進(jìn)行排序。Sort()方法有如下幾個(gè)重載方法：

public void Sort(int index, int count, IComparer<T> comparer);
public void Sort(Comparison<T> comparison);
public void Sort();
public void Sort(IComparer<T> comparer);

只有集合中的元素實(shí)現(xiàn)了IComparable接口，才能使用不帶參數(shù)的Sort()方法。

如果需要按照元素類型 不 默認(rèn)支持的方式排序，就需要使用其他重載方法，比如傳遞一個(gè)實(shí)現(xiàn)了IComparer<T>接口的對(duì)象。

下面將用一個(gè)具體的示例進(jìn)行說(shuō)明：

public class Racer : IComparable<Racer>
{
    public int Id { get; }
    public string FirstName { get; set; }
    public string LastName { get; set; }
    public string Country { get; set; }
    public int Wins { get; set; }
    //實(shí)現(xiàn)接口中的方法
    public int CompareTo(Racer other)
    {
        int compare = LastName?.CompareTo(other?.LastName) ?? -1;
        if (compare == 0)
        {
            return FirstName?.CompareTo(other?.FirstName) ?? -1;
        }
        return compare;
    }
    //定義構(gòu)造函數(shù)
    public Racer(int id, string firstName, string lastName, string country, int wins)
    {
        this.Id = id;
        this.FirstName = firstName;
        this.LastName = lastName;
        this.Country = country;
        this.Wins = wins;
    }
    //定義另一個(gè)構(gòu)造函數(shù)，并調(diào)用上述構(gòu)造函數(shù)
    public Racer(int id, string firstName, string lastName, string country)
        : this(id, firstName, lastName, country, wins: 0) { }
    //重寫object的Tostring()方法
    public override string ToString()
    {
        return $"{FirstName} {LastName}";
    }
}

上述的類直接實(shí)現(xiàn)了IComparable<T>泛型接口，所以可以直接使用不帶參數(shù)的Sort()方法進(jìn)行排序，排序的依據(jù)基于重寫的CompareTo()方法。

var racers = new List<Racer> {
    new Racer(1,"zhang","bsan","中國(guó)"),
    new Racer(3,"li","asi","中國(guó)"),
    new Racer(2,"wang","dwu","中國(guó)")
};
racers.Sort();

執(zhí)行上述語(yǔ)句，將會(huì)按照LastName進(jìn)行排序后輸出，依次為li asi、zhang bsan、wang dwu。

對(duì)上述示例進(jìn)行擴(kuò)展，使用傳遞一個(gè)實(shí)現(xiàn)了IComparer<T>接口的對(duì)象進(jìn)行排序。如下：

public class RacerComparer : IComparer<Racer>
{
    //定義一個(gè)枚舉，可以直接通過(guò)類名.枚舉名進(jìn)行訪問(wèn)
    public enum CompareType
    {
        FirstName,
        LastName,
        Country,
        Wins
    }
    //定義枚舉變量
    private CompareType _compareType;
    //定義構(gòu)造函數(shù)，通過(guò)外部指定枚舉類型
    public RacerComparer(CompareType compareType)
    {
        _compareType = compareType;
    }
    //重寫接口方法
    public int Compare(Racer x, Racer y)
    {
        if (x == null && y == null) return 0;
        if (x == null) return -1;
        if (y == null) return 1;
        int result;
        switch (_compareType)
        {
            case CompareType.FirstName:
                return string.Compare(x.FirstName, y.FirstName);
            case CompareType.LastName:
                return string.Compare(x.LastName, y.LastName);
            case CompareType.Country:
                result = string.Compare(x.Country, y.Country);
                if (result == 0)
                    return string.Compare(x.LastName, y.LastName);
                else return result;
            case CompareType.Wins:
                return x.Wins.CompareTo(y.Wins);
            default:
                throw new ArgumentException("Invalid Compare Type");
        }
    }
}

上述類RacerComparer 實(shí)現(xiàn)了泛型接口IComparer<T>，其中泛型類型為Racer（實(shí)現(xiàn)IComparer<T>接口中的泛型類型T應(yīng)該是將要進(jìn)行排序的元素的類型），并重寫了Compare()方法，因此可以調(diào)用Srot(IComparer><T>)方法進(jìn)行排序。

var racers = new List<Racer> {
    new Racer(1,"zhang","bsan","中國(guó)"),
    new Racer(3,"li","asi","中國(guó)"),
    new Racer(2,"wang","dwu","中國(guó)")
};
racers.Sort(new RacerComparer(RacerComparer.CompareType.FirstName));
//將會(huì)按照FirstName進(jìn)行排序

還可以調(diào)用Sort(Comparison<T> comparison)進(jìn)行排序，Comparison<T>是一個(gè)泛型委托，它的定義如下：

public delegate int Comparison<in T>(T x, T y);

它需要傳入兩個(gè)T類型的參數(shù)，返回類型為int。如果參數(shù)值相等，該方法返回0；如果第一個(gè)參數(shù)比第二個(gè)小，返回一個(gè)小于0的值；否則，返回一個(gè)大于0的值。

比如示例中如果按照Id進(jìn)行排序，可以使用如下方法調(diào)用：

//由于是委托，此處可以使用lambda表達(dá)式
racers.Sort((r1, r2) => r1.Id.CompareTo(r2.Id));

上述將會(huì)按照Id升序排序。

如果使用了Sort()進(jìn)行排序后，可以調(diào)用Reverse()方法，逆轉(zhuǎn)整個(gè)集合的排序。

只讀集合

可以調(diào)用List<T>集合的AsReadOnly()方法返回ReadOnlyCollection<T>類型的對(duì)象。ReadOnlyCollection<T>類實(shí)現(xiàn)的接口與List<T>集合相同，除此之外還實(shí)現(xiàn)了IReadOnlyCollection<T>和IReadOnlyList接口。因?yàn)檫@些接口的成員，集合不能修改。所有修改集合的方法和屬性都拋出NotSupportedException異常。

public class ReadOnlyCollection<T> : IList<T>, ICollection<T>, IEnumerable<T>, 
IEnumerable, IList, ICollection, IReadOnlyList<T>, IReadOnlyCollection<T>

隊(duì)列Queue<T>

隊(duì)列是其元素以先進(jìn)先出（Firstin，F(xiàn)irstout，F(xiàn)IFO）的方式來(lái)處理的集合，先放入隊(duì)列中的元素會(huì)先讀取。隊(duì)列使用System.Collections.Generic命名空間中的泛型類Queue<T>實(shí)現(xiàn)，它的聲明如下：

[System.Runtime.InteropServices.ComVisible(false)]
public class Queue<T> : System.Collections.Generic.IEnumerable<T>, 
System.Collections.Generic.IReadOnlyCollection<T>, System.Collections.ICollection

由于Queue<T>沒(méi)有實(shí)現(xiàn)ICollection<T>泛型接口，所以不能使用這個(gè)接口中定義的Add()和Remove()方法操作元素。也因?yàn)?code>Queue<T>沒(méi)有實(shí)現(xiàn)IList<T>泛型接口，所以也不能使用索引下標(biāo)的方式訪問(wèn)隊(duì)列。

Queue<T>常用方法和屬性說(shuō)明：

Dequeue() ：刪除并返回隊(duì)列開(kāi)頭的元素。如果隊(duì)列中沒(méi)有元素，在調(diào)用該方法時(shí)，將會(huì)拋出一個(gè)InvalidOperationException類型的異常。

Enqueue(T) ：將元素添加到隊(duì)列的末尾。

Peek() ：返回但不刪除隊(duì)列開(kāi)頭的元素。

TrimExcess() ：如果該數(shù)量小于當(dāng)前容量的90％，則將容量設(shè)置為隊(duì)列的實(shí)際元素?cái)?shù)。

Count ：獲取隊(duì)列中的元素的個(gè)數(shù)

可以使用默認(rèn)的構(gòu)造函數(shù)創(chuàng)建一個(gè)空隊(duì)列，也可以使用構(gòu)造函數(shù)指定容量。在把元素添加到隊(duì)列中時(shí)，如果沒(méi)有指定容量，將會(huì)類似于List<T>類，隊(duì)列的容量也總是根據(jù)需要成倍增加，從而包含4、8、16和32個(gè)元素等。

下面將使用一個(gè)復(fù)雜的示例說(shuō)明隊(duì)列是如何使用的。首先定義一個(gè)簡(jiǎn)單的類：

public class Document
{
    public string Title { get; }
    public string Content { get; }

    public Document(string title, string content)
    {
        this.Title = title;
        this.Content = content;
    }
}

接著為這個(gè)類進(jìn)行隊(duì)列寫入和讀取操作：

public class DocumentManager
{
    private readonly Queue<Document> _documentQueue = new Queue<Document>();
    //向隊(duì)列中添加元素
    public void AddDocument(Document doc)
    {
        //因?yàn)楹竺鎸⒁褂枚嗑€程，為了避免死鎖，進(jìn)行l(wèi)ock語(yǔ)句限制
        lock (this)
        {
            _documentQueue.Enqueue(doc);
        }
    }
    //獲取隊(duì)列中的元素
    public Document GetDocument()
    {
        Document doc = null;
        lock (this)
        {
            doc = _documentQueue.Dequeue();
        }
        return doc;
    }
    //隊(duì)列中是否還有元素未讀出
    public bool IsDocumentAvailable => _documentQueue.Count > 0;
}

然后定義一個(gè)操作此類的對(duì)外開(kāi)放的類：

public class ProcessDocuments
{
    private DocumentManager _documentManager;

    protected ProcessDocuments(DocumentManager dm)
    {
        _documentManager = dm ?? throw new ArgumentNullException(nameof(dm));
    }

    protected async Task Run()
    {
        while (true)
        {
            if (_documentManager.IsDocumentAvailable)
            {
                Document doc = _documentManager.GetDocument();
                Console.WriteLine(doc.Title + ":" + doc.Content);
            }
            //顯式的指定間隔時(shí)間，將會(huì)在此等待，從而執(zhí)行該方法之外的代碼部分
            await Task.Delay(new Random().Next(1000));
        }
    }
    //對(duì)外開(kāi)放的調(diào)用方法
    public static void Start(DocumentManager dm)
    {
        //啟動(dòng)一個(gè)新的任務(wù)
        Task.Run(new ProcessDocuments(dm).Run);
    }
}

調(diào)用代碼如下：

public static void Run()
{
    var dm = new DocumentManager();
    ProcessDocuments.Start(dm);

    for (int i = 0; i < 1000; i++)
    {
        var doc = new Document("Doc_" + i, "Content_" + i);
        dm.AddDocument(doc);
        Console.WriteLine("添加了document:Doc_" + i);
        System.Threading.Thread.Sleep(new Random().Next(1000));
    }
}

棧Stack<T>

棧是一個(gè)后進(jìn)先出（Lastin，F(xiàn)irstout，LIFO）的集合，最后添加到棧中的元素會(huì)最先讀取。它和隊(duì)列非常的類似，只是讀取元素的方法不同。棧在.NET中的聲明如下：

[System.Runtime.InteropServices.ComVisible(false)]
public class Stack<T> : System.Collections.Generic.IEnumerable<T>, 
System.Collections.Generic.IReadOnlyCollection<T>, System.Collections.ICollection

常用的方法和屬性有 ：

Pop() ：刪除并返回棧的頂部的一元素。如果棧沒(méi)有元素，調(diào)用該方法將會(huì)拋出InvalidOperationException異常。

Push(T) :在棧的頂部插入一個(gè)元素。

Peek() ：返回但不刪除棧的頂部的一個(gè)元素。

Contains(T) ：判斷一個(gè)元素是否在棧中。

Count ：返回棧中元素的個(gè)數(shù)。

下面使用一個(gè)簡(jiǎn)單的示例來(lái)說(shuō)明棧的相關(guān)操作：

var mystacks = new Stack<int>();
mystacks.Push(1);
mystacks.Push(2);
mystacks.Push(3);
foreach(var num in mystacks)
{
    Console.Write(num+"\t"); //將會(huì)輸出：3   2   1
}
Console.WriteLine();
while (mystacks.Count > 0)
{
    Console.Write(mystacks.Pop() + "\t");
}

鏈表LinkedList<T>

LinkedList<T>是一個(gè)雙向鏈表，其元素指向它前面和后面的元素。

鏈表的優(yōu)點(diǎn)是，如果將元素插入列表的中間位置，使用鏈表就會(huì)非常快。在往鏈表插入一個(gè)新的元素時(shí)，只需要修改上一個(gè)元素的Next引用和下一個(gè)元素的Previous引用，使它們的引用指向新插入的元素。【刪除原因：表述不準(zhǔn)確，Next和Previous都是獲取值不能設(shè)置值】

鏈表的缺點(diǎn)是，鏈表的元素只能一個(gè)接一個(gè)地訪問(wèn)，這需要較長(zhǎng)的時(shí)間來(lái)查找位于鏈表中間或尾部的元素。

LinkedList<T>在.NET中的定義：

[System.Runtime.InteropServices.ComVisible(false)]
public class LinkedList<T> : System.Collections.Generic.ICollection<T>,
System.Collections.Generic.IEnumerable<T>, System.Collections.Generic.IReadOnlyCollection<T>,
System.Collections.ICollection, System.Runtime.Serialization.IDeserializationCallback,
System.Runtime.Serialization.ISerializable

操作鏈表時(shí)，離不開(kāi)泛型類LinkedListNode<T>，它表示LinkedList<T>中的節(jié)點(diǎn)。LinkedListNode<T>是一個(gè)獨(dú)立定義的類，并不繼承自LinkedList<T>，但是鏈表LinkedList<T>包含的元素節(jié)點(diǎn)均來(lái)自于LinkedListNode<T>，以下為鏈表LinkedList<T>部分常用方法和屬性：

public LinkedListNode<T> Last { get; }
public LinkedListNode<T> First { get; }
public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value);
public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value);
public void AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode);
public LinkedListNode<T> AddFirst(T value);
public void AddFirst(LinkedListNode<T> node);
public LinkedListNode<T> AddLast(T value);
public void AddLast(LinkedListNode<T> node);
public LinkedListNode<T> Find(T value);
public LinkedListNode<T> FindLast(T value);

上述大多數(shù)都與LinkedListNode<T>緊密相關(guān)：

[System.Runtime.InteropServices.ComVisible(false)]
public sealed class LinkedListNode<T>
{
    public LinkedListNode(T value);
    public LinkedList<T> List { get; }
    public LinkedListNode<T> Next { get; }
    public LinkedListNode<T> Previous { get; }
    public T Value { get; set; }
}

通過(guò)定義可以知道，使用LinkedListNode<T>類，可以獲得列表中的下一個(gè)元素和上一個(gè)元素。LinkedListNode<T>定義了屬性List（返回對(duì)應(yīng)的LinkedList<T>對(duì)象）、Next、Previous和Value（返回與節(jié)點(diǎn)相關(guān)的元素，其類型是T）。并且它提供的屬性大多數(shù)都是可讀不可寫。

注：LinkedListNode<T>的成員很少，幾乎提供的全是讀取的操作，因此實(shí)際操作元素比如添加、刪除等，還是通過(guò)LinkedList<T>的成員方法（如上述展示的方法）進(jìn)行調(diào)用。

下面將使用一個(gè)完整的示例說(shuō)明如何使用鏈表進(jìn)行操作，該示例使用鏈表讓文檔按照優(yōu)先級(jí)進(jìn)行排序顯示，并且在鏈表中添加新文檔時(shí)，新添加的文檔應(yīng)該放在優(yōu)先級(jí)相同的最后一個(gè)文檔的后面。

首先定義一個(gè)簡(jiǎn)單的類Document_V2，它包括基本的文檔信息已經(jīng)優(yōu)先級(jí)：

public class Document_V2
{
    public string Title { get; private set; }
    public string Content { get; private set; }
    public byte Priority { get; private set; }

    public Document_V2(string title,string content,byte priority)
    {
        this.Title = title;
        this.Content = content;
        this.Priority = priority;
    }
}

接著定義一個(gè)操作該類鏈表的類：

public class PriorityDocumentManager
{
    //集合LinkedList<Document_V2>包含多個(gè)LinkedListNode<Document_V2>類型的元素
    private readonly LinkedList<Document_V2> _documentList;
    //定義包含LinkedListNode<Document_V2>類型的List集合，便于后續(xù)使用Next和Previous屬性進(jìn)行遍歷
    private readonly List<LinkedListNode<Document_V2>> _priorityNodes;

    public PriorityDocumentManager()
    {
        _documentList = new LinkedList<Document_V2>();
        _priorityNodes = new List<LinkedListNode<Document_V2>>(10);
        for (int i = 0; i < 10; i++)
        {
            //添加10個(gè)類型為Document_V2的空節(jié)點(diǎn)（節(jié)點(diǎn)的Value及其他屬性均為null）
            _priorityNodes.Add(new LinkedListNode<Document_V2>(null));
        }
    }

    public void AddDocument(Document_V2 d)
    {
        if (d == null) throw new ArgumentNullException("d");
        AddDocumentToPriorityNode(d, d.Priority);
    }
    private void AddDocumentToPriorityNode(Document_V2 doc, int priority)
    {
        if (priority > 9 || priority < 0)
        {
            throw new ArgumentException("等級(jí)必須為0~9");
        }
        if (_priorityNodes[priority].Value == null)
        {
            --priority;
            if (priority >= 0)
            {
                //遞歸調(diào)用該方法
                AddDocumentToPriorityNode(doc, priority);
            }
            else
            {
                _documentList.AddLast(doc);
                _priorityNodes[doc.Priority] = _documentList.Last;
            }
            return;
        }
        else
        {
            LinkedListNode<Document_V2> prioNode = _priorityNodes[priority];
            //判斷優(yōu)先級(jí)是否相同
            if (priority == doc.Priority)
            {
                _documentList.AddAfter(prioNode, doc);
                _priorityNodes[doc.Priority] = prioNode.Next;
            }
            else
            {
                LinkedListNode<Document_V2> firstPrioNode = prioNode;
                //循環(huán)遍歷所有鏈接節(jié)點(diǎn)
                while (firstPrioNode.Previous != null 
                    && firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)
                {
                    firstPrioNode = prioNode.Previous;
                    prioNode = firstPrioNode;
                }
                _documentList.AddBefore(firstPrioNode, doc);
                _priorityNodes[doc.Priority] = firstPrioNode.Previous;
            }
        }
    }
    public void DisplayAllNodes()
    {
        foreach (Document_V2 doc in _documentList)
        {
            Console.WriteLine($"priority:{doc.Priority},tilte:{doc.Title}");
        }
    }
    public Document_V2 GetDocument()
    {
        Document_V2 doc = _documentList.First.Value;
        _documentList.RemoveFirst();
        return doc;
    }
}

調(diào)用上述執(zhí)行：

public static void Run()
{
    var pdm = new PriorityDocumentManager();

    pdm.AddDocument(new Document_V2("one", "示例一", 8));
    pdm.AddDocument(new Document_V2("two", "示例二", 3));
    pdm.AddDocument(new Document_V2("three", "示例三", 4));
    pdm.AddDocument(new Document_V2("for", "示例四", 8));
    pdm.AddDocument(new Document_V2("five", "示例五", 1));
    pdm.AddDocument(new Document_V2("six", "示例六", 9));
    pdm.AddDocument(new Document_V2("seven", "示例七", 1));
    pdm.AddDocument(new Document_V2("eight", "示例八", 1));
    pdm.DisplayAllNodes();
}

輸出結(jié)果：

priority:9,title:six
priority:8,title:one
priority:8,title:for
priority:4,title:three
priority:3,title:two
priority:1,title:five
priority:1,title:seven
priority:1,title:eight

有序列表SortedList<TKey, TValue>

使用SortedList<TKey, TValue>類可以基于鍵對(duì)集合排序。

使用一個(gè)簡(jiǎn)單的示例對(duì)其進(jìn)行操作說(shuō)明：

var mysortedlist = new SortedList<string, string>();
mysortedlist.Add("one", "一");
mysortedlist.Add("two", "二");
mysortedlist.Add("three", "三");
mysortedlist.Add("four", "四");
//還可以使用索引的形式添加元素，索引參數(shù)是鍵
mysortedlist["five"] = "五";
//修改值
mysortedlist["three"] = "3";

foreach (var item in mysortedlist)
{
    Console.WriteLine($"{item.Key}:{item.Value}");
}

上述將會(huì)按照鍵自動(dòng)的進(jìn)行排序顯示，顯示結(jié)果：

five:五
four:四
one:一
three:3
two:二

字典Dictionary<TKey, TValue>

字典表示一種非常復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，由鍵和值組成，這種數(shù)據(jù)結(jié)構(gòu)允許按照某個(gè)鍵來(lái)訪問(wèn)元素。字典也被稱為映射或散列表。

字典初始化

之前只能先實(shí)例一個(gè)字典對(duì)象，然后使用Add()方法添加元素，在C#6定義了一個(gè)新的語(yǔ)法，可以在聲明的同時(shí)初始化字典，例如：

var dic = new Dictionary<int, string>()
{
    //第一元素的鍵是100
    [100] = "第一個(gè)元素",
    [200] = "第二個(gè)元素"
};

鍵的類型

字典類要確定元素的位置，它就要調(diào)用GetHashCode()方法，GetHashCode()方法返回的int由字典用于計(jì)算在對(duì)應(yīng)位置放置元素的索引，因此用作字典中的鍵的類型必須重寫Object類的GetHashCode()方法。GetHashCode()方法的實(shí)現(xiàn)代碼必須滿足如下要求：

• 相同的對(duì)象應(yīng)該總是返回相同的值。
• 不同的對(duì)象可以返回相同的值。
• 不能拋出異常。
• 至少使用一個(gè)實(shí)例字段。
• 散列代碼（調(diào)用GetHashCode方法得到的值）在對(duì)象的生存期中不發(fā)生變化。

除了必須要滿足的要求外，最好還滿足如下要求：

• 它應(yīng)該執(zhí)行的比較快，計(jì)算開(kāi)銷不大。
• 散列代碼值應(yīng)平均分布在int可以存儲(chǔ)的整個(gè)數(shù)字范圍內(nèi)。

注意：字典的性能 取決于GetHashCode()方法的實(shí)現(xiàn)代碼。

通過(guò)GetHashCode得到的散列代碼值的范圍應(yīng)該盡可能的分布在int可以存儲(chǔ)的整個(gè)數(shù)字范圍內(nèi)，避免兩個(gè)鍵返回的散列代碼值得到相同的索引（字典中的索引包含一個(gè)到值的鏈接，一個(gè)索引項(xiàng)可以關(guān)聯(lián)多個(gè)值，此處的索引不是指索引下標(biāo)），這會(huì)降低性能，因?yàn)樽值漕愋枰獙ふ易罱目捎每臻e位置來(lái)存儲(chǔ)第二個(gè)數(shù)據(jù)項(xiàng)，這需要進(jìn)行一定的搜索，如果在排序時(shí)許多鍵都有相同的索引，這類沖突就更可能出現(xiàn)，所以，當(dāng)計(jì)算出來(lái)的散列代碼值平均分布在int.MinValue和int.MaxValue之間時(shí)，這種風(fēng)險(xiǎn)會(huì)降低到最小。

除了實(shí)現(xiàn)GetHashCode()方法之外，鍵類型還必須實(shí)現(xiàn)IEquatable<T>.EQuals()方法，或重寫Object類的Equals()方法。因?yàn)椴煌逆I對(duì)象可能返回相同的散列代碼，所以字典使用Equals()方法來(lái)比較鍵。字典檢查兩個(gè)鍵A和B是否相等，并調(diào)用A.Equals(B)方法。這說(shuō)明必須確保下述條件總是成立：

如果A.Equals(B)方法返回true，則A.GetHashCode()和B.GetHashCode()方法必須總是返回相同的散列代碼。

注意：如果為Equals()方法提供了重寫版本，但沒(méi)有提供GetHashCode()方法的重寫版本，C#編譯器就會(huì)顯示一個(gè)編譯警告。

綜上所述，應(yīng)用在字典中的鍵，必須實(shí)現(xiàn)或重寫GetHashCode()和IEquatable<T>.EQuals()方法。如果這兩個(gè)方法都沒(méi)有實(shí)現(xiàn)，

可以創(chuàng)建一個(gè)實(shí)現(xiàn)IEqualityComparer<T>接口的比較器，IEqualityComparer<T>接口定義了GetHashCode()和Equals()方法，并將傳遞的對(duì)象作為參數(shù)，因此可以提供與對(duì)象類型不同的實(shí)現(xiàn)方式。Dictionary<TKey,TValue>構(gòu)造函數(shù)的一個(gè)重載版本允許傳遞一個(gè)實(shí)現(xiàn)了IEqualityComparer<T>接口的對(duì)象。如果把這個(gè)對(duì)象賦予字典，該類就用于生成散列代碼并比較鍵。

下面通過(guò)一個(gè)示例進(jìn)行說(shuō)明。首先創(chuàng)建字典中的鍵將要使用到的類型：

public struct EmployeeId : IEquatable<EmployeeId>
{
    private readonly char prefix;
    private readonly int number;

    public EmployeeId(string id)
    {
        //System.Diagnostics.Contracts.Contract.Requires<ArgumentNullException>(id != null);
        prefix = (id.ToUpper())[0];
        int numLength = id.Length - 1;
        try
        {
            number = int.Parse(id.Substring(1, numLength > 6 ? 6 : numLength));
        }
        catch (Exception)
        {
            throw new Exception("EmployeeId格式錯(cuò)誤");
        }
    }
    
    public override string ToString()
    {
        return prefix.ToString() + $"{number,6:000000}";
    }
    //重寫GetHashCode()方法
    public override int GetHashCode()
    {
        //此條語(yǔ)句只是為了使得到的值能夠盡可能的平均到int范圍
        //將數(shù)字向左移動(dòng)16位，再與原數(shù)字進(jìn)行異或操作，得到的結(jié)果乘以16進(jìn)制數(shù)15051505
        return (number ^ number << 16) * 0x15051505;
    }
    //必須實(shí)現(xiàn)Equals()方法
    public bool Equals(EmployeeId other)
    {
        //return (_prefix == other?._prefix && _number == other?._number);
        return (prefix == other.prefix && number == other.number);
    }

    public override bool Equals(object obj)
    {
        return Equals((EmployeeId)obj);
    }
    //使用 operator 關(guān)鍵字重載內(nèi)置運(yùn)算符==
    public static bool operator ==(EmployeeId left, EmployeeId right)
    {
        return left.Equals(right);
    }
    //使用 operator 關(guān)鍵字重載內(nèi)置運(yùn)算符!=
    public static bool operator !=(EmployeeId left, EmployeeId right) => !(left == right);
}

接著創(chuàng)建字典中的值對(duì)應(yīng)的類型：

public class Employee
{
    private string name;
    private decimal salary;
    private readonly EmployeeId id;

    public Employee(EmployeeId id, string name, decimal salary)
    {
        this.id = id;
        this.name = name;
        this.salary = salary;
    }

    public override string ToString()
    {
        return $"{id.ToString()}:{name,-20} {salary:C}";
    }
}

定義字典，并調(diào)用：

public static void Run()
{
    var idTony = new EmployeeId("C3755");
    var tony = new Employee(idTony, "Tony Stewart", 379025.00m);

    var idCarl = new EmployeeId("F3547");
    var carl = new Employee(idCarl, "Carl Edwards", 403466.00m);

    var idKevin = new EmployeeId("C3386");
    var kevin = new Employee(idKevin, "kevin Harwick", 415261.00m);

    //字典使用EmployeeId對(duì)象來(lái)索引
    var employees = new Dictionary<EmployeeId, Employee>(5)
    {
        [idTony] = tony,
        [idCarl] = carl,
        [idKevin] = kevin
    };

    foreach (var employee in employees.Values)
    {
        Console.WriteLine(employee);
    }
}

Lookup<TKey,TElement>

Lookup<TKey,TElement>類非常類似于Dictionary<TKey,TValue>類，但是Lookup<TKey,TElement>表示每個(gè)映射到一個(gè)或多個(gè)值的鍵集合，也就是它的鍵可以映射到一個(gè)或多個(gè)值，Lookup<TKey,TElement>中的TElement表示的是Lookup<TKey,TElement>中每個(gè)IEnumerable<T>值的元素類型。所以要獲取其中的每個(gè)元素，可以使用循環(huán)進(jìn)行遍歷：

var racers = new List<Racer>();
racers.Add(new Racer(1, "zhang", "san", "zhongguo"));
racers.Add(new Racer(2, "li", "si", "riben"));
racers.Add(new Racer(3, "wang", "wu", "zhongguo"));
racers.Add(new Racer(4, "zhao", "liu", "meiguo"));

var lookupRacers= racers.ToLookup(r => r.Country);
foreach (var item in lookupRacers)
{
    foreach(Racer r  in lookupRacers[item.Key])
    {
        Console.WriteLine($"{item.Key}:{r.ToString()}");
    }
}

有序字典SortedDictionary<Tkey,TValue>

SortedDictionary<TKey,TValue>和SortedList<TKey,TValue>功能類似，但因?yàn)?code>SortedList<Tkey,TValue>實(shí)現(xiàn)為一個(gè)基于數(shù)組的列表，而SortedDictionary<TKey,TValue>類實(shí)現(xiàn)為一個(gè)字典，所以它們有不同的特征。

• SortedList<TKey,TValue>使用的內(nèi)存比SortedDictionary<TKey,TValue>少。
• SortedDictionary<TKey,TValue>的元素插入和刪除操作比較快。
• 在用已排好序的數(shù)據(jù)填充集合時(shí)，若不需要修改容量，SortedList<TKey,TValue>就比較快。

注意：SortedList使用的內(nèi)存比SortedDictionary少，但SortedDictionary在插入和刪除未排序的數(shù)據(jù)時(shí)比較快。

SortedDictionary<TKey,TValue>是一個(gè)二叉搜索樹(shù)，其中的元素根據(jù)鍵來(lái)排序。該鍵類型必須實(shí)現(xiàn)IComparable<Tkey>接口。如果鍵的類型不能排序，則可以創(chuàng)建一個(gè)實(shí)現(xiàn)了IComparer<Tkey>接口的比較器，將比較器用作有序字典的構(gòu)造函數(shù)的一個(gè)參數(shù)。

集Set

集（set）是包含不重復(fù)的元素的集合。主要有兩個(gè)集，HashSet<T>和SortedSet<T>，它們都實(shí)現(xiàn)ISet<T>接口，其中，HashSet<T>集包含不重復(fù)元素的無(wú)序列表，SortedSet<T>集包含不重復(fù)元素的有序列表。

ISet<T>常用方法：

• bool Add(T item)：向當(dāng)前集添加元素并返回一個(gè)值以指示元素是否已成功添加。
• void ExceptWith(IEnumerable<T> other)：從當(dāng)前集中刪除指定集合中的所有元素。
• bool IsSubsetOf(IEnumerable<T> other)：確定集合是否是指定集合的子集。
• bool IsSupersetOf(IEnumerable<T> other)：確定當(dāng)前集是否是指定集合的超集。
• bool Overlaps(IEnumerable<T> other)：確定當(dāng)前集是否與指定集合重疊。
• void UnionWith(IEnumerable<T> other)：修改當(dāng)前集，使其包含當(dāng)前集，指定集合或兩者中存在的所有元素。

var hsA = new HashSet<string>() { "one", "two", "three" };
var hsB = new HashSet<string>() { "two", "three", "four" };
if (hsA.Add("five"))
{
    Console.WriteLine("添加了five");
}
if (!hsA.Add("two"))
{
    Console.WriteLine("已經(jīng)存在了two");
}
var hsM = new HashSet<string>() { "one", "two", "three", "four", "five", "six" };

//hsA的每個(gè)元素是否都包含在hsB中
if (hsA.IsSubsetOf(hsB))//false
{
    Console.WriteLine("hsA是hsB的子集");
}
if (hsA.IsSubsetOf(hsM))//true
{
    Console.WriteLine("hsA是hsM的子集");
}
//hsA是否是hsB的超集
if (hsA.IsSupersetOf(hsB))//false
{
    Console.WriteLine("hsA是hsB的超集");
}
if (hsM.IsSupersetOf(hsB))//true
{
    Console.WriteLine("hsM是hsB的超集");
}
//判斷hsA是否與hsB有公共元素
if (hsA.Overlaps(hsB))//true
{
    Console.WriteLine("hsA與hsB包含共同元素");
}

var allhs = new SortedSet<string>(hsA);
allhs.UnionWith(hsB);
allhs.UnionWith(hsM);
foreach (var n in allhs)
{
    Console.Write(n + "\t");
}
var ex = new HashSet<string>() { "five", "three" };
//刪除ex包含的元素
allhs.ExceptWith(ex);
Console.WriteLine();
Console.WriteLine("刪除后：");
foreach (var n in allhs)
{
    Console.Write(n + "\t");
}

性能

集合的性能決定了操作時(shí)應(yīng)該選擇哪種集合。在MSDN文檔中，集合的方法常常有性能提示，給出了以大寫O記號(hào)表示的操作時(shí)間：

• O(1)：表示無(wú)論集合中有多少數(shù)據(jù)項(xiàng)，這個(gè)操作需要的時(shí)間都不變。
• O(n)：表示對(duì)于集合執(zhí)行一個(gè)操作需要的時(shí)間在最壞情況下是N。
• O(log n)：表示操作需要的時(shí)間隨著集合中元素的增加而增加，但每個(gè)元素需要增加的時(shí)間不是線性的，而是成對(duì)數(shù)曲線。

下表列出了集合類執(zhí)行不同操作的性能，如果單元格中有多個(gè)大O值，表示若集合需要重置大小，該操作就需要一定的時(shí)間。一般重置大小出現(xiàn)在集合的容量不足以滿足需要添加的元素總個(gè)數(shù)，因此最好避免重置集合的大小，而應(yīng)把集合的容量設(shè)置為一個(gè)可以包含所有元素的值。

如果表單元格的內(nèi)容是n/a（代表not applicable），就表示這個(gè)操作不能應(yīng)用于這個(gè)集合類型。

參考資源

• 《C#高級(jí)編程（第10版）》
• C#集合和數(shù)據(jù)結(jié)構(gòu)

本文后續(xù)會(huì)隨著知識(shí)的積累不斷補(bǔ)充和更新，內(nèi)容如有錯(cuò)誤，歡迎指正。

最后一次更新時(shí)間 ：2018-07-06