无论是常用的List<T>、Hashtable还是ListDictionary<TKey,TValue>，在保存值的时候都是无序的，而今天要介绍的集合类SortedList和SortedList<TKey,TValue>在保存值的时候是有序保存。

SortedList之二分查找法

一个集合有序，意味着什么？意味着可以利用一些算法来提高遍历集合时的效率，最常见的就是运用二分查找法，SortedList集合的核心就是运用二分查找。

SortedList保存数据时和哈希表一样用Key-Value的方式进行存储，但不同的是，它把Key和Value分别保存在两个object[]数组中，每次插入删除操作都会保持这两个object[]大小的同步性。

SortedList在初始化时如果不指定大小，则会给一个默认的十六进制值0x10（16），在添加操作中，如果容量不足则会自动扩充为2倍容量，这些与ArrayList和Hashtable相同。

SortedList的独特之处在于它保证数据的有序性，这点是如何保证呢？

原来，在Add（key，value）方法中，SortedList会首先用二分查找插入的key值，如果有重复项，则报错，如果没有重复项，则根据key值大小，比较得出在集合中的位置，然后插入到该位置中，代码如下：

public virtual void Add(object key, object value){    if (key == null)    {        throw new ArgumentNullException("key", Environment.GetResourceString("ArgumentNull_Key"));    }    //调用Array的静态方法进行二分查找。    int index = Array.BinarySearch(this.keys, 0, this._size, key, this.comparer);    if (index >= 0)    {        throw new ArgumentException(Environment.GetResourceString("Argument_AddingDuplicate__", new object[] { this.GetKey(index), key }));    }    this.Insert(~index, key, value);}

二分查找的时间复杂度为O（LogN），所以SortedList的Add方法的时间复杂度为O（LogN），这一点略逊于ArrayList和Hashtable，后两者添加操作的时间复杂度都为O(1)，这也是“有序”所付出的代价。

在查询数据时，SortedList会先通过二分查找法，找到key值所在object[]数组的序号，然后根据该序号去保存value的object[]数组中直接取值，代码如下:

public virtual object this[object key]{    get    {        //IndexOfKey使用Array.BinarySearch进行二分查找;        int index = this.IndexOfKey(key);        if (index >= 0)        {            return this.values[index];        }        return null;    }    ......}

由于二分查找的关系，可以看出SortedList通过object查询操作的时间复杂度为O（logN），这一点强于ArrayList的O（n），逊于Hashtable的O（1）。

SortedList也可以通过序号下标来获取值，这种方式的复杂度为O（1），获取单个元素的方式在下面提到。

SortedList获取单个元素的灵活性

SortedList获取集合中单个元素的方式非常灵活，ArrayList只能通过int型的下标序号来获取，Hashtable只能object型的Key值来匹配，而SortedList既可以用object型的key获取，也可以用int型的序号来获取。

public void SortedListTest(){    ArrayList arrayList = new ArrayList();    arrayList.Add("a");    Console.WriteLine(arrayList[0]);    //output: a        Hashtable hash = new Hashtable();    hash.Add("a", "aaa");    Console.WriteLine(hash["a"]);    //output: aaa    SortedList sortlist = new SortedList();    sortlist.Add("a", "aaa");    sortlist.Add("b", "bbb");    Console.WriteLine(sortlist["b"]);    Console.WriteLine(sortlist.GetByIndex(0));    //output: bbb    //        aaa    }

SortedList<TKey,TValue>是SortedList对应的泛型集合，除了免装箱拆箱优势和一个TryGetValue方法外，就没有什么太大差别。

结论

SortedList保证集合中数据的有序性，有两种方式来获取单个元素，较为灵活。

添加操作比ArrayList，Hashtable略慢；查找、删除操作比ArrayList快，比Hashtable慢。

当然，如果使用，则优先选择泛型集合SortedList<TKey,TValue>。

 

从类名就可以看出SortedDictionary<TKey,TValue>和上篇介绍的SortedList一样，都是有序集合，但从类内部的存储结构上看，两者有很大区别，SortedList内部用数组保存，只能算是有序线性表，而SortedDictionary<TKey,TValue>的内部结构是。

园子里，已将红黑树分析的很透彻。所以这里不讨论红黑树的结构原理，而讨论SortedDictionary和SortedList有什么差异？何时应该选择使用SortedDictionary？

SortedDictionary内部结构是红黑树，红黑树是平衡二叉树的一种，SortedList是有序线性表，内部结构是Array，运用了二分查找法提高效率。从两者查找、插入、删除操作的时间复杂度来看，都为O（LogN），分辨不出优劣，但内部结构的不同导致了实际操作中的性能差异。

SortedDictionary和SortedList性能比较--插入

由于SortedList用数组保存，每次进行插入操作时，首先用二分查找法找到相应的位置，得到位置以后，SortedList会把该位置以后的值依次往后移一个位置，空出当前位，再把值插入，这个过程中用到了Array.Copy方法，而调用该方法是比较损耗性能的，代码如下：

private void  Insert(int  index, TKey key, TValue value){    ......    if  (index < this._size)    {        Array.Copy(this.keys, index, this.keys, index + 1, this._size - index);        Array.Copy(this.values, index, this.values, index + 1, this._size - index);    }        ......}

SortedDictionary在添加操作时，只会根据红黑树的特性，旋转节点，保持平衡，并没有对Array.Copy的调用。

现在我们用数据测试一下：循环一个int型、容量为100000的随机数组，分别用SortedList和SortedDictionary添加。（代码中的CodeTimer类，来自。）

public void SortedAddInTest(){    Random random = new Random();    int array_count = 100000;    List
    
      intList = new List
     
      ();    for (int i = 0; i <= array_count; i++)    {        int ran = random.Next();        intList.Add(ran);    }    SortedList
      
        sortedlist_int = new SortedList
       
        ();    SortedDictionary
        
          dic_int = new SortedDictionary
         
          (); CodeTimer.Time("sortedList_Add_int", 1, () => { foreach (var item in intList) { if (sortedlist_int.ContainsKey(item) == false) sortedlist_int.Add(item, item); } }); CodeTimer.Time("sortedDictionary_Add_int", 1, () => { foreach (var item in intList) { if (dic_int.ContainsKey(item) == false) dic_int.Add(item, item); } });}
         
        
       
      
     
    

结果跟之前分析的一样，为：

sortedList_Add_int 

    Time Elapsed:    4,311ms 

    CPU Cycles:    8,249,183,130 

    Gen0:        0 

    Gen1:        0 

    Gen2:        0

sortedDictionary_Add_int 

    Time Elapsed:    217ms 

    CPU Cycles:    278,164,530 

    Gen0:        1 

    Gen1:        1 

    Gen2:        0 

由此可以看出：在大量添加操作的情况下，SortedDictionary性能优于SortedList。

SortedDictionary和SortedList性能比较--查询

两者的查询操作中，时间复杂度都为O（LogN），且源码中也没有额外的操作造成性能损失，那么他们在查询操作中性能如何？继续上面一个例子进行测试。

public void SortedAddInTest(){    ......    CodeTimer.Time("sortedList_Search_int", 1, () =>    {        foreach (var item in intList)        {            sortedlist_int.ContainsKey(item);        }    });    CodeTimer.Time("sortedDictionary_Search_int", 1, () =>    {        foreach (var item in intList)        {            dic_int.ContainsKey(item);        }    });}

结果为：

sortedList_Search 

    Time Elapsed:    602ms 

    CPU Cycles:    1,156,460,630 

    Gen0:        0 

    Gen1:        0 

    Gen2:        0

sortedDictionary_Search 

    Time Elapsed:    667ms 

    CPU Cycles:    1,256,685,950 

    Gen0:        0 

    Gen1:        0 

    Gen2:        0

可以得出：两者在循环10w次的情况下，仅仅相差几十毫秒，可以看出，两者的查询操作性能相差不大。

SortedDictionary和SortedList性能比较--删除

从添加操作例子可以看出，由于SortedList内部使用数组进行存储数据，而数组本身的局限性使得SortedList大部分的添加操作都要调用Array.Copy方法，从而导致了性能的损失，这种情况同样存在于删除操作中。

SortedList每次删除操作都会将删除位置后的值往前挪动一位，以填补删除位置的空白，这个过程刚好跟添加操作反过来，同样也需要调用Array.Copy方法，相关代码如下。

public void RemoveAt(int index){    ......    if (index < this._size)    {        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);        Array.Copy(this.values, index + 1, this.values, index, this._size - index);    }        ......}

情况跟添加操作一样，所以先在这里预测一下：在大量删除操作的情况下时，SortedDictionary的性能优于SortedList。

让我们继续上面的测试代码来验证这一点。

public void SortedDictionaryTest(){    //.......    CodeTimer.Time("sortedList_Delete_String", 1, () =>    {        foreach (var item in temp_List)        {            sortedlist.Remove(item);        }    });    CodeTimer.Time("sortedDictionary_Delete_String", 1, () =>    {        foreach (var item in temp_List)        {            dic.Remove(item);        }    });}

结果跟之前预测的一样，SortedDictionary的性能较好，如下：

sortedList_Delete

    Time Elapsed:    13,346ms 

    CPU Cycles:    25,040,378,250 

    Gen0:        0 

    Gen1:        0 

    Gen2:        0

sortedDictionary_Delete

    Time Elapsed:    731ms 

    CPU Cycles:    1,335,367,350 

    Gen0:        0 

    Gen1:        0 

    Gen2:        0

总结

SortedDictionary内部用红黑表存储数据，SortedList用数组存储数据，两者的查询效率差不多，但由于数组本身的限制，在大量添加删除操作的情况下，SortedDictionary的性能优于SortedList，而SortedList又存在二倍扩充的问题，在内存占用上也处于劣势。（这两者的添加删除操作因Array.Copy造成的性能差异也同样存在于泛型链表LinkedList<T>和线性表中，我之前里忘记分析这一块了，^_^）

此处我有了一个迷惑，既然SortedDictionary的性能全面优于SortedList，那SortedList存在的意义是什么？我找来找去只发现SortedList的一个优点就两种获取单个元素的方式--key和index，这点在上篇文章也有提到，难道SortedList的优点只有这个？