.net源码分析 – List<T>

通过分析源码可以更好理解List<T>的工作方式,帮助我们写出更稳定的代码。

List<T>源码地址: https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/List.cs

接口

List<T>实现的接口:IList<T>, IList, IReadOnlyList<T>

其实.net framework经过多代发展,List的接口确实是有点多了,添加新功能时为了兼容老功能,一些旧的接口又不能丢掉,所以看上去有点复杂。先把这些接口捋一下:

IEnumerator是枚举器接口,拥有枚举元素的功能,成员有Current, MoveNext, Reset,这三个函数可以使集合支持遍历。

IEnumerable是支持枚举接口,实现这接口表示支持遍历,成员就是上面的IEnumerator。

ICollection是集合接口,支持着集合的Count属性和CopyTo操作,另外还有同步的属性IsSynchronized(判断是否线程安全)和SyncRoot(lock的对象)。

IList是集合的操作接口,支持索引器,Add, Remove, Insert, Contains等操作。

泛型部分基本是上面这些接口的泛型实现,不过IList<T>的一些操作放到ICollection<T>里了,可能微软也觉得对于集合的一些操作放到ICollection更合理吧。

IReadOnlyCollection<T>是.net 4.5加进来的,可以认为是IList<T>的只读版。

变量

 1 private const int _defaultCapacity = 4;
 2 
 3 private T[] _items;
 4 
 5 private int _size;
 6 
 7 private int _version;
 8 
 9 private Object _syncRoot;
10 
11 static readonly T[] _emptyArray = new T[0];

_defaultCapacity意思是new List<T>时默认大小是4。

_items就是存List<T>元素的数组了,List<T>也是基于数组实现的。

_size指元素个数。

_version看字面意思是版本,具体用处下面看,与遍历集合时经常碰到的集合被修改异常有关。

_syncRoot上面有说到,内置的用于lock的对象,如果在多线程时只是操作这个集合就可以lock这个来保证线程安全,当然一般来说这个是内部用的,虽然对List<T>本身来说没什么用,这个不取的话是不会把对象new出来的,对于锁我们更常用的是在外面new一个readonly的object。

emptyArray这是个静态只读的空数组,所有没有元素的List<T>都是用这个,所以两个List<int>的_items其实是一样的,都是这个_emptyArray。

构造函数

有三个构造函数

1 public List()
2 {
3     _items = _emptyArray;
4 }

最常用的,_items直接指向静态空数组。

 1 public List(int capacity)
 2 {
 3     if (capacity < 0) throw new ArgumentOutOfRangeException(nameof(capacity), capacity, SR.ArgumentOutOfRange_NeedNonNegNum);
 4     Contract.EndContractBlock();
 5 
 6     if (capacity == 0)
 7         _items = _emptyArray;
 8     else
 9         _items = new T[capacity];
10 }

可以通过capacity指定大小

 1 public List(IEnumerable<T> collection)
 2 {
 3     if (collection == null)
 4         throw new ArgumentNullException(nameof(collection));
 5     Contract.EndContractBlock();
 6 
 7     ICollection<T> c = collection as ICollection<T>;
 8     if (c != null)
 9     {
10         int count = c.Count;
11         if (count == 0)
12         {
13             _items = _emptyArray;
14         }
15         else
16         {
17             _items = new T[count];
18             c.CopyTo(_items, 0);
19             _size = count;
20         }
21     }
22     else
23     {
24         _size = 0;
25         _items = _emptyArray;
26         // This enumerable could be empty.  Let Add allocate a new array, if needed.
27         // Note it will also go to _defaultCapacity first, not 1, then 2, etc.
28 
29         using (IEnumerator<T> en = collection.GetEnumerator())
30         {
31             while (en.MoveNext())
32             {
33                 Add(en.Current);
34             }
35         }
36     }
37 }

初始添加一个集合, 先看是否是ICollection,看上面知道这个接口有Copy的功能,copy到_items里。如果不是ICollection,不过由于是IEnumerable,所以可以遍历,一个一个加到_items里。

属性

Count 返回的是_size,这个是元素的实际个数,不是数组大小。

IsSynchronized是false,表示并非用SyncRoot 来实现同步。List<T>不是线程安全,需要我们自己用锁搞定,

IsReadOnly也是false, 那为什么要继承IReadOnlyList<T>呢,是为了提供一个转换成只读List的机会,比如有的方法不希望传进来的List可以修改,就可以把参数设成IReadOnlyList。

 1 Object System.Collections.ICollection.SyncRoot
 2 {
 3     get
 4     {
 5         if (_syncRoot == null)
 6         {
 7             System.Threading.Interlocked.CompareExchange<Object>(ref _syncRoot, new Object(), null);
 8         }
 9         return _syncRoot;
10     }
11 }

SyncRoot通过原子操作得到一个对象,对于List<T>来说并没有用,对于某些集合比较有用,比如SyncHashtable,就是通过syncRoot来实现线程安全。

比较重要的Capacity:

 1 public int Capacity
 2 {
 3     get
 4     {
 5         Contract.Ensures(Contract.Result<int>() >= 0);
 6         return _items.Length;
 7     }
 8     set
 9     {
10         if (value < _size)
11         {
12             throw new ArgumentOutOfRangeException(nameof(value), value, SR.ArgumentOutOfRange_SmallCapacity);
13         }
14         Contract.EndContractBlock();
15 
16         if (value != _items.Length)
17         {
18             if (value > 0)
19             {
20                 var items = new T[value];
21                 Array.Copy(_items, 0, items, 0, _size);
22                 _items = items;
23             }
24             else
25             {
26                 _items = _emptyArray;
27             }
28         }
29     }
30 }

