03_C#之集合

数组(Array)与集合(ArrayList)与List
单向链表（ListDictionary）与双向链表（LinkedList）
HashSet
HashTable(哈希表)与Dictionary
Queue、Queue
Stack、Stack
SortedList、SortedList与SortedDictionary
- SortedList
- SortedDictionary
HybridDictionary
BitArray

这个是对C#中的集合类发展做出简要概述、对比、使用、原理等剖析。
集合是一个数据结构，在不同的业务场景使用的数据结构也是完全不同的，但是历史发展史有进程的，C#中的集合类也是在不断完善的过程，所以从最小的业务场景来一步步的看看C#中对集合类的实现。
学习数组的时候会对其特点/原理、优点，缺点等几个方面进行学习，对引用场景进行了解。

数组(Array)与集合(ArrayList)与List

数组（Array）

数组可以说是最简单的数据结构了，数组有以下几个特点：

数组存储在连续的内存上。
数组的内容都是相同类型。如果类型为值类型，则将会有size个未装箱的该类型的值被创建。如果类型为引用类型，则将会有size个相应类型的引用被创建。
数组可以直接通过下标访问。

在C#中：

{
    int size = 2;
    // 声明并实例化数组:数组在实例化得时候必须给出大小。注意这里赋值的是大小，在这里赋值为2，随意数组的下标最大值为[1]。
    int[] a = new int[size];
    // 数组赋值:值与声明时候的类型必须一致，下标索引从0开始。
    a[0] = 1;
    // 数组获取：接收的参数类型必须与数组的一致,当没有赋值的默认为0。
    int x = a[1];
}

优点：
由于是在连续内存上存储的，所以它的索引速度非常快，访问一个元素的时间是恒定的也就是说与数组的元素数量无关，而且赋值与修改元素也很简单。
缺点：

由于是连续存储，所以在两个元素之间插入新的元素与删除元素就变得不方便。
声明一个新的数组时，必须指定其长度，这就会存在一个潜在的问题，那就是当我们声明的长度过长时，显然会浪费内存，当我们声明长度过短的时候，则面临这溢出的风险。
集合(ArrayList)
集合是为了弥补数组的缺点而推出的。位于System.Collections命名空间下。特点：
- 不必在声明ArrayList时指定它的长度，这是由于ArrayList对象的长度是按照其中存储的数据来动态增长与缩减的。
- ArrayList可以存储不同类型的元素。这是由于ArrayList会把它的元素都当做Object来处理。因而，加入不同类型的元素是允许的。

{
    ArrayList test3 = new ArrayList();
    //新增数据
    test3.Add("liu");
    test3.Add(25);
    //修改数据
    test3[1] = 26;
    //删除数据
    test3.RemoveAt(0);
}

优点：

不必在声明ArrayList时指定它的长度，这是由于ArrayList对象的长度是按照其中存储的数据来动态增长与缩减的。
ArrayList可以存储不同类型的元素。这是由于ArrayList会把它的元素都当做Object来处理。因而，加入不同类型的元素是允许的。

缺点：

ArrayList不是类型安全的。因为把不同的类型都当做Object来做处理，很有可能会在使用ArrayList时发生类型不匹配的情况。
ArrayList由于把所有类型都当做了Object，所以不可避免的当插入值类型时会发生装箱操作，在索引取值时会发生拆箱操作。
List

可以说为了解决ArrayList的缺点，而且在C#2.0的时候引入了泛型的概念，所以推出了List这种结合。特点：和ArrayList很相似，长度都可以灵活的改变，最大的不同在于在声明List集合时，我们同时需要为其声明List集合内数据的对象类型，这点又和Array很相似，其实List内部使用了Array来实现。

{
    // 这里使用IList接口来调用子类实现，为了满足依赖倒置原则
    IList<string> test4 = new List<string>();
    //新增数据 
    test4.Add("Fanyoy");
    test4.Add("Chenjd");
    //修改数据 
    test4[1] = "murongxiaopifu";
    //移除数据 
    test4.RemoveAt(0);
}

