讲解c#中ArrayList是怎么实现的自动扩容增长?

讲解c#中ArrayList是怎么实现的自动扩容增长?

362发表于2018-09-26

我们都知道c#中的ArrayList是一个类似数组的集合,使用的时候不用像数组那样需要先定义数组的大小。

ArrayList具有自动扩容增长的功能,那么它的底层是怎么实现的呢?Java中其实也是类似的原理。

ArrayList在空间System.Collections下面:

可以看到,ArrayList实现了接口,IList,ICollectiton等接口,且里面定义一些内部的私有类,这些类我们暂且不管它。

我们关心的是ArrayList的类。

可以从上面截图看到有几个属性很重要:

private object[] _items;//用于存储元素类型为object,因此可以用来存任何类型,注意:这个数组不是所有都有值

private int _size;//集合实际元素大小,自动扩容将要用到的

private const int _defaultCapacity = 4;//默认初始容量。


下面我们从,Add方法开始:

public virtual int Add(object value)
{
	if (this._size == this._items.Length)
	{
		this.EnsureCapacity(this._size + 1);//当没有空间后自动增加空闲空间
	}
	this._items[this._size] = value;//把要add的元素加到数组最后一个的后面
	this._version++;
	int size = this._size;
	this._size = size + 1;//更新size值,保持size始终为实际元素的数量
	return size;
}
我们再来看看EnsureCapacity这个方法:
private void EnsureCapacity(int min)
{
	if (this._items.Length < min)
	{
		int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2);//默认为大小为4,否则按当前大小的2倍大小增加空间。
		if (num > 2146435071)
		{
			num = 2146435071;
		}
		if (num < min)
		{
			num = min;
		}
		this.Capacity = num;
	}
}
参数min表示添加时需要的最小容量,我们在上面Add方法可以看到传入的最小为当前实际真正size+1。

我们添加元素的时候假如遇到如下情况:

ArrayList大小为4,里面有4个元素,正好满了。那么_items.length为4,size为4。

当我们Add的时候调用EnsureCapacity时min为4+1=5,这个时候,_items.length<min

这个时候num为4*2=8。并会执行:

this.Capacity = num;

Capacity是一个属性,代码如下:

public virtual int Capacity
{
	get
	{
		return this._items.Length;
	}
	set
	{
		if (value < this._size)
		{
			throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
		}
		if (value != this._items.Length)
		{
			if (value > 0)
			{
				object[] array = new object[value];//当设容量更改时,声明一个更大的新数组,达到扩容的效果
				if (this._size > 0)
				{
					Array.Copy(this._items, 0, array, 0, this._size);//拷贝原来的元素到新数组
				}
				this._items = array;//把原来的数组引用指向,上面的拷贝后的新数组。
				return;
			}
			this._items = new object[4];
		}
	}
}
可以看到在set属性时会执行一段代码,主要作用就是就是声明新数组,然后拷贝原来数据,最后更新_items引用到新的数组。

为了提高性能,这里的Array.Copy是一个外部方法,是用c或c++实现的本地方法。



小编蓝狐