Capacity取的就是数组的长度,另外我们可以通过Capacity给List设置大小,即使这个List里面已经有元素,会先new一个目标大小的数组,然后通过Array.Copy把现有元素复制到新数组里。但一般情况下这些不用我们设置Capacity,添加新元素时发现长度不够会自动扩大数组。Capacity是int型,说明最大是int.MaxValue,大约2G个,如果我们直接给List设置int.MaxValue就要看你的内存够不够2G*4也就是8G了,不够的话会报OutofMemory Exception。其实个人觉得这里Capacity用uint是不是更好。

用100M个,内存占用400M多

同样100M个,由于是long,内存占了800M多

方法

看几个重要的方法:

1 public void Add(T item)
2 {
3     if (_size == _items.Length) EnsureCapacity(_size + 1);
4     _items[_size++] = item;
5     _version++;
6 }

当前数组大小和元素个数相等时表明再Add的话大小不够了,需要先通过EnsureCapacity扩容, _size+1指明了一个最小的扩容目标。

 1 private void EnsureCapacity(int min)
 2 {
 3     if (_items.Length < min)
 4     {
 5         int newCapacity = _items.Length == 0 ? _defaultCapacity : _items.Length * 2;
 6         // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
 7         // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
 8         //if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
 9         if (newCapacity < min) newCapacity = min;
10         Capacity = newCapacity;
11     }
12 }

扩容方法,如果数组长度是0的话则用_defaultCapacity也就是4来做为数组长度,否则则以当前元素个数的2倍去扩大。如果新得到的长度比传进来的min小的话则就用min,也就是选大的,这种情况在InsertRange时有可能发生,因为insert的list很可能比当前list的元素个数多。

Add函数里还有个_version++,这个_version可以在很多方法里看到,如remove, insert, sort等,但凡要修改集合都需要_version++。那这个_version有什么用呢?

 1 public void ForEach(Action<T> action)
 2 {
 3     if (action == null)
 4     {
 5         throw new ArgumentNullException(nameof(action));
 6     }
 7 
 8     int version = _version;
 9 
10     for (int i = 0; i < _size; i++)
11     {
12         if (version != _version)
13         {
14             break;
15         }
16         action(_items[i]);
17     }
18 
19     if (version != _version)
20         throw new InvalidOperationException(SR.InvalidOperation_EnumFailedVersion);
21 }

在遍历时如果发现_version变了立即退出并抛出遍历过程集合被修改异常,比如在foreach里remove或add元素就会导致这个异常。更常见的是出现在多线程时一个线程遍历集合,另一个线程修改集合的时候,相信很多人吃过苦头。

如果一个线程时想在遍历时修改集合,比如删除,可以用原始的for(int i=list.Count-1;i>=0;i--)方式。

另外用到version还有枚举器Enumerator,MoveNext过程中同样会检测这个。

其他大部分方法都是通过Array的静态函数实现,不多说,需要注意的是List<T>继承自IList,所以可以转成IList,转之后泛型就没了,如果是List<int>,转成IList的话和IList<object>没什么两样,装拆箱带来的性能损失也值得注意。

总结

List<T>初始大小是4,自动扩容是以当前数组元素的两倍或InsertRange目标list的元素个数来扩容(哪个大选哪个)。如果有比较确定的大小可以考虑提前设置,因为每次自动扩容需要重新分配数组和copy元素,性能损耗不小。

List<T>通过version来跟踪集合是否发生改变,如果在foreach遍历时发生改变则抛出异常。

List<T>并非线程安全,任何使用的时候都要考虑当前环境是否可能有多线程存在,是否需要用锁来保证集合线程安全。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

scala 学习笔记(06) OOP(下)多重继承 及 AOP

一、多继承 上篇trait中,已经看到了其用法十分灵活,可以借此实现类似"多重继承"的效果,语法格式为: class/trait A extends B wit...

18110
来自专栏个人随笔

房上的猫:数组插入算法等难点专开

一:查找算法 public class Aini { public static void main(String[] args) { ...

3378
来自专栏GreenLeaves

Linq基础知识之延迟执行

Linq中的绝大多数查询运算符都有延迟执行的特性,查询并不是在查询创建的时候执行,而是在遍历的时候执行,也就是在enumerator的MoveNext()方法被...

19810
来自专栏张善友的专栏

在Entity Framework 中执行T-sql语句

从Entity Framework  4开始在ObjectContext对象上提供了2个方法可以直接执行SQL语句:ExecuteStoreQuery<T> 和...

17810
来自专栏用户画像

JAVA笔试题

4.public、private、protected、Friendly的区别与作用域,以及不写时的区别?

521
来自专栏技术小讲堂

WCF中的集合类型

在.net中,各种类型的集合均实现了IEnumerable或者IEnumerable<T>接口,一个数据契约的数据成员可以是一个集合类型,服务契约也可以定义直接...

2606
来自专栏逸鹏说道

Python3 与 C# 扩展之~基础衍生

在线编程: https://mybinder.org/v2/gh/lotapp/BaseCode/master

1837
来自专栏Java开发者杂谈

java如何获取一个对象的大小

When---什么时候需要知道对象的内存大小 在内存足够用的情况下我们是不需要考虑java中一个对象所占内存大小的。但当一个系统的内存有限,或者某块程序代码允许...

4436
来自专栏窗户

深入设计电子计算器(一)——CPU框架及指令集设计

前几天写了一篇《如何设计一个电子计算器》,一个朋友看了之后说实在太low,好吧,依照他的意思,那我就采用文中FPGA设计的方式,然后自己从指令集设计、cpu设...

1736
来自专栏码神联盟

java常见异常汇总

程序猿的成长之路,从这开始.......... ? 在6月的投票中,结果昨天已经出来了,大家多数的希望多推送一些java的基础知识。首先来一下热...

3246

扫码关注云+社区