优点：

确保了类型安全。
取消了装箱和拆箱的操作。
它融合了Array可以快速访问的优点以及ArrayList长度可以灵活变化的优点。

缺点：
他是现在最长使用的集合类型，经过多次的改进，已经很完备了，他弥补了Array与ArrayList的缺点，同时拥有他们的有点。

探究原理

自己实现一个MyList来看一下内部原理：
这里主要是扩容的原理，容量不够会增加为原来容量的二倍。

/// <summary>
/// 首先这是一个泛型类，因为自己实现，所以不继承Ilist接口
/// </summary>
/// <typeparam name="T"></typeparam>
class MyList<T>
{
    public T this[int index] {
        get
        {
            if ((uint)index >= (uint)Count)
            {
                throw new Exception("数组越界异常");
            }
            return Items[index];
        }
        set
        {
            if ((uint)index >= (uint)Count)
            {
                throw new Exception("数组越界异常");
            }
            Items[index] = value;
        }
    }
    // MyList容量
    private int Capacity { get; set; }
    // MyList中元素个数
    private int Count { get; set; }
    // 声明数组
    private T[] Items { get; set; }
    // 默认容量为4
    public MyList(int capacity = 4)
    {
        if (capacity < 0)
        {
            throw new Exception("数组越界");
        }
        else
        {
            this.Capacity = capacity;
            this.Items = new T[capacity];
        }
    }
    //元素添加
    public void add(T x)
    {
        //执行扩容方法
        Resize();
        this.Items[this.Count] = x;
        this.Count++;
    }
    //根据当前索引移除元素
    public void RemoveAt(int index)
    {
        if ((uint)index >= (uint)Count)
        {
            throw new Exception("数组越界异常");
        }
        Count--;
        if (index < Count)
        {
            Array.Copy(Items, index + 1, Items, index, Count - index);
        }
        Items[Count] = default(T);
    }
    // 私有的扩容方法
    private void Resize()
    {
        if (this.Capacity <= this.Count)
        {
            // 容量变为原来得二倍
            this.Capacity = this.Capacity * 2;
            if (this.Count>this.Capacity)
            {
                this.Count = this.Capacity;
            }
            T[] destinationArray = new T[this.Capacity];
            Array.Copy(this.Items, destinationArray, this.Count);
            this.Items = destinationArray;
        }
    }
}

单向链表（ListDictionary）与双向链表（LinkedList）

单向链表（ListDictionary）

因为Array这种数据类型对查找与修改比较友好，但是对删除与增加还是不太理想的。因为array的扩容原理，所以对内存有浪费，但是链表使用的是指针来连接，所以不会浪费内存。其实ListDictionary不是本质的单向链表，他是用单链表实现的字典。特点：

对内存利用率高。

{
    // 创建
    ListDictionary listDictionary = new ListDictionary();
    // 添加元素
    listDictionary.Add("1", "2");
    listDictionary.Add("2", "3");
    // 移除元素
    listDictionary.Remove("1");
}

