|
|
C#中List的深入理解
1. 简介
List是怎么在内存中进行存储，它为什么可以一直add数据，不用像数组一样，在申明的时候直接就定死长度。它又为什么能像list一样直接用list[0]直接取数据。
大批量数据并发add到list中，会发生什么情况？
我去翻找了一下源代码
public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T> private const int _defaultCapacity = 4; private T[] _items; [ContractPublicPropertyName("Count")] private int _size; private int _version; [NonSerialized] private Object _syncRoot; static readonly T[] _emptyArray = new T[0]; // Constructs a List. The list is initially empty and has a capacity // of zero. Upon adding the first element to the list the capacity is // increased to 16, and then increased in multiples of two as required. public List() { _items = _emptyArray; // Gets and sets the capacity of this list. The capacity is the size of // the internal array used to hold items. When set, the internal // array of the list is reallocated to the given capacity. public int Capacity { get { Contract.Ensures(Contract.Result<int>() >= 0); return _items.Length; set { if (value < _size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity); Contract.EndContractBlock(); if (value != _items.Length) { if (value > 0) { T[] newItems = new T[value]; if (_size > 0) { Array.Copy(_items, 0, newItems, 0, _size); _items = newItems; else { _items = _emptyArray; public void Add(T item) { if (_size == _items.Length) EnsureCapacity(_size + 1); _items[_size++] = item; _version++; private void EnsureCapacity(int min) { if (_items.Length < min) { int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2; // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow. // Note that this check works even when _items.Length overflowed thanks to the (uint) cast if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength; if (newCapacity < min) newCapacity = min; Capacity = newCapacity;
我去，一看源代码，我才知道，list里面数据的存储，根本就是用数组进行存储。
在
new List()
的时候，是直接声明了一个泛型数组
_items = _emptyArray;
,怪不得它可以像数组一样直接[]取值，他根本就是数组啊。
2. list为什么可以一直add
我看了一下add方法的实现原理，我去....，它在实现的时候执行了这一步
if (_size == _items.Length) EnsureCapacity(_size + 1);
，如果当前数组的长度和我们记录元素的数量一致时，执行函数
EnsureCapacity(_size + 1)
，重新定义了一下这个list的容量，第一次添加默认存储容量4，如果list持续添加新成员，变量
Capacity
会重新赋值，每次都是原来的数组长度*2。
3. list内部是用数组来存储数据，数组一开始长度都是固定死的，那它是怎么扩充长度呢？
Array.Copy(_items, 0, newItems, 0, _size);
哈哈哈...，里面直接建了一个新的数组，然后将老的数组拷贝了过去，看来如果是大数量list数据的添加，new的时候要直接带一个大点的长度，不然内部会一直创建新数组替换老数组。
4. 大批量数据并发插入list
创建了一个控制台，模拟大批量数据的插入,发现插入的数量不够，还容易报出异常，代码如下。
class Program
private static List<Student> _students { get; set; }
private static int n1 = 0;
static void Main(string[] args)
_students = new List<Student>();
Task t1 = Task.Factory.StartNew(() =>
AddStudents();
Task t2 = Task.Factory.StartNew(() =>
AddStudents();
Task t3 = Task.Factory.StartNew(() =>
AddStudents();
Task.WaitAll(t1, t2, t3);//同步执行
Console.WriteLine(_students.Count);
for (int i=0; i <_students.Count;i++)
if(_students[i] is null)
n1++;
Console.WriteLine("第"+i+"个是空值");
Console.WriteLine("总共"+n1+"个是空值");
Console.ReadLine();
static void AddStudents()
Parallel.For(0, 1000, (i) =>
Student student = new Student();
student.Name = "name" + i;
student.Age = i;
_students.Add(student);
class Student
public string Name { get; set; }
public int Age { get; set; }
添加了3000个，结果只添加了2225个，还有是null的空值。
翻翻代码，找找原因，发现在add添加的时候，多线程并发时，_size++ 执行了多次，_items[_size++] = item; 赋值才赋上，所以才有21个null值，可这也才21个null值啊，还差很多啊，怀疑是在赋值时_items[_size++] = item; ，有数据进行了覆盖，就是list[6]=1，同时又来了个list[6]=2，这个不好验证啊，先跳过了。
并发时，还容易出现异常情况。
list2.PNG
在上面我们知道，list添加的时候，超出了数组界限，就会创建新的数组取代老的数组，可是多线程下，在数组最后一位赋值时，我们同时执行了两次或多次的_size++ ，赋值就会出现索引超出数组界限的情况。
5. 如何解决并发插入list混乱的问题
5.1 使用lock，就是效率有点低
lock (_students)
Student student = new Student();
student.Name = "name" + i;
student.Age = i;
_students.Add(student);
5.2 使用微软提供的新方法，System.Collections.Concurrent.ConcurrentQueue<T>
专门解决多线程并发问题，而且效率高。
不知道list还有没有其它方法解决并发问题。