C#常用容器源码浅析 agile Posted on Jun 18 2023 c# > 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [www.cnblogs.com](https://www.cnblogs.com/moran-amos/p/14375570.html) C# 常用容器源码浅析 ----------- * List ``` private static readonly T[] _emptyArray = new T[0]; //默认数组 private const int _defaultCapacity = 4;//如果没给出指定长度默认的列表长度，但是我不得不吐槽一点，定义出来没用这是最骚的，过会你们就看到了 private T[] _items;//存储列表元素的数组 private int _size;//当前列表元素个数 private int _version;//版本，防止迭代时再对容器操作 //------------------------------创建-------------------------------------- public List() { this._items = List<T>._emptyArray; } public List(int capacity) { if (capacity < 0) //抛异常 if (capacity == 0) this._items = List<T>._emptyArray; else this._items = new T[capacity]; } //声明一个默认大小，没啥好说的 //------------------------------Add-------------------------------------- public void Add(T item) { if (this._size == this._items.Length) this.EnsureCapacity(this._size + 1);//如果列表的元素大小和容器大小一致了，就要扩容自己的内部容器 this._items[this._size++] = item;//正常的添加 ++this._version;//更新版本 } private void EnsureCapacity(int min) { if (this._items.Length >= min) return; int num = this._items.Length == 0 ? 4 : this._items.Length * 2;//重点在这里，如果没指定长度，创建的时候默认为0，当第一次添加元素的时候，指定的大小为4，对，就上面那个_defaultCapacity的值，最骚的就是他写了_defaultCapacity然后用的时候自己写了个4，666。不然就是扩容长度*2,每次进行2倍扩容 if ((uint) num > 2146435071U)//为啥这函数叫安全扩容就是因为这里做了个安全性校验，防止*2以后的容量溢出uint范围 num = 2146435071; if (num < min) num = min; this.Capacity = num;//设置新的大小 } public int Capacity { get { return this._items.Length; } set { if (value < this._size) //如果设置的值比已有的元素容量还小肯定是要抛异常的拉 if (value == this._items.Length) return; if (value > 0) { T[] objArray = new T[value];//新创建一个数组 if (this._size > 0) Array.Copy((Array) this._items, 0, (Array) objArray, 0, this._size);//吧当前容器的内容全部搬移到新的数组里，就是逐个拷贝，所以这里的开销需要自己考量，比如你初始数组是0，一开始就插入100w个元素，其中扩容了n次，实际上你的开销是远远大于100w次的，这就是为啥上面给你个指定容量大小的new，指定以后就是100w次，没有搬移的开销 this._items = objArray; } else this._items = List<T>._emptyArray; } } //------------------------------Remove-------------------------------------- public bool Remove(T item) { int index = this.IndexOf(item);//先找到要移除的item下标，所以如果要移除指定元素且你知道具体位置的话，直接调用RemoveAt会更高效 if (index < 0) return false; this.RemoveAt(index);//移除 return true; } public void RemoveAt(int index) { if ((uint) index >= (uint) this._size) ThrowHelper.ThrowArgumentOutOfRangeException(); --this._size; if (index < this._size) Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);//吧当前移除的下标+1后面的值全部搬运到index的位置 this._items[this._size] = default (T);//然后把最后一个值清空咯 ++this._version; } //所以其实remove的时候不会根据元素个数把之前扩容的空间再缩回来，如果你先加了100w个元素，再删99w个元素，实际上list的占用容量空间还是100w+的容量空间，那能怎么办呢，别急，下面那个方法可以让你快速瘦身 public void TrimExcess() { if (this._size >= (int) ((double) this._items.Length * 0.9))//如果你的当前的元素个数大于容器空间的百分90那还是别缩了 return; this.Capacity = this._size;//缩 } //------------------------------迭代-------------------------------------- public bool MoveNext() { List<T> list = this.list; if (this.version != list._version || (uint) this.index >= (uint) list._size) return this.MoveNextRare(); this.current = list._items[this.index]; ++this.index; return true; } private bool MoveNextRare() { if (this.version != this.list._version) //版本就是这里用的,防止有人在迭代的时候再去把元素增删这种骚操作，一抓到就报异常 this.index = this.list._size + 1; this.current = default (T); return false; } //总结：list底层就是用array实现的一个可变长数组，存储形式是顺序存储，so，他具有顺序存储的数据结构的优点和缺点，查询快，增删开销大。 //----------END 其他没啥好说的了，下一个-------- ``` * Stack ``` private object[] _array; //内部容器 private int _size;//元素个数 private int _version; [NonSerialized] private object _syncRoot; private const int _defaultCapacity = 10; //------------------------------new-------------------------------------- public Stack() { this._array = new object[10];//stack默认大小是10 this._size = 0; this._version = 0; } public Stack(int initialCapacity) { if (initialCapacity < 0) //抛异常 if (initialCapacity < 10) initialCapacity = 10; this._array = new object[initialCapacity]; this._size = 0; this._version = 0; } //------------------------------Push-------------------------------------- public virtual void Push(object obj) { if (this._size == this._array.Length) { object[] objArray = new object[2 * this._array.Length]; //直接两倍扩容，和list一样，为啥不安全扩容，嗯，好问题，我也不知道。 Array.Copy((Array) this._array, 0, (Array) objArray, 0, this._size);//其他都和List一样 this._array = objArray; } this._array[this._size++] = obj; ++this._version; } //------------------------------Pop Peek-------------------------------------- //和list一样，也没缩减 public virtual object Pop() { if (this._size == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack")); ++this._version; object obj = this._array[--this._size]; this._array[this._size] = (object) null; return obj; } public virtual object Peek() { if (this._size == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyStack")); return this._array[this._size - 1]; } //总结C#的Stack底层就是用数组模拟的栈，细节就是扩容的数据大小不会在缩回来了(所以我个人认为还是链表容器适合作stack，不会有开辟后搬移的开销，至于查嘛，stack本身就不允许随机访问，所以简直不要太完美，不懂为啥用arr) ``` * Queue ``` private object[] _array; //容器对象数组 private int _head;//头指针 private int _tail;//尾指针,指向下一个可用的空节点 private int _size;//实际大小 private int _growFactor;//增长因子，就每次扩容多少，默认2倍扩容 private int _version;//版本 //------------------------------new-------------------------------------- public Queue(): this(32, 2f) { }//默认扩容2，一开始大小32 public Queue(int capacity) : this(capacity, 2f) { } public Queue(int capacity, float growFactor) { if (capacity < 0) //容量是负数，抛出异常 if ((double) growFactor < 1.0 || (double) growFactor > 10.0) //增长因子高于指定范围，抛出异常 this._array = new object[capacity]; this._head = 0; this._tail = 0; this._size = 0; this._growFactor = (int) ((double) growFactor * 100.0); } //------------------------------入队-------------------------------------- public virtual void Enqueue(object obj)//尾插 { if (this._size == this._array.Length) {//扩容 int capacity = (int) ((long) this._array.Length * (long) this._growFactor / 100L);//扩容大小 if (capacity < this._array.Length + 4) capacity = this._array.Length + 4;//扩容得太小还不行，至少要扩4个 this.SetCapacity(capacity); } this._array[this._tail] = obj; this._tail = (this._tail + 1) % this._array.Length;//这里有个细节，他的容器是环状实现，尾是往后插的，当头是往尾巴部分回收的，所以数组前段的空间是可以被重复利用的，所以这里用了取余来去拿复用的回收后的空节点 ++this._size; ++this._version; } private void SetCapacity(int capacity) { object[] objArray = new object[capacity]; if (this._size > 0) { if (this._head < this._tail)//当头<尾时就是正常的拷贝，将当前内容从当前头的位置开始全部拷贝到新数组 { Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._size); } else//当头>=尾,先吧头到容器屁股的那段拷完再去吧0-尾巴的那段都拷了 { Array.Copy((Array) this._array, this._head, (Array) objArray, 0, this._array.Length - this._head); Array.Copy((Array) this._array, 0, (Array) objArray, this._array.Length - this._head, this._tail); } } this._array = objArray; this._head = 0; this._tail = this._size == capacity ? 0 : this._size; ++this._version; } //------------------------------Dequeue Peek-------------------------------------- public virtual object Dequeue() { if (this.Count == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); object obj = this._array[this._head]; this._array[this._head] = (object) null; this._head = (this._head + 1) % this._array.Length;//环状容器，所以要跟着尾链表一样动态取余 --this._size; ++this._version; return obj; } public virtual object Peek() { if (this.Count == 0) throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EmptyQueue")); return this._array[this._head]; } //总结C#的Queue底层就是用数组模拟的队列，两个细节 //1.是环状容器实现，保证空间复用 //2.细节就是扩容的数据大小不会在缩回来了 ``` * LinkedList ``` internal LinkedListNode<T> head;//头节点 internal int count;//容量 internal int version;//版本 //------------------------------new-------------------------------------- public LinkedList()//是的没错，啥都不干 { } //------------------------------插入-------------------------------------- public void AddLast(T value) { LinkedListNode<T> newNode = new LinkedListNode<T>(this, value);//封装成一个节点 if (this.head == null) this.InternalInsertNodeToEmptyList(newNode);//插入第一个 else this.InternalInsertNodeBefore(this.head, newNode);//头插法 node.list = this;//细节吧自己记下来了 } private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode) { newNode.next = newNode;//指向自己 newNode.prev = newNode;//指向自己 this.head = newNode;//指向第一个节点 ++this.version; ++this.count; } private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode) { //头插法基本操作 newNode.next = node; newNode.prev = node.prev; node.prev.next = newNode; node.prev = newNode; ++this.version; ++this.count; } /* 原理类似不列举了，都是操作列表移动前后指针齐活，开销就是new这个节点的开销 AddAfter AddBefore AddFirst */ //------------------------------Remove-------------------------------------- public bool Remove(T value) { LinkedListNode<T> node = this.Find(value);//这个要先找到是哪个节点，find本身就是一个链表结构里很大的开销，所以建议少用这种方式而是直接指定，要指定不了又要频繁查询，顺序结构香的一批啊 if (node == null) return false; this.InternalRemoveNode(node); return true; } public void Remove(LinkedListNode<T> node) { this.ValidateNode(node);//检查节点可用性 this.InternalRemoveNode(node);//remove } internal void InternalRemoveNode(LinkedListNode<T> node) { if (node.next == node) { this.head = (LinkedListNode<T>) null;//是最后一个，那直接置空 } else { //前的后等于我的后 //后的前等于我的前 node.next.prev = node.prev; node.prev.next = node.next; if (this.head == node)//如果是头节点再改下头指针 this.head = node.next; } node.Invalidate();//这个内部就是置空,没做缓存，所以优化的话可以考虑做个空节点回收缓存池 --this.count; ++this.version; } //node的Invalidate() internal void Invalidate() { this.list = (LinkedList<T>) null; this.next = (LinkedListNode<T>) null; this.prev = (LinkedListNode<T>) null; } //--------------------------Find-------------------------- public LinkedListNode<T> Find(T value) { LinkedListNode<T> linkedListNode = this.head; EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default; if (linkedListNode != null) { if ((object) value != null) { while (!equalityComparer.Equals(linkedListNode.item, value)) { linkedListNode = linkedListNode.next;//从头结点开始往后遍历 if (linkedListNode == this.head)//没找到（还记得这是个环状链表吗，一开始head的prev和next都是指向自己，所以最后还会指到自己） goto label_8; } return linkedListNode; } while ((object) linkedListNode.item != null) { linkedListNode = linkedListNode.next; if (linkedListNode == this.head) goto label_8; } return linkedListNode; } label_8: return (LinkedListNode<T>) null; } //总结：linked是个双向链表，所以基本可以应付大部分需求，但是如果从优化角度的话可以考虑下将linked的释放重写下，变成缓存的，这样还就可以省去一部分new的开销，根据自己的使用场景来确定是用顺序列表（增删开销大，查询快）还是链表（增删开销小，查询快）。 ``` * Dictionary * 我另一篇帖子深入讲了，就不再写一遍了，快速定位就 ctrl+F 搜：字典的实现原理 * [C# 知识树整理——C# 基础](https://www.cnblogs.com/moran-amos/p/14366344.html) * ... 如果还有想了解的容器欢迎评论留言 __EOF__ 语言 数据结构与算法知识树整理——算法篇——排序