优点：对内存空间利用高。
缺点：每次添加数据时都要遍历链表，数据量大时效率较低，数据量较大且插入频繁的情况下，不宜选用。且Key与value都是object，类型是不安全的。
自制单向链表

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _11_Collections
{
    public class ListNode<T>
     {
         public ListNode(T NewValue)
         {
             Value = NewValue;
         }
         //前一个
         public ListNode<T> Previous;
         //后一个
         public ListNode<T> Next;
         //值
         public T Value;
     }
    class SinglyLinkedList<T>
    {
        public SinglyLinkedList()//构造函数
        {
            //初始化
            ListCountValue = 0;
            Head = null;
            Tail = null;
        }
        private ListNode<T> Head;//头指针
        private ListNode<T> Tail;//尾指针
        private ListNode<T> Current;//当前指针
        private int ListCountValue;//链表数据的个数
        //向尾部添加数据方法
        public void Append(T DataValue)
        {
            ListNode<T> NewNode = new ListNode<T>(DataValue);
            if (IsNull())//如果头指针为空
            {
                Head = NewNode;
                Tail = NewNode;
            }
            else
            {
                Tail.Next = NewNode;
                NewNode.Previous = Tail;
                Tail = NewNode;
            }
            Current = NewNode;
            ListCountValue += 1;//链表个数加 1
        }
        public void Delete()
        {
            if (!IsNull())//若为空链表
            {
                if (!IsBof())//若删除头
                {
                    Head = Current.Next;
                    Current = Head;
                    ListCountValue -= 1;
                    return;
                }
                if (!IsEof())//若删除尾
                {
                    Tail = Current.Previous;
                    Current = Tail;
                    ListCountValue -= 1;
                    return;
                }
                Current.Previous.Next = Current.Next;//若删除中间数据
                Current = Current.Previous;
                ListCountValue -= 1;
                return;
            }
        }
        //向后移动一个数据的方法
        public void MoveNext()
        {
            if (!IsEof()) Current = Current.Next;
        }
        //向前移动一个数据的方法
        public void MovePrevious()
        {
            if (!IsBof()) Current = Current.Previous;
        }
        //移动到第一个数据方法
        public void MoveFrist()
        {
            Current = Head;
        }
        //移动到最后一个数据方法
        public void MoveLast()
        {
            Current = Tail;
        }
        //判断是否为空链表方法
        public bool IsNull()
        {
            if (ListCountValue == 0)
                return true;
            return false;
        }
        //判断是否为到达尾部方法
        public bool IsEof()
        {
            if (Current == Tail)
                return true;
            return false;
        }
        //判断是否为到达头部方法
        public bool IsBof()
        {
            if (Current == Head)
                return true;
            return false;
        }
        //取得当前结点的值方法
        public T GetCurrentValue()
        {
            return Current.Value;
        }
        //取得链表的数据个数方法
        public int ListCount
        {
            get { return ListCountValue; }
        }
        //清空链表方法
        public void Clear()
        {
            MoveFrist();
            while (!IsNull())
            {
                Delete();//若不为空链表，从尾部删除
            }
        }
        //在当前位置前输入数据方法
        public void Insert(T DataValue)
        {
            ListNode<T> NewNode = new ListNode<T>(DataValue);
            if (IsNull())
            {
                Append(DataValue);//为空表，则添加
                return;
            }
            if (IsBof())
            {
                //为头部插入
                NewNode.Next = Head;
                Head.Previous = NewNode;
                Head = NewNode;
                Current = Head;
                ListCountValue += 1;
                return;
            }
            //中间插入
            NewNode.Next = Current;
            NewNode.Previous = Current.Previous;
            Current.Previous.Next = NewNode;
            Current = NewNode;
            ListCountValue += 1;
        }
    }
}

双向链表（LinkedList）

为了解决单向链表的缺点，用LinkedList来代替。

1
2
3
4
LinkedList<int> vs = new LinkedList<int>();
vs.AddFirst(1);
vs.AddFirst(2);
vs.AddLast(3);

优点：

向链表中插入或删除节点无需调整结构的容量。因为本身不是连续存储而是靠各对象的指针所决定，所以添加元素和删除元素都要比数组要有优势。
链表适合在需要有序的排序的情境下增加新的元素，这里还拿数组做对比，例如要在数组中间某个位置增加新的元素，则可能需要移动移动很多元素，而对于链表而言可能只是若干元素的指向发生变化而已。
有优点就有缺点，由于其在内存空间中不一定是连续排列，所以访问时候无法利用下标，而是必须从头结点开始，逐次遍历下一个节点直到寻找到目标。所以当需要快速访问对象时，数组无疑更有优势。

总结与对比
数组的优点：
随机访问性强（通过下标进行快速定位）
查找速度快

数组的缺点：

