解析從源碼分析常見的基于Array的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)擴(kuò)容機(jī)制的詳解
本文的寫作沖動(dòng)來源于今晚看到的老趙的一則微博“大家知道System.Collections.Generic.List<T>是一種什么樣的數(shù)據(jù)結(jié)構(gòu)？內(nèi)部的元素是怎么存放的？還有Dictionary<TKey,TValue>呢？…”。
查了一下書，如果參考數(shù)據(jù)結(jié)構(gòu)和算法里介紹的線性表合哈希表的特點(diǎn)，非常官方的答案就類似：List<T>是一種線性的內(nèi)存連續(xù)分配的存儲(chǔ)結(jié)構(gòu)，元素是順序存放的；它的優(yōu)點(diǎn)是內(nèi)存連續(xù)分配，相對(duì)節(jié)省空間，在設(shè)定長度范圍內(nèi)增加元素開銷很?。蝗秉c(diǎn)是查找復(fù)雜度為O(n)，不如哈希結(jié)構(gòu)O(1)復(fù)雜度來的快，如插入節(jié)點(diǎn)超過指定長度需要重新開辟內(nèi)存，開銷很大云云。而Dictionary<TKey,TValue>則是哈希結(jié)構(gòu)，優(yōu)點(diǎn)blahblahblah缺點(diǎn)blahblahblah?；卮鸾Y(jié)束。
然后再看老趙微博下面的回答，似乎很不統(tǒng)一，多數(shù)認(rèn)為是基于數(shù)組實(shí)現(xiàn)的，但是…擦，看一圈都沒有老趙滿意的答案。以前看過文章聽說過StringBuilder和HashTable內(nèi)部是怎么實(shí)現(xiàn)的，以及一個(gè)籠統(tǒng)的列表內(nèi)存擴(kuò)容兩倍說，但是一直不知道具體細(xì)節(jié)也不太肯定，所以我也很想知道答案。老趙說稍微有點(diǎn)兒好奇心的程序員都應(yīng)該會(huì)去看看兩個(gè)實(shí)現(xiàn)的源代碼。世上無難事只怕有心人，要是真的有心人順便還應(yīng)該不論對(duì)錯(cuò)記錄一下自己的學(xué)習(xí)心得，哈哈。
注：如果你是新手，建議直接到此為止，不要再往下看了。實(shí)在好奇想知道答案，最簡單正確也是我的偶像老趙所推薦的做法當(dāng)然是自己查MSDN和framework源碼。為了不誤導(dǎo)人，本文再加上一個(gè)標(biāo)簽：無責(zé)任亂寫。
一、StringBuilder
StringBuilder有6種構(gòu)造函數(shù)，直接通過無參構(gòu)造函數(shù)創(chuàng)建對(duì)象比較常見。MSDN（中文）里說“此實(shí)現(xiàn)的默認(rèn)容量是 16，默認(rèn)的最大容量是 Int32.MaxValue”。默認(rèn)容量是16，16什么呢，這話怎么說得這么模糊呢？反匯編跟一下源碼，看到它的構(gòu)造函數(shù)最終要調(diào)用一個(gè)方法：
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; //默認(rèn)值
}
if (capacity < length)
{
capacity = length;
}
this.m_ChunkChars = new char[capacity]; //字符數(shù)組容量初始化
this.m_ChunkLength = length;
fixed (char* ptr = value)
{
StringBuilder.ThreadSafeCopy(ptr + (IntPtr)startIndex, this.m_ChunkChars, 0, length);
}
}
默認(rèn)容量16，其實(shí)估計(jì)是指默認(rèn)預(yù)分配的字符串容量為16個(gè)字符。
再分析其中帶兩個(gè)參數(shù)的：public StringBuilder(int capacity, int maxCapacity)，它的主要實(shí)現(xiàn)如下：
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); //將最大容量和默認(rèn)容量16進(jìn)行比較，取較小的
}
this.m_MaxCapacity = maxCapacity;
this.m_ChunkChars = new char[capacity];
}
這里就有一個(gè)疑問：通常我們實(shí)現(xiàn)字符串拼接的時(shí)候，肯定不能保證字符串的容量不大于默認(rèn)容量16，如果大于16，StringBuilder是如何實(shí)現(xiàn)這種動(dòng)態(tài)擴(kuò)容效果的呢，總不能一下子就留足內(nèi)存吧？我們看一下常見的Append(string value)方法是如何實(shí)現(xiàn)的：
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個(gè)及2個(gè)以下字符拼接
{
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函數(shù) 看不到內(nèi)部實(shí)現(xiàn)
}
}
}
this.m_ChunkLength = num;
}
else
{
this.AppendHelper(value);
}
}
return this;
}
上面的代碼中，對(duì)于超過拼接后默認(rèn)最大容量的字符串的邏輯在AppendHelper中，AppendHelper最終是通過下面的方法實(shí)現(xiàn)的：
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); //終于看到擴(kuò)容函數(shù)了
StringBuilder.ThreadSafeCopy(value + (IntPtr)num2, this.m_ChunkChars, 0, num3);
this.m_ChunkLength = num3;
}
return this;
}
接著來分析擴(kuò)容函數(shù)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)); //重新分配數(shù)組的空間計(jì)算
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]; //數(shù)組重新分配空間
}
從上面的直白分析我們可明顯看出，實(shí)例化一個(gè)StringBuilder必然要初始化并維護(hù)一個(gè)內(nèi)部數(shù)組char[] m_ChunkChars。而學(xué)過C語言和數(shù)據(jù)結(jié)構(gòu)的應(yīng)該都知道，數(shù)組對(duì)于它的創(chuàng)建需要預(yù)先給出一定的連續(xù)分配的內(nèi)存空間,它并不支持在原有的內(nèi)存空間的基礎(chǔ)上去擴(kuò)展，所以數(shù)組對(duì)于動(dòng)態(tài)內(nèi)存分配是極為不利的，但是基本的數(shù)據(jù)結(jié)構(gòu)如字符串和線性表就是基于數(shù)組實(shí)現(xiàn)的。
接著簡單看了一下其他幾個(gè)常用拼接方法和索引器，內(nèi)部實(shí)現(xiàn)大致一樣，幾乎都是對(duì)字符數(shù)組的操作邏輯。有興趣大家不妨也看看源碼。
分析到這里，我們可以大膽假設(shè)：StringBuilder內(nèi)部實(shí)現(xiàn)的字符串操作最終是通過字符數(shù)組char[] m_ChunkChars進(jìn)行處理的。想一想也對(duì)啊，如果StringBuildr的實(shí)現(xiàn)是通過String加等于減等于地拼過來接過去那就遜掉了。
不能忽視的是它的擴(kuò)展容量的算法，最關(guān)鍵的就是下面這行代碼：
int num = Math.Max(minBlockCharCount, Math.Min(this.Length, 8000));其實(shí)是非常簡單的數(shù)學(xué)方法，StringBuilder內(nèi)部的MaxChunkSize默認(rèn)為8000，大家可以評(píng)估一下，如果進(jìn)行多次拼接，字符串長度隨機(jī)一點(diǎn)，內(nèi)存分配情況會(huì)怎么樣，8000這個(gè)數(shù)字有沒有道理。據(jù)傳說和GC內(nèi)部算法一樣，framework一些常用類的內(nèi)部實(shí)現(xiàn)也遵循著平衡的設(shè)計(jì)，不知真假。
二、基于Array的可動(dòng)態(tài)擴(kuò)容的線性結(jié)構(gòu)
大家應(yīng)該都非常熟悉，就像StringBuilder一樣，framework中很多集合都有動(dòng)態(tài)擴(kuò)容效果。比如我們熟悉的線性集合ArrayList，泛型List，Queue，Stack等等，這些都是直接基于Array而實(shí)現(xiàn)的。
那么基于Array的集合它們內(nèi)部是如何實(shí)現(xiàn)動(dòng)態(tài)擴(kuò)容的，擴(kuò)容的量是怎么控制的？也許我們?cè)缬卸劊褪莿?dòng)態(tài)擴(kuò)展的容量是上一次已有容量的兩倍，到底是不是這樣的呢？帶著疑問我們挑一個(gè)最常見的集合泛型List<T>分析一下。
和StringBuilder分析法類似，我們也從構(gòu)造函數(shù)和Add方法著手分析。
無參構(gòu)造函數(shù)如下：
public List()
{
this._items = List<T>._emptyArray;
}
_items是個(gè)泛型數(shù)組（private T[] _items;泛型數(shù)組好像不能這么說？），通過構(gòu)造函數(shù)它肯定有默認(rèn)初始容量了,_emptyArray肯定初始化分配了一定空間，猜對(duì)了嗎？_emptyArray定義如下：
private static readonly T[] _emptyArray = new T[0];
看看有一個(gè)參數(shù)的：
public List(int capacity)
{
if (capacity < 0)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
}
this._items = new T[capacity];
}
這回直接給_items new了一個(gè)數(shù)組對(duì)象。
好，再來一個(gè)傳入初始集合的：
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);
}
}
}
到這里估計(jì)大家都看到關(guān)鍵的地方了：每個(gè)構(gòu)造函數(shù)都要對(duì)_items 變量進(jìn)行初始化，而這個(gè)_items 正是一個(gè)數(shù)組（如我們所知，泛型List確實(shí)是基于數(shù)組實(shí)現(xiàn)的）。
再來分析下增刪改查中的增加也就是Add方法：
public void Add(T item)
{
if (this._size == this._items.Length)
{
this.EnsureCapacity(this._size + 1); //擴(kuò)容函數(shù)
}
this._items[this._size++] = item; //通過索引器賦值，添加元素
this._version++;
}
我們目標(biāo)明確，終于找到了擴(kuò)容函數(shù)EnsureCapacity：
private void EnsureCapacity(int min)
{
if (this._items.Length < min)
{
int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2); //容量=當(dāng)前的長度的兩倍
if (num < min)
{
num = min;
}
this.Capacity = num; //當(dāng)前數(shù)組容量賦值
}
}
到這里，我們看到，添加一個(gè)元素的時(shí)候，如果容量沒超過預(yù)分配的數(shù)組空間大小，直接通過下面的索引器賦值：
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++;
}
}
如果新增的項(xiàng)超過了現(xiàn)有數(shù)組的最大容量，通過擴(kuò)容函數(shù)進(jìn)行容量再分配（再new一個(gè)數(shù)組對(duì)象），在函數(shù)EnsureCapacity中，我們看到：
int num = (this._items.Length == 0) ? 4 : (this._items.Length * 2); //容量=當(dāng)前的長度的兩倍這里進(jìn)行了數(shù)組容量的重新計(jì)算，方法很簡單。最重要的是給屬性Capacity賦值：
this.Capacity = num; //當(dāng)前數(shù)組容量賦值這個(gè)屬性的set里面包含了數(shù)組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]; //重新初始化一個(gè)數(shù)組
if (this._size > 0)
{
Array.Copy(this._items, 0, array, 0, this._size);
}
this._items = array; //新數(shù)組指向原數(shù)組，原數(shù)組丟棄
return;
}
this._items = List<T>._emptyArray;
}
}
}
分析到這里我們完全可以通過偽代碼總結(jié)出集合的擴(kuò)容算法：
public void Add(T item)
{
判斷當(dāng)前元素個(gè)數(shù)是否等于它預(yù)設(shè)定的容量
if(等于)
{
重新分配內(nèi)存空間(前一次的空間乘以二)
利用Array.Copy方法把元素復(fù)制到新分配的空間
}
設(shè)置元素的當(dāng)前位置
currentIndex++;
this[currentIndex] = item;
}
也許有人會(huì)問，重新分配內(nèi)存空間時(shí)直接簡單的乘以2會(huì)不會(huì)太草率了，這樣不是容易造成內(nèi)存空間的浪費(fèi)嗎？MS的實(shí)現(xiàn)也不都是非常嚴(yán)謹(jǐn)?shù)穆铮?/P>
確實(shí)，緩沖區(qū)擴(kuò)容的時(shí)候，如數(shù)據(jù)量較大，很明顯會(huì)造成內(nèi)存浪費(fèi)，泛型List提供了一個(gè)方法叫TrimExcess用來解決內(nèi)存浪費(fèi)的問題：
public void TrimExcess()
{
int num = (int)((double)this._items.Length * 0.9); //當(dāng)前數(shù)組空間容量乘以0.9
if (this._size < num)
{
this.Capacity = this._size; //重新設(shè)置數(shù)組空間
}
}
原理也就是一個(gè)簡單的數(shù)學(xué)方法，你在外部調(diào)用一次或多次，它就會(huì)自動(dòng)幫你平衡空間節(jié)省內(nèi)存了。
有一個(gè)非常常用的功能就是判斷元素是否在列表里，方法名就是熟悉的Contains，看代碼果然是O(n)復(fù)雜度：
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果然也是基于數(shù)組的，而且我們現(xiàn)在可以理直氣壯地說我很清楚它的內(nèi)部擴(kuò)容實(shí)現(xiàn)算法。此時(shí)我真想拍著肩膀?qū)ψ约赫f，哥們你辛苦了，太有成就感了，抓緊時(shí)間多想想你喜歡的姑娘吧……我果然又紅光滿面了。
然后，再查看源碼，發(fā)現(xiàn)很多核心方法的實(shí)現(xiàn)都直接對(duì)_items數(shù)組進(jìn)行操作，并多次調(diào)用了Array的靜態(tài)方法，所以我們一定不可小視數(shù)據(jù)結(jié)構(gòu)數(shù)組(Array)。
反匯編查看Array的源碼，發(fā)現(xiàn)增刪改查方法相當(dāng)之豐富，哪位有心人可以挖掘挖掘里面使用了多少種經(jīng)典算法（比如BinarySearch聽說用了二分查找），反正感覺它是被我大大低估了。至少現(xiàn)在我們知道，經(jīng)常使用的常用數(shù)據(jù)結(jié)構(gòu)如StringBuilder、ArrayList，泛型List，Queue，Stack等等都是基于Array實(shí)現(xiàn)的。不要小看了它，隨著framework的發(fā)展，也許未來還會(huì)不斷出現(xiàn)基于Array的新的數(shù)據(jù)結(jié)構(gòu)的出現(xiàn)。
三、基于Array的可動(dòng)態(tài)擴(kuò)容的哈希結(jié)構(gòu)
平時(shí)開發(fā)中經(jīng)常使用的其他的一些數(shù)據(jù)結(jié)構(gòu)如HashTable，泛型Dictionary，HashSet以及線程安全容器ConcurrentDictionary等等也可以動(dòng)態(tài)擴(kuò)容。下面從HashTable源碼入手簡單分析下。
先從無參構(gòu)造函數(shù)開始：
public Hashtable()
: this(0, 1f)
{
}
無參構(gòu)造函數(shù)最終需要調(diào)用的構(gòu)造方法如下：
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; //負(fù)載因子 熟悉又陌生的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; //初始化數(shù)組空間
this.buckets = new Hashtable.bucket[num2]; //原來是bucket結(jié)構(gòu)構(gòu)造的數(shù)組
this.loadsize = (int)(this.loadFactor * (float)num2);
this.isWriterInProgress = false;
}
正如我們所知，哈希函數(shù)的計(jì)算結(jié)果是一個(gè)存儲(chǔ)單位地址，每個(gè)存儲(chǔ)單位稱為桶，而buckets不正是我們要找的存儲(chǔ)散列函數(shù)計(jì)算結(jié)果的哈希桶嗎？原來它也是個(gè)數(shù)組。這里大家看到了嗎？this.buckets原來就是一個(gè)struct結(jié)構(gòu)數(shù)組，心里好像一下子就有底了。
好，接著找動(dòng)態(tài)擴(kuò)容函數(shù)，從Add方法入手吧：
public virtual void Add(object key, object value)
{
this.Insert(key, value, true);
}
跟蹤到Insert方法，代碼一下子變得內(nèi)容豐富，但是我們直接看到了一個(gè)判斷語句：
if (this.count >= this.loadsize)
{
this.expand();
}
上面這個(gè)if判斷一目了然，expand不就是擴(kuò)展的意思嗎？跟進(jìn)去：
private void expand()
{
int prime = HashHelpers.GetPrime(this.buckets.Length * 2); //直接乘以2 好像還有個(gè)輔助調(diào)用獲取素?cái)?shù) HashHelpers.GetPrime
this.rehash(prime); //重新hash
}
有個(gè)rehash函數(shù)，再跟進(jìn)去：
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的引用改變?yōu)樾绿畛涞膎ewBuckets
this.loadsize = (int)(this.loadFactor * (float)newsize);
this.UpdateVersion();
this.isWriterInProgress = false;
Thread.EndCriticalRegion();
}
果然又看到了數(shù)組的重新定義和再賦值：this.buckets = newBuckets;
這不就又回到老路上來了嗎？再查查Array出現(xiàn)的頻率，哈希表很多方法的實(shí)現(xiàn)也還是數(shù)組操作來操作去的。到這里，忍不住想起周星馳電影里的話：打完收功。
但是還沒完，有一個(gè)動(dòng)態(tài)擴(kuò)容容量的計(jì)算問題，是和泛型列表一樣的直接乘以2嗎？在expand函數(shù)里我們看到了下面這一行：
int prime = HashHelpers.GetPrime(this.buckets.Length * 2);
很顯然，乘以2以后還需要一個(gè)輔助函數(shù)HashHelpers.GetPrime（看命名就知道是獲取素?cái)?shù)）的運(yùn)算，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;
}
}
獲取素?cái)?shù)的實(shí)現(xiàn)好像還蠻熟悉的。繼續(xù)跟蹤HashHelpers，發(fā)現(xiàn)它的primes數(shù)組列舉了最小為3，最大為7199369的素?cái)?shù)。如果你的哈希表容量不是特別大，3到7199369的素?cái)?shù)足夠使用了（符合二八原則），否則哈希表擴(kuò)容的時(shí)候需要在2147483647這個(gè)數(shù)字范圍內(nèi)通過HashHelpers.IsPrime來判斷并動(dòng)態(tài)生成素?cái)?shù)。所以簡單地說哈希表擴(kuò)容后的容量是原來的兩倍并不準(zhǔn)確，這個(gè)就和哈希算法對(duì)素?cái)?shù)的要求有直接關(guān)系，在不太精確的情況下我們可以認(rèn)為約等于兩倍。
出于好奇順便查看了一下泛型字典的源碼，它的內(nèi)部實(shí)現(xiàn)包含了buckets和entries兩個(gè)結(jié)構(gòu)數(shù)組，還發(fā)現(xiàn)哈希結(jié)構(gòu)的容器通常內(nèi)部算法果然都比較繞。我猜它們的實(shí)現(xiàn)也不同程度地利用了數(shù)組的特點(diǎn)，說到底應(yīng)該也是基于Array實(shí)現(xiàn)的吧（看到?jīng)]，不知道就算無責(zé)任亂寫）？其他的幾種常見哈希結(jié)構(gòu)的容器還沒有認(rèn)真看，有興趣大家可以直接查看源碼詳細(xì)分析一下，挑典型的一兩個(gè)對(duì)比著看應(yīng)該非常有效果。
歡迎大家暢所欲言說說你所知道的基于Array的其他數(shù)據(jù)結(jié)構(gòu)，這里我就不再班門弄斧貽笑大方了。
思考：拋一個(gè)弱弱的疑問向大家求證：實(shí)現(xiàn)容器的動(dòng)態(tài)特性是不是必須要基于數(shù)組呢，基于數(shù)組的實(shí)現(xiàn)是唯一的方式嗎？
- python實(shí)現(xiàn)bitmap數(shù)據(jù)結(jié)構(gòu)詳解
- java數(shù)據(jù)結(jié)構(gòu)和算法學(xué)習(xí)之漢諾塔示例
- LinkedList學(xué)習(xí)示例模擬堆棧與隊(duì)列數(shù)據(jù)結(jié)構(gòu)
- C數(shù)據(jù)結(jié)構(gòu)之雙鏈表詳細(xì)示例分析
- C數(shù)據(jù)結(jié)構(gòu)之單鏈表詳細(xì)示例分析
- 從數(shù)據(jù)結(jié)構(gòu)的角度分析 for each in 比 for in 快的多
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)- 解析最少換車次數(shù)的問題詳解
- 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-用棧實(shí)現(xiàn)表達(dá)式求值的方法詳解
- C++ 冒泡排序數(shù)據(jù)結(jié)構(gòu)、算法及改進(jìn)算法
- 從數(shù)據(jù)結(jié)構(gòu)分析看：用for each...in 比 for...in 要快些
- C#數(shù)據(jù)結(jié)構(gòu)之循環(huán)鏈表的實(shí)例代碼
- Oracle 11g Release (11.1) 索引底層的數(shù)據(jù)結(jié)構(gòu)
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘五 棧和隊(duì)列
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘四 雙向鏈表
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘三 鏈表
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘二 線性結(jié)構(gòu)
- C#數(shù)據(jù)結(jié)構(gòu)與算法揭秘一
- 數(shù)據(jù)結(jié)構(gòu)順序表操作示例
相關(guān)文章
本文主要介紹兩種方法處理大牛生小牛的問題，第二種效率更高，希望能給大家一個(gè)參考。2016-06-06
Unity Shader相交算法實(shí)現(xiàn)簡易防能量盾
這篇文章主要為大家詳細(xì)介紹了Unity Shader相交算法實(shí)現(xiàn)簡易防能量盾，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
C#連接SQLite數(shù)據(jù)庫并實(shí)現(xiàn)基本操作
本文介紹了SQLite,一個(gè)輕量級(jí)的跨平臺(tái)數(shù)據(jù)庫管理系統(tǒng),以及如何在C#中使用System.Data.SQLite庫進(jìn)行操作,包括創(chuàng)建、修改和查詢數(shù)據(jù)庫,以及使用SQLiteHelper類簡化SQL使用,此外,還提到了DB文件查看工具SQLiteSpy的應(yīng)用,需要的朋友可以參考下2024-12-12
c#調(diào)用qq郵箱smtp發(fā)送郵件修改版代碼分享
c#調(diào)用qq郵箱發(fā)送郵件的方法，網(wǎng)上找到的有錯(cuò)誤，這里修改了一下提供給大家使用2013-12-12
這篇文章主要介紹了C#網(wǎng)頁信息采集方法,實(shí)例匯總了三種常用的方法,是非常實(shí)用的技巧,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了基于C#實(shí)現(xiàn)的敏感字檢測(cè)示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-09-09![Log4Net 日志配置[附帶源碼下載]](http://img.jbzj.com/images/xgimg/bcimg6.png)
這篇文章主要介紹了Log4Net 日志配置[附帶源碼下載],需要的朋友可以參考下2015-05-05
這篇文章主要介紹了c#并行編程示例,大家直接看下面的代碼吧2014-01-01
C#的鋸齒數(shù)組以及C++實(shí)現(xiàn)代碼
鋸齒數(shù)組首先是二維數(shù)組，第一維的維數(shù)是確定的。之所以在C#中能夠出現(xiàn)靈活的鋸齒數(shù)組，是因?yàn)?，C#的數(shù)組是引用類型（本質(zhì)上存放的是指針）。根據(jù)這個(gè)引用類型（指針）的概念，C++中用指針數(shù)組同樣可以實(shí)現(xiàn)2013-09-09
C# Winform 調(diào)用系統(tǒng)接口操作 INI 配置文件的代碼
封裝了一小段代碼, 調(diào)用系統(tǒng)接口, 操作配置文件. 一般用于 .ini 文件, 或者其它鍵值對(duì)格式的配置文件2011-05-05