.Net集合类的研究-有序集合（一）-SortedList、SortedList<TKey,TValue>
无论是常用的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: aaaSortedList 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>。
补充：Web开发 , ASP.Net ,