插入和删除效率低（插入和删除需要移动数据）
可能浪费内存（因为是连续的，所以每次申请数组之前必须规定数组的大小，如果大小不合理，则可能会浪费内存）
内存空间要求高，必须有足够的连续内存空间。
数组大小固定，不能动态拓展

链表的优点：

插入删除速度快（因为有next指针指向其下一个节点，通过改变指针的指向可以方便的增加删除元素）
内存利用率高，不会浪费内存（可以使用内存中细小的不连续空间（大于node节点的大小），并且在需要空间的时候才创建空间）
大小没有固定，拓展很灵活。

链表的缺点：

不能随机查找，必须从第一个开始遍历，查找效率低

双向链表与单向链表的对比：

删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的，指针的总的移动操作都会有2*i次。而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为i次。
查找时也一样，我们可以借用二分法的思路，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。
从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节）的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这时一种工程总体上的衡量。
HashSet

hashset是一种以散列表形式的集合，这个集合类包含不重复项的无序列表。HashSet类提供的方法可以创建合集和交集，泛型类的集合，类型安全。特点：因为这个集合基于散列值，插入元素的操作非常快，不需要像List类那样重排集合。 HashSet与Dictionary的实现几乎一模一样，只不过没有key，所以存储的时候是用value的HashCode值进行判断。

1
2
3
4
5
6
7
{
    // hashset维护的是散列表，所以没有索引的。不能按照索引查找。
    HashSet<int> vs = new HashSet<int>();
    vs.Add(1);
    // 删除只能匹配删除，不能按照索引删除
    vs.Remove(1);
}

优点：这个集合基于散列值，插入元素的操作非常快，不需要像List类那样重排集合。
缺点：查找不便。需要比较查找。
本质上可以理解为一个功能集合，主要是对集合内部进行改性能的运算操作，在存储方面并不常用。

HashTable(哈希表)与Dictionary

HashTable(哈希表)

HashTable是一种根据key查找非常快的键值数据结构，不能有重复key，而且由于其特点，其长度总是一个素数，所以扩容后容量会比2倍大一点点，加载因子为0.72f。当要大量使用key来查找value的时候，HashTable无疑是最有选择，HashTable与ArrayList一样，是非泛型的，value存进去是object,存取会发生装箱、拆箱，所以出现了Dictionary。

1
2
3
4
5
6
{
    // hashtable是非泛型的，所以类型不安全。
    Hashtable hashtable = new Hashtable();
    hashtable.Add("a", "asdf");
    hashtable.Add("b", 1);
}

优点：
可以进行大量的key value操作，速度很快。
缺点：
内部为object类型，所以会大量的拆箱装箱操作。

Dictionary

他是为了解决HashTable的类型安全问题而提出的全新的集合类型。字典是类型安全的，也就是说当创建字典时，必须声明key和item的类型，这是第一条字典与哈希表的区别。在创建字典时，我们可以传入一个容量值，但实际使用的容量并非该值。而是使用“不小于该值的最小质数来作为它使用的实际容量，最小是3。”（老赵），当有了实际容量之后，并非直接实现索引，而是通过创建额外的2个数组来实现间接的索引，即int[] buckets和Entry[] entries两个数组（即buckets中保存的其实是entries数组的下标），这里就是第二条字典与哈希表的区别，还记得哈希冲突吗？对，第二个区别就是处理哈希冲突的策略是不同的！字典会采用额外的数据结构来处理哈希冲突，这就是刚才提到的数组之一buckets桶了，buckets的长度就是字典的真实长度，因为buckets就是字典每个位置的映射，然后buckets中的每个元素都是一个链表，用来存储相同哈希的元素，然后再分配存储空间。

1
2
3
4
{
    Dictionary<int, int> keyValuePairs = new Dictionary<int, int>();
    keyValuePairs.Add(1, 2);
}

优点：
解决了HashTable的类型安全问题，并对HashTable进行了优化。
缺点：
当数据量小的时候，尽量不要用Dictionary，因为内部实现的关系，消耗空间很大，当数据量大的时候，可以考虑用空间换时间。

