欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

解析從源碼分析常見的基于Array的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)擴(kuò)容機(jī)制的詳解

 更新時(shí)間：2013年05月13日 11:01:01   作者：  
本篇文章是對(duì)從源碼分析常見的基于Array的數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)擴(kuò)容機(jī)制進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下

本文的寫作沖動(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)增加元素開銷很小；缺點(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è)方法：

復(fù)制代碼 代碼如下:

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)如下：

復(fù)制代碼 代碼如下:

       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)的：
復(fù)制代碼 代碼如下:

        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)的：
復(fù)制代碼 代碼如下:

      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：
復(fù)制代碼 代碼如下:

     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ù)如下：

復(fù)制代碼 代碼如下:

     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ù)的：

復(fù)制代碼 代碼如下:

        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è)傳入初始集合的：

復(fù)制代碼 代碼如下:

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方法：

復(fù)制代碼 代碼如下:

       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：
復(fù)制代碼 代碼如下:

        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ù)組空間大小，直接通過下面的索引器賦值：
復(fù)制代碼 代碼如下:

      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的操作：

復(fù)制代碼 代碼如下:

    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ò)容算法：
復(fù)制代碼 代碼如下:

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)的問題：

復(fù)制代碼 代碼如下:

       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ù)雜度：

復(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ù)開始：

復(fù)制代碼 代碼如下:

      public Hashtable()
            : this(0, 1f)
        {
        }

無參構(gòu)造函數(shù)最終需要調(diào)用的構(gòu)造方法如下：
復(fù)制代碼 代碼如下:

      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)去：

復(fù)制代碼 代碼如下:

        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代碼如下：

復(fù)制代碼 代碼如下:

 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)是唯一的方式嗎？

相關(guān)文章

  • LRU緩存替換策略及C#實(shí)現(xiàn)方法分享

    LRU緩存替換策略及C#實(shí)現(xiàn)方法分享

    LRU（Least Recently Used）緩存替換策略是一種常用的緩存管理策略，它根據(jù)數(shù)據(jù)最近被訪問的時(shí)間來決定哪些數(shù)據(jù)應(yīng)該被保留在緩存中。本文將介紹LRU緩存替換策略的原理和C#實(shí)現(xiàn)方法。
    2023-04-04
  • C#中類與接口的區(qū)別個(gè)人總結(jié)

    C#中類與接口的區(qū)別個(gè)人總結(jié)

    這篇文章主要介紹了C#中類與接口的區(qū)別個(gè)人總結(jié),本文講解了類與接口的區(qū)別、接口的用處主要體現(xiàn)在下面幾個(gè)方面、一些接口的疑問等內(nèi)容,需要的朋友可以參考下
    2015-06-06
  • C#從畫刷創(chuàng)建畫筆的方法

    C#從畫刷創(chuàng)建畫筆的方法

    這篇文章主要介紹了C#從畫刷創(chuàng)建畫筆的方法,涉及C#圖形繪制的基本技巧,需要的朋友可以參考下
    2015-06-06
  • C#枚舉類型與位域枚舉Enum

    C#枚舉類型與位域枚舉Enum

    這篇文章介紹了C#中的枚舉類型與位域枚舉Enum，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
    2022-05-05
  • 雜談try-catch-finally異常處理

    雜談try-catch-finally異常處理

    這篇文章主要介紹了雜談try-catch-finally異常處理的相關(guān)資料,需要的朋友可以參考下
    2016-01-01
  • C#使用NPOI讀取excel轉(zhuǎn)為DataSet

    C#使用NPOI讀取excel轉(zhuǎn)為DataSet

    這篇文章主要為大家詳細(xì)介紹了C#使用NPOI讀取excel轉(zhuǎn)為DataSet，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2022-02-02
  • 詳解C#壓縮、解壓文件夾/文件(帶密碼)

    詳解C#壓縮、解壓文件夾/文件(帶密碼)

    這篇文章主要給大家介紹了關(guān)于C#壓縮、解壓文件夾/文件(帶密碼)的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-09-09
  • C#實(shí)現(xiàn)String類型和json之間的相互轉(zhuǎn)換功能示例

    C#實(shí)現(xiàn)String類型和json之間的相互轉(zhuǎn)換功能示例

    這篇文章主要介紹了C#實(shí)現(xiàn)String類型和json之間的相互轉(zhuǎn)換功能,涉及C# json格式數(shù)據(jù)的構(gòu)造、轉(zhuǎn)換相關(guān)操作技巧,需要的朋友可以參考下
    2017-09-09
  • C#使用timer定時(shí)在屏幕上輸出信息的方法

    C#使用timer定時(shí)在屏幕上輸出信息的方法

    這篇文章主要介紹了C#使用timer定時(shí)在屏幕上輸出信息的方法,涉及C#中timer定時(shí)器的使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
    2015-03-03
  • C# DataTable的詳細(xì)用法分享

    C# DataTable的詳細(xì)用法分享

    在項(xiàng)目中經(jīng)常用到DataTable,如果DataTable使用得當(dāng)，不僅能使程序簡潔實(shí)用，而且能夠提高性能，達(dá)到事半功倍的效果，現(xiàn)對(duì)DataTable的使用技巧進(jìn)行一下總結(jié)
    2013-11-11

最新評(píng)論