C#常用容器源码浅析

C#常用容器源码浅析

• [x] 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 其他没啥好说的了，下一个--------
  

• [x] 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)
  

• [x] 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.细节就是扩容的数据大小不会在缩回来了
  

• [x] 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的开销，根据自己的使用场景来确定是用顺序列表（增删开销大，查询快）还是链表（增删开销小，查询快）。
  

• [x] Dictionary

  • 我另一篇帖子深入讲了，就不再写一遍了，快速定位就ctrl+F搜：字典的实现原理

  • C#知识树整理——C#基础

• [ ] ...如果还有想了解的容器欢迎评论留言

C#常用容器源码浅析

原文：https://www.cnblogs.com/moran-amos/p/14375570.html