内部原理解析

博客： https://blog.csdn.net/fdyshlk/article/details/76407397
C++中STL的Map跟C#的Dictionary的使用几乎是一样的，Map使用的是红黑树来实现，所以想当然的以为C#的Dictionary也是红黑树，老兄，那可真就大错特错了。
我也是有次没事去看下Dictionary的实现才发现压根就没有树的影子，原来使用散列表的方式来实现。下面我们一起来看下Dictionary的内部实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Dictionary<TKey,TValue>: IDictionary<TKey,TValue>, IDictionary, IReadOnlyDictionary<TKey, TValue>, ISerializable, IDeserializationCallback  {
private struct Entry {
        public int hashCode;    // Lower 31 bits of hash code, -1 if unused
        public int next;        // Index of next entry, -1 if last
        public TKey key;           // Key of entry
        public TValue value;         // Value of entry
    }

    private int[] buckets;
    private Entry[] entries;
    private int count;
    private int version;
    private int freeList;
    private int freeCount;
    private IEqualityComparer<TKey> comparer;
    private KeyCollection keys;
    private ValueCollection values;
    private Object _syncRoot;

可以看到声明了两个数组，其中buckets记录的为指向entries数组的索引，entries记录的为dictionary的value值部分，count为存储的元素的数量，version为当前的版本号，freeList为空闲的列表，freeCount为空闲的列表数量。
我认为dictionary最重要的就是Insert函数，理解了Insert函数就说明你真正理解了dictionary的实现方式了，Add方法最终调用的也是Insert函数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
private void Insert(TKey key, TValue value, bool add) {

            if( key == null ) {
                ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
            }
            if (buckets == null) Initialize(0);//第一次初始化
           int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;//得到key的hashcode进行运算并得到在buckets的索引值

            int targetBucket = hashCode % buckets.Length;

#if FEATURE_RANDOMIZED_STRING_HASHING
            int collisionCount = 0;
#endif
            for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {//判断是否已经存在，如果存在，那么进行值得替换

                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    if (add) { 
                        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                    }
                    entries[i].value = value;
                    version++;
                    return;
                } 

#if FEATURE_RANDOMIZED_STRING_HASHING
                collisionCount++;
#endif
            }
            int index;
            if (freeCount > 0) {//判断entries是否有释放的空闲空间，如果有，则进行利用

                index = freeList;
                freeList = entries[index].next;
                freeCount--;
            }
            else {
                if (count == entries.Length) //数组空间不够，则重新分配两倍的内存进行存储
                {
                    Resize();
                    targetBucket = hashCode % buckets.Length;
                }
                index = count;
                count++;
            }

            entries[index].hashCode = hashCode;//具体的值存储
            entries[index].next = buckets[targetBucket];
            entries[index].key = key;
            entries[index].value = value;
            buckets[targetBucket] = index;
            version++;

#if FEATURE_RANDOMIZED_STRING_HASHING

#if FEATURE_CORECLR
            // In case we hit the collision threshold we'll need to switch to the comparer which is using randomized string hashing
            // in this case will be EqualityComparer<string>.Default.
            // Note, randomized string hashing is turned on by default on coreclr so EqualityComparer<string>.Default will 
            // be using randomized string hashing

            if (collisionCount > HashHelpers.HashCollisionThreshold && comparer == NonRandomizedStringEqualityComparer.Default) 
            {
                comparer = (IEqualityComparer<TKey>) EqualityComparer<string>.Default;
                Resize(entries.Length, true);
            }
#else
            if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
            {
                comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
                Resize(entries.Length, true);
            }
#endif // FEATURE_CORECLR

#endif

        }

