本篇文章是对从源码分析常见的基于Array的数据结构动态扩容机制进行了详细的分析介绍，需要的朋友参考下
本文的写作冲动来源于今晚看到的老赵的一则微博“大家知道System.Collections.Generic.List
查了一下书，如果参考数据结构和算法里介绍的线性表合哈希表的特点，非常官方的答案就类似：List
然后再看老赵微博下面的回答，似乎很不统一，多数认为是基于数组实现的，但是…擦，看一圈都没有老赵满意的答案。以前看过文章听说过StringBuilder和HashTable内部是怎么实现的，以及一个笼统的列表内存扩容两倍说，但是一直不知道具体细节也不太肯定，所以我也很想知道答案。老赵说稍微有点儿好奇心的程序员都应该会去看看两个实现的源代码。世上无难事只怕有心人，要是真的有心人顺便还应该不论对错记录一下自己的学习心得，哈哈。
注：如果你是新手，建议直接到此为止，不要再往下看了。实在好奇想知道答案，最简单正确也是我的偶像老赵所推荐的做法当然是自己查MSDN和framework源码。为了不误导人，本文再加上一个标签：无责任乱写。
一、StringBuilder
StringBuilder有6种构造函数，直接通过无参构造函数创建对象比较常见。MSDN（中文）里说“此实现的默认容量是 16，默认的最大容量是 Int32.MaxValue”。默认容量是16，16什么呢，这话怎么说得这么模糊呢？反汇编跟一下源码，看到它的构造函数最终要调用一个方法：
public unsafe StringBuilder(string value, int startIndex, int length, int capacity)
{
if (capacity <0)
{
throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_MustBePositive", new object[]
{
"capacity"
}));
}
if (length <0)
{
throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_MustBeNonNegNum", new object[]
{
"length"
}));
}
if (startIndex <0)
{
throw new ArgumentOutOfRangeException("startIndex", Environment.GetResourceString("ArgumentOutOfRange_StartIndex"));
}
if (value == null)
{
value = string.Empty;
}
if (startIndex > value.Length - length)
{
throw new ArgumentOutOfRangeException("length", Environment.GetResourceString("ArgumentOutOfRange_IndexLength"));
}
this.m_MaxCapacity = 2147483647;
if (capacity == 0)
{
capacity = 16; //默认值
}
if (capacity
capacity = length;
}
this.m_ChunkChars = new char[capacity]; //字符数组容量初始化
this.m_ChunkLength = length;
fixed (char* ptr = value)
{
StringBuilder.ThreadSafeCopy(ptr + (IntPtr)startIndex, this.m_ChunkChars, 0, length);
}
}
默认容量16，其实估计是指默认预分配的字符串容量为16个字符。
再分析其中带两个参数的：public StringBuilder(int capacity, int maxCapacity)，它的主要实现如下：
public StringBuilder(int capacity, int maxCapacity)
{
if (capacity > maxCapacity)
{
throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_Capacity"));
}
if (maxCapacity <1)
{
throw new ArgumentOutOfRangeException("maxCapacity", Environment.GetResourceString("ArgumentOutOfRange_SmallMaxCapacity"));
}
if (capacity <0)
{
throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_MustBePositive", new object[]
{
"capacity"
}));
}
if (capacity == 0)
{
capacity = Math.Min(16, maxCapacity); //将最大容量和默认容量16进行比较，取较小的
}
this.m_MaxCapacity = maxCapacity;
this.m_ChunkChars = new char[capacity];
}
这里就有一个疑问：通常我们实现字符串拼接的时候，肯定不能保证字符串的容量不大于默认容量16，如果大于16，StringBuilder是如何实现这种动态扩容效果的呢，总不能一下子就留足内存吧？我们看一下常见的Append(string value)方法是如何实现的：
public unsafe StringBuilder Append(string value)
{
if (value != null)
{
char[] chunkChars = this.m_ChunkChars;
int chunkLength = this.m_ChunkLength;
int length = value.Length;
int num = chunkLength + length;
if (num
if (length <= 2) //2个及2个以下字符拼接
{
if (length > 0)
{
chunkChars[chunkLength] = value[0];
}
if (length > 1)
{
chunkChars[chunkLength + 1] = value[1];
}
}
else
{
fixed (char* smem = value)
{
fixed (char* ptr = &chunkChars[chunkLength])
{
string.wstrcpy(ptr, smem, length); //好像C函数 看不到内部实现
}
}
}
this.m_ChunkLength = num;
}
else
{
this.AppendHelper(value);
}
}
return this;
}
上面的代码中，对于超过拼接后默认最大容量的字符串的逻辑在AppendHelper中，AppendHelper最终是通过下面的方法实现的：
internal unsafe StringBuilder Append(char* value, int valueCount)
{
int num = valueCount + this.m_ChunkLength;
if (num <= this.m_ChunkChars.Length)
{
StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, valueCount);
this.m_ChunkLength = num;
}
else
{
int num2 = this.m_ChunkChars.Length - this.m_ChunkLength;
if (num2 > 0)
{
StringBuilder.ThreadSafeCopy(value, this.m_ChunkChars, this.m_ChunkLength, num2);
this.m_ChunkLength = this.m_ChunkChars.Length;
}
int num3 = valueCount - num2;
this.ExpandByABlock(num3); //终于看到扩容函数了
StringBuilder.ThreadSafeCopy(value + (IntPtr)num2, this.m_ChunkChars, 0, num3);
this.m_ChunkLength = num3;
}
return this;
}
接着来分析扩容函数ExpandByABlock：
private void ExpandByABlock(int minBlockCharCount)
{
if (minBlockCharCount + this.Length > this.m_MaxCapacity)
{
throw new ArgumentOutOfRangeException("requiredLength", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
}
int num = Math.Max(minBlockCharCount, Math.Min(this.Length, 8000)); //重新分配数组的空间计算
this.m_ChunkPrevious = new StringBuilder(this);
this.m_ChunkOffset += this.m_ChunkLength;
this.m_ChunkLength = 0;
if (this.m_ChunkOffset + num
this.m_ChunkChars = null;
throw new OutOfMemoryException();
}
this.m_ChunkChars = new char[num]; //数组重新分配空间
}
从上面的直白分析我们可明显看出，实例化一个StringBuilder必然要初始化并维护一个内部数组char[] m_ChunkChars。而学过C语言和数据结构的应该都知道，数组对于它的创建需要预先给出一定的连续分配的内存空间,它并不支持在原有的内存空间的基础上去扩展，所以数组对于动态内存分配是极为不利的，但是基本的数据结构如字符串和线性表就是基于数组实现的。
接着简单看了一下其他几个常用拼接方法和索引器，内部实现大致一样，几乎都是对字符数组的操作逻辑。有兴趣大家不妨也看看源码。
分析到这里，我们可以大胆假设：StringBuilder内部实现的字符串操作最终是通过字符数组char[] m_ChunkChars进行处理的。想一想也对啊，如果StringBuildr的实现是通过String加等于减等于地拼过来接过去那就逊掉了。
不能忽视的是它的扩展容量的算法，最关键的就是下面这行代码：
int num = Math.Max(minBlockCharCount, Math.Min(this.Length, 8000));其实是非常简单的数学方法，StringBuilder内部的MaxChunkSize默认为8000，大家可以评估一下，如果进行多次拼接，字符串长度随机一点，内存分配情况会怎么样，8000这个数字有没有道理。据传说和GC内部算法一样，framework一些常用类的内部实现也遵循着平衡的设计，不知真假。
二、基于Array的可动态扩容的线性结构
大家应该都非常熟悉，就像StringBuilder一样，framework中很多集合都有动态扩容效果。比如我们熟悉的线性集合ArrayList，泛型List，Queue，Stack等等，这些都是直接基于Array而实现的。
那么基于Array的集合它们内部是如何实现动态扩容的，扩容的量是怎么控制的？也许我们早有耳闻，就是动态扩展的容量是上一次已有容量的两倍，到底是不是这样的呢？带着疑问我们挑一个最常见的集合泛型List
和StringBuilder分析法类似，我们也从构造函数和Add方法着手分析。
无参构造函数如下：
public List()
{
this._items = List
}
以上就是解析从源码分析常见的基于Array的数据结构动态扩容机制的详解的详细内容，更多请关注0133技术站其它相关文章！
