本文的寫作沖動來源于今晚看到的老趙的一則微博“大家知道System.Collections.Generic.List<T>是一種什么樣的數據結構？內部的元素是怎么存放的？還有Dictionary<TKey,TValue>呢？…”。
查了一下書，如果參考數據結構和算法里介紹的線性表合哈希表的特點，非常官方的答案就類似：List<T>是一種線性的內存連續分配的存儲結構，元素是順序存放的；它的優點是內存連續分配，相對節省空間，在設定長度范圍內增加元素開銷很小；缺點是查找復雜度為O(n)，不如哈希結構O(1)復雜度來的快，如插入節點超過指定長度需要重新開辟內存，開銷很大云云。而Dictionary<TKey,TValue>則是哈希結構，優點blahblahblah缺點blahblahblah。回答結束。
然后再看老趙微博下面的回答，似乎很不統一，多數認為是基于數組實現的，但是…擦，看一圈都沒有老趙滿意的答案。以前看過文章聽說過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 < length)
{
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 < chunkChars.Length) //沒有超過最大容量
{
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 < 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<T>分析一下。
和StringBuilder分析法類似，我們也從構造函數和Add方法著手分析。
無參構造函數如下：
public List()
{
this._items = List<T>._emptyArray;
}
_items是個泛型數組（private T[] _items;泛型數組好像不能這么說？），通過構造函數它肯定有默認初始容量了,_emptyArray肯定初始化分配了一定空間，猜對了嗎？_emptyArray定義如下： private static readonly T[] _emptyArray = new T[0];
看看有一個參數的：
public List(int capacity)
{
if (capacity < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
this._items = new T[capacity];
}
這回直接給_items new了一個數組對象。好，再來一個傳入初始集合的：
public List(IEnumerable<T> collection)
{
if (collection == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection);
}
ICollection<T> collection2 = collection as ICollection<T>;
if (collection2 != null)
{
int count = collection2.Count;
this._items = new T[count];
collection2.CopyTo(this._items, 0);
this._size = count;
return;
}
this._size = 0;
this._items = new T[4];
using (IEnumerator<T> enumerator = collection.GetEnumerator())
{
while (enumerator.MoveNext())
{
this.Add(enumerator.Current);
}
}
}
到這里估計大家都看到關鍵的地方了：每個構造函數都要對_items 變量進行初始化，而這個_items 正是一個數組（如我們所知，泛型List確實是基于數組實現的）。再來分析下增刪改查中的增加也就是Add方法：
public void Add(T item)
{
if (this._size == this._items.Length)
{
this.EnsureCapacity(this._size + 1); //擴容函數
}
this._items[this._size++] = item; //通過索引器賦值，添加元素
this._version++;
}
我們目標明確，終于找到了擴容函數EnsureCapacity：
private void EnsureCapacity(int min)
{
if (this._items.Length < min)
{
int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2); //容量=當前的長度的兩倍
if (num < min)
{
num = min;
}
this.Capacity = num; //當前數組容量賦值
}
}
到這里，我們看到，添加一個元素的時候，如果容量沒超過預分配的數組空間大小，直接通過下面的索引器賦值：
public T this[int index]
{
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
get
{
if (index >= this._size)
{
ThrowHelper.ThrowArgumentOutOfRangeException();
}
return this._items[index];
}
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
set
{
if (index >= this._size)
{
ThrowHelper.ThrowArgumentOutOfRangeException();
}
this._items[index] = value;
this._version++;
}
}
如果新增的項超過了現有數組的最大容量，通過擴容函數進行容量再分配（再new一個數組對象），在函數EnsureCapacity中，我們看到：int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2); //容量=當前的長度的兩倍這里進行了數組容量的重新計算，方法很簡單。最重要的是給屬性Capacity賦值：
this.Capacity = num; //當前數組容量賦值這個屬性的set里面包含了數組new的操作：
public int Capacity
{
[TargetedPatchingOptOut("Performance critical to inline across NGen image boundaries")]
get
{
return this._items.Length;
}
set
{
if (value < this._size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value != this._items.Length)
{
if (value > 0)
{
T[] array = new T[value]; //重新初始化一個數組
if (this._size > 0)
{
Array.Copy(this._items, 0, array, 0, this._size);
}
this._items = array; //新數組指向原數組，原數組丟棄
return;
}
this._items = List<T>._emptyArray;
}
}
}
分析到這里我們完全可以通過偽代碼總結出集合的擴容算法：
public void Add(T item)
{
判斷當前元素個數是否等于它預設定的容量
if(等于)
{
重新分配內存空間(前一次的空間乘以二)
利用Array.Copy方法把元素復制到新分配的空間
}
設置元素的當前位置
currentIndex++;
this[currentIndex] = item;
}
也許有人會問，重新分配內存空間時直接簡單的乘以2會不會太草率了，這樣不是容易造成內存空間的浪費嗎？MS的實現也不都是非常嚴謹的嘛？確實，緩沖區擴容的時候，如數據量較大，很明顯會造成內存浪費，泛型List提供了一個方法叫TrimExcess用來解決內存浪費的問題：
public void TrimExcess()
{
int num = (int)((double)this._items.Length * 0.9); //當前數組空間容量乘以0.9
if (this._size < num)
{
this.Capacity = this._size; //重新設置數組空間
}
}
原理也就是一個簡單的數學方法，你在外部調用一次或多次，它就會自動幫你平衡空間節省內存了。有一個非常常用的功能就是判斷元素是否在列表里，方法名就是熟悉的Contains，看代碼果然是O(n)復雜度：
public bool Contains(T item)
{
if (item == null)
{
for (int i = 0; i < this._size; i++)
{
if (this._items[i] == null)
{
return true;
}
}
return false;
}
EqualityComparer<T> @default = EqualityComparer<T>.Default;
for (int j = 0; j < this._size; j++)
{
if (@default.Equals(this._items[j], item))
{
return true;
}
}
return false;
}
大功告成，哈哈，我驚詫極了目瞪口呆，泛型List果然也是基于數組的，而且我們現在可以理直氣壯地說我很清楚它的內部擴容實現算法。此時我真想拍著肩膀對自己說，哥們你辛苦了，太有成就感了，抓緊時間多想想你喜歡的姑娘吧……我果然又紅光滿面了。然后，再查看源碼，發現很多核心方法的實現都直接對_items數組進行操作，并多次調用了Array的靜態方法，所以我們一定不可小視數據結構數組(Array)。
反匯編查看Array的源碼，發現增刪改查方法相當之豐富，哪位有心人可以挖掘挖掘里面使用了多少種經典算法（比如BinarySearch聽說用了二分查找），反正感覺它是被我大大低估了。至少現在我們知道，經常使用的常用數據結構如StringBuilder、ArrayList，泛型List，Queue，Stack等等都是基于Array實現的。不要小看了它，隨著framework的發展，也許未來還會不斷出現基于Array的新的數據結構的出現。
三、基于Array的可動態擴容的哈希結構
平時開發中經常使用的其他的一些數據結構如HashTable，泛型Dictionary，HashSet以及線程安全容器ConcurrentDictionary等等也可以動態擴容。下面從HashTable源碼入手簡單分析下。
先從無參構造函數開始：
public Hashtable()
: this(0, 1f)
{
}
無參構造函數最終需要調用的構造方法如下：
public Hashtable(int capacity, float loadFactor)
{
if (capacity < 0)
{
throw new ArgumentOutOfRangeException("capacity", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
}
if (loadFactor < 0.1f || loadFactor > 1f)
{
throw new ArgumentOutOfRangeException("loadFactor", Environment.GetResourceString("ArgumentOutOfRange_HashtableLoadFactor", new object[]
{
0.1,
1.0
}));
}
this.loadFactor = 0.72f * loadFactor; //負載因子 熟悉又陌生的0.72
double num = (double)((float)capacity / this.loadFactor);
if (num > 2147483647.0)
{
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
}
int num2 = (num > 3.0) ? HashHelpers.GetPrime((int)num) : 3; //初始化數組空間
this.buckets = new Hashtable.bucket[num2]; //原來是bucket結構構造的數組
this.loadsize = (int)(this.loadFactor * (float)num2);
this.isWriterInProgress = false;
}
正如我們所知，哈希函數的計算結果是一個存儲單位地址，每個存儲單位稱為桶，而buckets不正是我們要找的存儲散列函數計算結果的哈希桶嗎？原來它也是個數組。這里大家看到了嗎？this.buckets原來就是一個struct結構數組，心里好像一下子就有底了。好，接著找動態擴容函數，從Add方法入手吧：
public virtual void Add(object key, object value)
{
this.Insert(key, value, true);
}
跟蹤到Insert方法，代碼一下子變得內容豐富，但是我們直接看到了一個判斷語句：
if (this.count >= this.loadsize)
{
this.expand();
}
上面這個if判斷一目了然，expand不就是擴展的意思嗎？跟進去：
private void expand()
{
int prime = HashHelpers.GetPrime(this.buckets.Length * 2); //直接乘以2 好像還有個輔助調用獲取素數 HashHelpers.GetPrime
this.rehash(prime); //重新hash
}
有個rehash函數，再跟進去：
private void rehash(int newsize)
{
this.occupancy = 0;
Hashtable.bucket[] newBuckets = new Hashtable.bucket[newsize]; //重新定義哈希buckets
for (int i = 0; i < this.buckets.Length; i++) //竟然是遍歷舊buckets，然后填充新buckets
{
Hashtable.bucket bucket = this.buckets[i];
if (bucket.key != null && bucket.key != this.buckets)
{
this.putEntry(newBuckets, bucket.key, bucket.val, bucket.hash_coll & 2147483647);
}
}
Thread.BeginCriticalRegion();
this.isWriterInProgress = true;
this.buckets = newBuckets; //舊buckets的引用改變為新填充的newBuckets
this.loadsize = (int)(this.loadFactor * (float)newsize);
this.UpdateVersion();
this.isWriterInProgress = false;
Thread.EndCriticalRegion();
}
果然又看到了數組的重新定義和再賦值：this.buckets = newBuckets;這不就又回到老路上來了嗎？再查查Array出現的頻率，哈希表很多方法的實現也還是數組操作來操作去的。到這里，忍不住想起周星馳電影里的話：打完收功。
但是還沒完，有一個動態擴容容量的計算問題，是和泛型列表一樣的直接乘以2嗎？在expand函數里我們看到了下面這一行：
int prime = HashHelpers.GetPrime(this.buckets.Length * 2);
很顯然，乘以2以后還需要一個輔助函數HashHelpers.GetPrime（看命名就知道是獲取素數）的運算，HashHelpers.GetPrime代碼如下：
internal static int GetPrime(int min)
{
if (min < 0)
{
throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
}
for (int i = 0; i < HashHelpers.primes.Length; i++)
{
int num = HashHelpers.primes[i];
if (num >= min)
{
return num;
}
}
for (int j = min | 1; j < 2147483647; j += 2)
{
if (HashHelpers.IsPrime(j))
{
return j;
}
}
return min;
}
}
獲取素數的實現好像還蠻熟悉的。繼續跟蹤HashHelpers，發現它的primes數組列舉了最小為3，最大為7199369的素數。如果你的哈希表容量不是特別大，3到7199369的素數足夠使用了（符合二八原則），否則哈希表擴容的時候需要在2147483647這個數字范圍內通過HashHelpers.IsPrime來判斷并動態生成素數。所以簡單地說哈希表擴容后的容量是原來的兩倍并不準確，這個就和哈希算法對素數的要求有直接關系，在不太精確的情況下我們可以認為約等于兩倍。出于好奇順便查看了一下泛型字典的源碼，它的內部實現包含了buckets和entries兩個結構數組，還發現哈希結構的容器通常內部算法果然都比較繞。我猜它們的實現也不同程度地利用了數組的特點，說到底應該也是基于Array實現的吧（看到沒，不知道就算無責任亂寫）？其他的幾種常見哈希結構的容器還沒有認真看，有興趣大家可以直接查看源碼詳細分析一下，挑典型的一兩個對比著看應該非常有效果。
歡迎大家暢所欲言說說你所知道的基于Array的其他數據結構，這里我就不再班門弄斧貽笑大方了。
思考：拋一個弱弱的疑問向大家求證：實現容器的動態特性是不是必須要基于數組呢，基于數組的實現是唯一的方式嗎？
