本篇文章為大家展示了如何進(jìn)行C#中Dictionary的內(nèi)部實(shí)現(xiàn)分析，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比武平網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式武平網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋武平地區(qū)。費(fèi)用合理售后完善，10多年實(shí)體公司更值得信賴。

了解Dictionary的開發(fā)人員都了解，和List相比，字典添加會(huì)慢，但是查找會(huì)比較快，那么Dictionary是如何實(shí)現(xiàn)的呢？

Dictionary的構(gòu)造

下面的代碼我看看Dictionary在構(gòu)造時(shí)都做了什么：

private void Initialize(int capacity)
        {
            int prime = HashHelpers.GetPrime(capacity);
            this.buckets = new int[prime];
            for (int i = 0; i < this.buckets.Length; i++)
            {
                this.buckets[i] = -1;
            }
            this.entries = new Entry<TKey, TValue>[prime];
            this.freeList = -1;
        }

我們看到，Dictionary在構(gòu)造的時(shí)候做了以下幾件事：

1. 初始化一個(gè)this.buckets = new int[prime]

2. 初始化一個(gè)this.entries = new Entry<TKey, TValue>[prime]

3. Bucket和entries的容量都為大于字典容量的一個(gè)最小的質(zhì)數(shù)

其中this.buckets主要用來進(jìn)行Hash碰撞，this.entries用來存儲(chǔ)字典的內(nèi)容，并且標(biāo)識(shí)下一個(gè)元素的位置。

我們以Dictionary<int,string> 為例，來展示一下Dictionary如何添加元素：

首先，我們構(gòu)造一個(gè):

Dictionary<int, string> test = new Dictionary<int, string>(6);

初始化后：

添加元素時(shí)，集合內(nèi)部Bucket和entries的變化

Test.Add(4,”4&Prime;)后：

根據(jù)Hash算法： 4.GetHashCode()%7= 4,因此碰撞到buckets中下標(biāo)為4的槽上，此時(shí)由于Count為0，因此元素放在Entries中第0個(gè)元素上，添加后Count變?yōu)?

Test.Add(11,”11&Prime;)

根據(jù)Hash算法  11.GetHashCode()%7=4,因此再次碰撞到Buckets中下標(biāo)為4的槽上，由于此槽上的值已經(jīng)不為-1，此時(shí)Count=1，因此把這 個(gè)新加的元素放到entries中下標(biāo)為1的數(shù)組中，并且讓Buckets槽指向下標(biāo)為1的entries中，下標(biāo)為1的entry之下下標(biāo)為0的 entries。

Test.Add(18,”18&Prime;)

我們添加18，讓HashCode再次碰撞到Buckets中下標(biāo)為4的槽上，這個(gè)時(shí)候新元素添加到count+1的位置，并且Bucket槽指向 新元素，新元素的Next指向Entries中下標(biāo)為1的元素。此時(shí)你會(huì)發(fā)現(xiàn)所有hashcode相同的元素都形成了一個(gè)鏈表，如果元素碰撞次數(shù)越多，鏈 表越長(zhǎng)。所花費(fèi)的時(shí)間也相對(duì)較多。

Test.Add(19,”19&Prime;)

再次添加元素19，此時(shí)Hash碰撞到另外一個(gè)槽上，但是元素仍然添加到count+1的位置。

刪除元素時(shí)集合內(nèi)部的變化

Test.Remove(4)

我們刪除元素時(shí)，通過一次碰撞，并且沿著鏈表尋找3次，找到key為4的元素所在的位置，刪除當(dāng)前元素。并且把FreeList的位置指向當(dāng)前刪除元素的位置，F(xiàn)reeCount置為1

Test.Remove(18)

刪除Key為18的元素，仍然通過一次碰撞，并且沿著鏈表尋找2次，找到當(dāng)前元素，刪除當(dāng)前元素，并且讓FreeList指向當(dāng)前元素，當(dāng)前元素的Next指向上一個(gè)FreeList元素。

此時(shí)你會(huì)發(fā)現(xiàn)FreeList指向了一個(gè)鏈表，鏈表里面不包含任何元素，F(xiàn)reeCount表示不包含元素的鏈表的長(zhǎng)度。

Test.Add(20,”20&Prime;)

再添加一個(gè)元素，此時(shí)由于FreeList鏈表不為空，因此字典會(huì)優(yōu)先添加到FreeList鏈表所指向的位置，添加后FreeCount減1，F(xiàn)reeList鏈表長(zhǎng)度變?yōu)?

通過以上試驗(yàn)，我們可以發(fā)現(xiàn)Dictionary在添加，刪除元素按照如下方法進(jìn)行：

1. 通過Hash算法來碰撞到指定的Bucket上，碰撞到同一個(gè)Bucket槽上所有數(shù)據(jù)形成一個(gè)單鏈表

2. 默認(rèn)情況Entries槽中的數(shù)據(jù)按照添加順序排列

3. 刪除的數(shù)據(jù)會(huì)形成一個(gè)FreeList的鏈表，添加數(shù)據(jù)的時(shí)候，優(yōu)先向FreeList鏈表中添加數(shù)據(jù)，F(xiàn)reeList為空則按照count依次排列

4. 字典查詢及其的效率取決于碰撞的次數(shù)，這也解釋了為什么Dictionary的查找會(huì)很快。

上述內(nèi)容就是如何進(jìn)行C#中Dictionary的內(nèi)部實(shí)現(xiàn)分析，你們學(xué)到知識(shí)或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識(shí)儲(chǔ)備，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。

網(wǎng)站欄目：如何進(jìn)行C#中Dictionary的內(nèi)部實(shí)現(xiàn)分析
當(dāng)前URL：http://chinadenli.net/article42/goijec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊(cè)、用戶體驗(yàn)、軟件開發(fā)、做網(wǎng)站、網(wǎng)站導(dǎo)航、網(wǎng)站維護(hù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)