这段代码的难点就在于buckets数组和entries数组的映射，如果这理解了，代码自然就清晰了。
03_C#之集合 - 图1
在add第一份数据V1的时候，假如hashcode取余的索引数据为0，则把V1放入entries的第一个数据中，buckets[0]存储的数据为V1在entries的索引，所以buckets[0]为0，假设add的第二份数据V2的hashcode值取模后也为0，那么表示这两份数据的key值发生了碰撞，则判断buckets[0]指向的entries链的key值是否与当前插入V2对应的key值相等，如果相等则用V2替换原有值，如果不等，则V2插入到entries的空闲列表中（因为remove，中间空出的内存块），如果不存在空闲列表则直接插入到末尾，本例因为刚添加，所以直接添加到entries[1]中，然后把entries[1]中的hashcode值赋为V2对应key的hashcode值，next指向0，对应buckets[0]也改成指向entries[1]，插入V3与插入V2同理。多添加几个value值时，有可能如下图所示：
03_C#之集合 - 图2
还有个点时如同List一样，Dictionary在数组不够用的情况下会分配2倍的新内存来进行存储，与List不同的是capacity的默认值为3，而且dictionary包含了buckets和entries两个数组，entries是通过Array.Copy直接拷贝到新地址，但是buckets的计算方式是haahcode对长度取余，所以在长度变化后，不能直接通过内存拷贝的方式，而是必须全部再重新计算一遍。在Dictionary的构造函数中可以直接对其进行设置，所以capacity的值如果能设置的合理，那么可以减少内存申请、拷贝的次数，效率也会提高很多。

Queue、Queue

这两个本质上就是一个数据结构，区别就是泛型的区别，类型安全的区别，所以只了解一个就可以了。在Queue这种数据结构中，最先插入在元素将是最先被删除；反之最后插入的元素将最后被删除，因此队列又称为“先进先出”（FIFO—first in first out）的线性表。通过使用Enqueue和Dequeue这两个方法来实现对 Queue 的存取。特点：

先进先出的情景。
默认情况下，Queue的初始容量为32，增长因子为2.0。
当使用Enqueue时，会判断队列的长度是否足够，若不足，则依据增长因子来增加容量，例如当为初始的2.0时，则队列容量增长2倍。

1
2
3
4
{
    Queue queue = new Queue();
    queue.Enqueue("asd");
}

Stack、Stack

与Queue相对，当需要使用后进先出顺序（LIFO）的数据结构时，我们就需要用到Stack了。特点：

后进先出的情景。
默认容量为10。
使用pop和push来操作。

1
2
3
4
{
    Stack stack = new Stack();
    stack.Push("asdfa");
}

SortedList、SortedList与SortedDictionary

SortedList

SortedList集合中的数据是有序的。可以通过key来匹配数据，也可以通过int下标来获取数据。特点：添加操作比ArrayList，Hashtable略慢；查找、删除操作比ArrayList快，比Hashtable慢。所以用Hashtable更好。

1
2
3
4
{
    SortedList sortedList = new SortedList();
    sortedList.Add("a", "1");
}

SortedDictionary

SortedDictionary相比于SortedList其性能优化了，SortedList其内部维护的是数组而SortedDictionary内部维护的是红黑树(平衡二叉树)的一种，因此其占用的内存，性能都好于SortedDictionary。唯一差在不能用下标取值。

1
2
3
4
{
    SortedDictionary<int, int> keyValuePairs = new SortedDictionary<int, int>();
    keyValuePairs.Add(1, 2);
}

HybridDictionary

HybridDictionary的类，充分利用了Hashtable查询效率高和ListDictionary占用内存空间少的优点，内置了Hashtable和ListDictionary两个容器，添加数据时内部逻辑如下：当数据量小于8时，Hashtable为null，用ListDictionary保存数据。当数据量大于8时，实例化Hashtable，数据转移到Hashtable中，然后将ListDictionary置为null。

1
2
3
4
{
    HybridDictionary hybridDictionary = new HybridDictionary();
    hybridDictionary.Add("1", "a");
}

BitArray

BitArray这个东东是用于二进制运算，”或”、”非”、”与”、”异或非”等这种操作，只能存true或false；