一、什麼是Tu Share

Tushare是一個免費、開源的python財經數據接口包。主要實現對股票等金融數據從數據採集、清洗加工 到 數據存儲的過程，用戶可以免費（部分數據的下載有積分限制）的通過它提供的財經接口獲取股票交易、期貨等財經信息，功能非常強大。該接口和直接到各財經網站爬數據相比，最大的優勢就是快，去傳統財經網站爬數據，好多關鍵性的股票信息只能一隻股一隻股爬，而Tu Share的API，一個調用可以獲得一天的全部數據，速度差了好幾個數量級。另外一方面各財經網站的接口的API沒有對外文檔化，隨時可能變化，而Tu Share的API有正式的文檔化相對比較穩定。

二、如何註冊

該網站使用積分制來控制數據的訪問權限，如果想要訪問數據，先要到下面這個網址完成註冊，https://tushare.pro/register。註冊完成后，可以需要到個人主頁中拷貝Token，這個Token會在以後的訪問中用到，步驟如下

1、登錄成功后，點擊右上角->個人主頁

2、 在“用戶中心”中點擊“接口TOKEN”

 

3、 可以點擊右側複製按鈕複製token

三、Http API說明

Tushare HTTP數據獲取的方式，採用了post的機制，通過提交JSON body參數，就可以獲得您想要的數據。具體參數說明如下：

輸入參數

api_name：接口名稱，比如stock_basic

token ：用戶唯一標識，可通過登錄pro網站獲取

params：接口參數，如daily接口中start_date和end_date

fields：字段列表，用於接口獲取指定的字段，以逗號分隔，如”open,high,low,close”

輸出參數

code： 接口返回碼，2002表示權限問題。

msg：錯誤信息，比如“系統內部錯誤”，“沒有權限”等

data：數據，data里包含fields和items字段，分別為字段和數據內容

四、c#(.net core)實現

1、在Visual Studio中安裝下面幾個包：Microsoft.Extensions.Http、Newtonsoft.Json

2、封裝方法，實現對REST web service的調用

public interface IHttpClientUtility
{
     string HttpClientPost(string url, object datajson);
}

public class HttpClientUtility : IHttpClientUtility
    {
        

        public HttpClientUtility()
        {
            
        }
        public  string HttpClientPost(string url, object datajson)
        {
            using (HttpClient httpClient = new HttpClient()) //http對象
            {
                httpClient.DefaultRequestHeaders.Accept.Clear();
                httpClient.DefaultRequestHeaders.Accept.Add(new MediaTypeWithQualityHeaderValue("application/json"));
                httpClient.Timeout = new TimeSpan(0, 0, 5);
                //轉為鏈接需要的格式
                HttpContent httpContent = new JsonContent(datajson);
                //請求
                HttpResponseMessage response = httpClient.PostAsync(url, httpContent).Result;
                if (response.IsSuccessStatusCode)
                {
                    Task<string> t = response.Content.ReadAsStringAsync();
                    return t.Result;
                }
                throw new Exception("調用失敗");
            }
                                                                       
        }
    }

 

    public class JsonContent : StringContent
    {
        public JsonContent(object value)
            : base(JsonConvert.SerializeObject(value), Encoding.UTF8,
                "application/json")
        {
        }

        public JsonContent(object value, string mediaType)
            : base(JsonConvert.SerializeObject(value), Encoding.UTF8, mediaType)
        {
        }
    }

3、封裝對Tu Share API的調用

public  class TuShareUtility 
    {
        private IHttpClientUtility _httpClientUtility;
        private string _url = "http://api.waditu.com/";
        
        public TuShareUtility(IHttpClientUtility httpClientUtility)
        {
            _httpClientUtility = httpClientUtility;
        }

        /// <summary>
        /// 調用TuShare API
        /// </summary>
        /// <param name="apiName"></param>
        /// <param name="parmaMap"></param>
        /// <param name="fields"></param>
        /// <returns></returns>
        public  DataTable GetData(string apiName,Dictionary<string,string> parmaMap,params string[] fields)
        {
            var tuShareParamObj=new TuShareParamObj(){ ApiName = apiName ,Params = parmaMap,Fields = string.Join(",",fields)};
            //做Http調用
            var result=_httpClientUtility.HttpClientPost(_url, tuShareParamObj);
            //將返回結果序列化成對象
            var desResult=JsonConvert.DeserializeObject<TuShareResult>(result);
            //如果調用失敗，拋出異常
            if(!string.IsNullOrEmpty(desResult.Msg))
                throw new Exception(desResult.Msg);
            //返回結果分成兩部分，一部分是列頭信息，另一部分是數據本身，用這兩部分數據可以構建DataTable
            DataTable dt = new DataTable();
            foreach (var dataField in desResult.Data.Fields)
            {
                dt.Columns.Add(dataField);
            }

            foreach (var dataItemRow in desResult.Data.Items)
            {
                var newdr=dt.NewRow();
                for (int i=0;i< dataItemRow.Length;i++)
                {
                    newdr[i] = dataItemRow[i];
                }

                dt.Rows.Add(newdr);
            }
            return dt;
        }

        private class TuShareParamObj
        {
            [JsonProperty("api_name")]
            public string ApiName { get; set; }

            [JsonProperty("token")]
            public string Token { get; } = "****************";//你的Token

            [JsonProperty("params")]
            public Dictionary<string, string> Params { get; set; }

            [JsonProperty("fields")]
            public string Fields { get; set; }
        }

        private class TuShareData
        {
            [JsonProperty("fields")]
            public string[] Fields { get; set; }

            [JsonProperty("items")]
            public string[][] Items { get; set; }
        }

        private class TuShareResult
        {
            [JsonProperty("code")]
            public string Code { get; set; }

            [JsonProperty("msg")]
            public string Msg { get; set; }

            [JsonProperty("data")]
            public TuShareData Data { get; set; }
        }
    }

4、調用示例

獲得日線行情，整個過程1秒左右，返回6月24日，股票相關交易信息，代碼如下，(該網站的其它接口定義可以到https://tushare.pro/document/2查看)

var tuShareUtility=new TuShareUtility();
Dictionary<string, string> p = new Dictionary<string, string>();
p["trade_date"] = "20200624";
var table = tuShareUtility.GetData("daily", p, "");

返回如下結果

返回字段說明

名稱	類型	描述
ts_code	str	股票代碼
trade_date	str	交易日期
open	float	開盤價
high	float	最高價
low	float	最低價
close	float	收盤價
pre_close	float	昨收價
change	float	漲跌額
pct_chg	float	漲跌幅 （未復權，如果是復權請用 通用行情接口 ）
vol	float	成交量 （手）
amount	float	成交額 （千元）

 

 

 

  本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

最近在寫一個多模塊的SpringBoot項目，基於過程總了一些總結，故把SpringBoot多個模塊的項目創建記錄下來。

首先，先建立一個父工程：

（1）在IDEA工具欄選擇File->New->Project

（2）選擇Spring Initializr,默認選擇Default，然後點擊Next:    

（3）在輸入框填寫以下截圖內容，點擊Next

（4）直接點Next，無需選擇

（5）直接點擊Finish完成創建

（6）按照以上步驟，可以生成以下的項目目錄結構：

（7）這時把沒用的.mvn目錄，src目錄，mvnw還有mvnw.cmd都刪除，最終只保留.gitignore和pom.xml，若是web項目，可在該pom.xml里添加以下依賴：

1 <!--web特徵-->
2 <dependency>
3     <groupId>org.springframework.boot</groupId>
4     <artifactId>spring-boot-starter-web</artifactId>
5     <version>2.3.1.RELEASE</version>
6 </dependency>

最終得到以下的父結構目錄：

 

以上是創建父模塊，下面創建子模塊：

（1）在父模塊的根目錄fte上點右鍵，在彈出的框里選擇New->Module

（2）選擇Maven，點擊Next

（3）填寫以下內容，點擊Next

（4）填寫Module,點擊Finish

（5）同理添加fte-controller,fte-dao,fte-service,fte-web,最終得到以下的目錄結構：

（6）增加模塊之間的依賴：

controller層添加以下依賴：

 1 <dependencies>
 2     <dependency>
 3         <groupId>com.example</groupId>
 4         <artifactId>fte-common</artifactId>
 5         <version>0.0.1-SNAPSHOT</version>
 6     </dependency>
 7 
 8     <dependency>
 9         <groupId>com.example</groupId>
10         <artifactId>fte-dao</artifactId>
11         <version>0.0.1-SNAPSHOT</version>
12     </dependency>
13 
14     <dependency>
15         <groupId>com.example</groupId>
16         <artifactId>fte-service</artifactId>
17         <version>0.0.1-SNAPSHOT</version>
18     </dependency>
19 </dependencies>

service層添加以下依賴：

1 <dependencies>
2     <dependency>
3         <groupId>com.example</groupId>
4         <artifactId>fte-dao</artifactId>
5         <version>0.0.1-SNAPSHOT</version>
6     </dependency>
7 </dependencies>

（7）測試

在fte-controller創建com.zhu.fte.web包，增加以下兩個類：

fteWebApplication類：

 1 package com.zhu.fte.web;
 2 
 3 import org.springframework.boot.SpringApplication;
 4 import org.springframework.boot.autoconfigure.SpringBootApplication;
 5 
 6 @SpringBootApplication
 7 public class fteWebApplication {
 8     public static void main(String[] args) {
 9         SpringApplication.run(fteWebApplication.class,args);
10     }
11 }

DemoController類

 1 package java.com.zhu.fte.web;
 2 
 3 import org.springframework.web.bind.annotation.GetMapping;
 4 import org.springframework.web.bind.annotation.RequestMapping;
 5 import org.springframework.web.bind.annotation.RestController;
 6 
 7 @RestController
 8 @RequestMapping("demo")
 9 public class DemoController {
10 
11     @GetMapping("test")
12     public String test(){
13         return "hello world";
14     }
15 
16 }

運行發現出現錯誤：

出現錯誤：

[ERROR] Failed to execute goal org.apache.maven.plugins:maven-surefire-plugin:2.22.2:test (default-test) on project fte-common: Execution default-test of goal org.apache.maven.plugins:maven-surefire-plugin:2.22.2:test failed: Plugin org.apache.maven.plugins:maven-surefire-plugin:2.22.2 or one of its dependencies could not be resolved: Could not transfer artifact junit:junit:jar:4.12 from/to central (https://repo.maven.apache.org/maven2): Connect to repo.maven.apache.org:443 [repo.maven.apache.org/151.101.52.215] failed: Connection timed out: connect -> [Help 1]

把缺少的org.apache.maven.plugins手動放到父工程的pom.xml里

 1 <build>
 2    <plugins>
 3       <plugin>
 4          <groupId>org.apache.maven.plugins</groupId>
 5          <artifactId>maven-clean-plugin</artifactId>
 6          <version>2.5</version>
 7       </plugin>
 8       <plugin>
 9          <groupId>org.apache.maven.plugins</groupId>
10          <artifactId>maven-source-plugin</artifactId>
11          <version>2.2</version>
12       </plugin>
13       <plugin>
14          <groupId>org.apache.maven.plugins</groupId>
15          <artifactId>maven-compiler-plugin</artifactId>
16          <version>3.0</version>
17          <configuration>
18             <source>1.8</source>
19             <target>1.8</target>
20             <encoding>${file.encoding}</encoding>
21             <!--編譯的時候方法不改變方法參數名稱，用於支持使用反射獲取方法參數名稱-->
22             <compilerArgument>-parameters</compilerArgument>
23          </configuration>
24       </plugin>
25       <plugin>
26          <groupId>org.apache.maven.plugins</groupId>
27          <artifactId>maven-install-plugin</artifactId>
28          <version>2.4</version>
29       </plugin>
30       <plugin>
31          <groupId>org.apache.maven.plugins</groupId>
32          <artifactId>maven-jar-plugin</artifactId>
33          <version>2.4</version>
34          <configuration>
35             <archive>
36                <manifest>
37                   <addDefaultImplementationEntries>true
38                   </addDefaultImplementationEntries>
39                </manifest>
40             </archive>
41          </configuration>
42       </plugin>
43 
44       <plugin>
45          <groupId>org.apache.maven.plugins</groupId>
46          <artifactId>maven-surefire-plugin</artifactId>
47          <version>2.13</version>
48          <configuration>
49             <argLine>-Xmx512M -Dfile.encoding=${file.encoding}</argLine>
50          </configuration>
51       </plugin>
52    </plugins>
53 </build>

運行fteWebApplication類里的main方法，默認端口為8080，訪問http://localhost:8080/demo/test，正常出現以下情況：

 

按照以上步驟，就可以初步建立SpringBoot多模塊的項目，下一章將基於這個基礎搭建Mybatis以及其逆向工程。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

阻止谷歌下記住密碼

當我們將input框的類型設置為密碼框的時候，就會出現下面這種效果，不僅樣式不統一，有的時候，密碼框的上面並不是用戶名，而是其他的內容，也會被強制显示為用戶名：

 首先需要解決樣式問題：

 #app input:-webkit-autofill {
    -webkit-text-fill-color: #fff !important;
    -webkit-box-shadow: none !important;
    background-color: transparent;
    background-image: none;
    transition: background-color 999999s ease-in-out, color 999999s ease-in-out;
  }

 其次，阻止谷歌自帶的記住密碼：

 回車重定向

 單個el-input獲得焦點時，點擊鍵盤迴車，會觸發路由重定向。

解決方法：@submit.native.preven t阻止表單默認事件

 日期時間框的默認值在IE無法清除

element的日期框添加默認值后，在ie下，默認的清空按鈕無法清空默認日期值：

 

 

 數據應該是已經清空了，但是DOM沒有刷新，所以需要強制刷新DOM：

 

 自定義表頭

<template>
    <div>
        <el-table-column
            v-for="(item, idx) in list"
            :key="idx"
            v-bind="item" :show-overflow-tooltip="true">
            <tHeader
                v-if="item.children"
                :list="item.children">
            </tHeader>
        </el-table-column>
    </div>
</template>
<script>
export default {
    name: 'tHeader',
    props: [
        'list'
    ],
    methods: {
        repairEleSortBug() {
            this.list.unshift(this.list.pop());
        }
    },
    
    created() {
            //修復elementUI排序倒置的bug（將數組最後一個放到第一個）
        this.repairEleSortBug();
    }
};
</script>

 

 

 

 對象監聽

在vue中可以通過監聽一個變量的值變化觸發相應事件，但是當需要監聽的變量是個複雜對象時，通常在外出是監聽不到對象裏面值的變化，這時就需要深度監聽：

 

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

0.前言

通過前面幾篇，我們了解到了如何實現項目的基本架構：數據源、路由設置、加密以及身份驗證。那麼在實現的時候，我們還會遇到這樣的一個問題：當我們業務類和數據源越來越多的時候，我們無法通過普通的構造對象的方法為每個實例進行賦值。同時，傳統意義上的賦值遇到底層切換或者其他修改的時候，就需要修改大量的代碼，對改變不友好。為了改變這種現狀，我們基於面向接口編程，然後使用一些DI功能和IOC框架。

1. IOC和DI

先來給大家解釋幾個概念，IOC全稱Inversion of Control，翻譯過來就是控制反轉，是面向對象編程的一種設計原則，用來降低代碼之間的耦合度。所謂的控制反轉簡單來講就是將類中屬性或者其他參數的初始化交給其他方處理，而不是直接使用構造函數。

public class Demo1
{
}

public class Demo2
{
	public Demo1 demo;
}

對於以上簡單示例代碼中，在Demo2類中持有了一個Demo1的實例。如果按照之前的情況來講，我們會通過以下方法為demo賦值：

// 方法一
public Demo1 demo = new Demo1();
// 方法二
public Demo2()
{
    demo = new Demo1();
}

這時候，如果Demo1變成下面的樣子：

public class Demo1
{
    public Demo1(Demo3 demo3)
    {
        // 隱藏
    }
}
public class Demo3
{
}

那麼，如果Demo2 沒有持有一個Demo3的實例對象，這時候創建Demo1的時候就需要額外構造一個Demo3。如果Demo3需要持有另外一個類的對象，那麼Demo2中就需要多創建一個對象。最後就會發現這樣就陷入了一個構造“地獄”（我發明的詞，指這種為了一個對象卻得構造一大堆其他類型的對象）。

實際上，對於Demo2並不關心Demo1的實例對象是如何獲取的，甚至都不關心它是不是Demo1的子類或者接口實現類。我在示例中使用了類，但這裏可以同步替換成Interface，替換之後，Demo2在調用Demo1的時候，還需要知道Demo1有實現類，以及實現類的信息。

為了解決這個問題，一些高明的程序員們提出了將對象的創建這一過程交給第三方去操作，而不是調用類來創建。於是乎，上述代碼就變成了：

public class Demo2
{
    public Demo1 Demo {get;set;}
    public Demo2(Demo1 demo)
    {
        Demo = demo;
    }
}

似乎並沒有什麼變化？對於Demo2來說，Demo2從此不再負責Demo1的創建，這個步驟交由Demo2的調用方去創建，Demo2從此從負責維護Demo1這個對象的大麻煩中解脫了。

但實際上構造地獄的問題還是沒有解決，只不過是通過IOC的設計將這一步后移了。這時候，那些大神們想了想，不如開發一個框架這些實體對象吧。所以就出現了很多IOC框架：AutoFac、Sping.net、Unity等。

說到IOC就不得不提一下DI（Dependency Injection)依賴注入。所謂的依賴注入就是屬性對應實例通過構造函數或者使用屬性由第三方進行賦值。也就是最後Demo2的示例代碼中的寫法。

早期IOC和DI是指一種技術，後來開始確定這是不同的描述。IOC描述的是一種設計模式，而DI是一種行為。

2. 使用asp.net core的默認IOC

在之前的ASP.NET 框架中，微軟並沒有提供默認的IOC支持。在最新的asp.net core中微軟提供了一套IOC支持，該支持在命名空間：

Microsoft.Extensions.DependencyInjection

里，在代碼中引用即可。

主要通過以下幾組方法實現：

public static IServiceCollection AddScoped<TService>(this IServiceCollection services) where TService : class;
public static IServiceCollection AddSingleton<TService>(this IServiceCollection services) where TService : class;
public static IServiceCollection AddTransient<TService>(this IServiceCollection services) where TService : class;

這裏只列出了這三組方法的一種重載版本。

這三組方法分別代表三種生命周期：

• AddScored 表示對象的生命周期為整個Request請求
• AddTransient 表示每次從服務容器進行請求時創建的，適合輕量級、 無狀態的服務
• AddSingleton 表示該對象在第一次從服務容器請求后獲取，之後就不會再次初始化了

這裏每組方法只介紹了一個版本，但實際上每個方法都有以下幾個版本：

public static IServiceCollection AddXXX<TService>(this IServiceCollection services) where TService : class;
public static IServiceCollection AddXXX(this IServiceCollection services, Type serviceType, Type implementationType);
public static IServiceCollection AddXXX(this IServiceCollection services, Type serviceType, Func<IServiceProvider, object> implementationFactory);
public static IServiceCollection AddXXX<TService, TImplementation>(this IServiceCollection services)
            where TService : class
            where TImplementation : class, TService;
public static IServiceCollection AddXXX(this IServiceCollection services, Type serviceType);
public static IServiceCollection AddXXX<TService>(this IServiceCollection services, Func<IServiceProvider, TService> implementationFactory) where TService : class;
public static IServiceCollection AddXXX<TService, TImplementation>(this IServiceCollection services, Func<IServiceProvider, TImplementation> implementationFactory)
            where TService : class
            where TImplementation : class, TService;

其中：implementationFactory 表示通過一個Provider實現TService/TImplementation 的工廠方法。當方法指定了泛型的時候，會自動依據泛型參數獲取要注入的類型信息，如果沒有使用泛型則必須手動傳入參數類型。

asp.net core如果使用依賴注入的話，需要在Startup方法中設置，具體內容可以參照以下：

public void ConfigureServices(IServiceCollection services)
{
    //省略其他代碼
    services.AddScoped<ISysUserAuthRepository,SysUserAuthRepository>();
}

asp.net core 為DbContext提供了不同的IOC支持，AddDbContext：

public static IServiceCollection AddDbContext<TContext>(
      this IServiceCollection serviceCollection,
      Action<DbContextOptionsBuilder> optionsAction = null,
      ServiceLifetime contextLifetime = ServiceLifetime.Scoped,
      ServiceLifetime optionsLifetime = ServiceLifetime.Scoped)
      where TContext : DbContext;

使用方法如下：

services.AddDbContext<DefaultContext>();

3. AutoFac 使用

理論上，asp.net core的IOC已經足夠好了，但是依舊原諒我的貪婪。如果有二三百個業務類需要我來設置的話，我寧願不使用IOC。因為那配置起來就是一場極其痛苦的過程。不過，可喜可賀的是AutoFac可以讓我免收這部分的困擾。

這裏簡單介紹一下如何使用AutoFac作為IOC管理：

cd Web  # 切換目錄到Web項目
dotnet package add Autofac.Extensions.DependencyInjection # 添加 AutoFac的引用

因為asp.net core 版本3更改了一些邏輯，AutoFac的引用方式發生了改變，現在不介紹之前版本的內容，以3為主。使用AutoFac需要先在 Program類里設置以下代碼：

public static IHostBuilder CreateHostBuilder(string[] args) =>
    		Host.CreateDefaultBuilder(args)
    		.UseServiceProviderFactory(new AutofacServiceProviderFactory()) // 添加這行代碼
    		.ConfigureWebHostDefaults(webBuilder =>
			{
                webBuilder.UseStartup<Startup>();
            });

在Program類里啟用AutoFac的一個Service提供工廠類。然後在Startup類里添加如下方法：

public void ConfigureContainer(ContainerBuilder builder)
{
    builder.RegisterType<DefaultContext>().As<DbContext>()
                .WithParameter("connectStr","Data Source=./demo.db")
                .InstancePerLifetimeScope();
            

    builder.RegisterAssemblyTypes(Assembly.Load("Web"))
        .Where(t => t.BaseType.FullName.Contains("Filter"))
        .AsSelf();

    builder.RegisterAssemblyTypes(Assembly.Load("Domain"),
                    Assembly.Load("Domain.Implements"), Assembly.Load("Service"), Assembly.Load("Service.Implements"))
                .AsSelf()
                .AsImplementedInterfaces()
                .InstancePerLifetimeScope()
                .PropertiesAutowired();
}

修改：

public void ConfigureServices(IServiceCollection services)
{
    services.AddControllersWithViews(options =>
            {
                options.Filters.Add<UnitOfWorkFilterAttribute>();
            }).AddControllersAsServices();// 這行新增
    // 省略其他
}

4. 總結

這一篇簡單介紹了如何在Asp.net Core中啟用IOC支持，並提供了兩種方式，可以說是各有優劣。小夥伴們根據自己需要選擇。後續會為大家詳細深入AutoFac之類IOC框架的核心秘密。

更多內容煩請關注我的博客《高先生小屋》

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

Dictionary<TKey,TValue>是日常.net開發中最常用的數據類型之一，基本上遇到鍵值對類型的數據時第一反應就是使用這種散列表。散列表特別適合快速查找操作，查找的效率是常數階O(1)。那麼為什麼這種數據類型的查找效率能夠這麼高效？它背後的數據類型是如何支撐這種查找效率的？它在使用過程中有沒有什麼局限性？一起來探究下這個數據類型的奧秘吧。

本文內容針對的是.Net Framework 4.5.1的代碼實現，在其他.Net版本中或多或少都會有些差異，但是基本的原理還是相同的。

本文的內容主要分為三個部分，第一部分是從代碼的角度來分析並以圖文並茂的方式通俗的解釋Dictionary如何解決的散列衝突並實現高效的數據插入和查找。第二部分名為“眼見為實”，由於第一部分是從代碼層面分析Dictionary的實現，側重於理論分析，因此第二部分使用windbg直接分析內存結構，跟第一部分的理論分析相互印證，加深對於這種數據類型的深入理解。最後是從數據結構的時間複雜度的角度進行分析並提出了幾條實踐建議。

本文內容：

• 第一部分 代碼分析
  • 散列衝突
  • Dictionary圖文解析
  • Dictionary的初始化
  • 添加第四個元素
• 第二部分 眼見為實
  • 添加第一個元素后的內存結構
  • 添加第四個元素后的內存結構
• 第三部分
  • 時間複雜度分析
  • 實踐建議

散列衝突

提到散列表，就不能不提散列衝突。由於哈希算法被計算的數據是無限的，而計算后的結果範圍有限，因此總會存在不同的數據經過計算后得到的值相同，這就是哈希衝突。（兩個不同的數據計算后的結果一樣）。散列衝突的解決方案有好幾個，比如開放尋址法、鏈式尋址法。

Dictionary使用的是鏈式尋址法，也叫做拉鏈法。拉鏈法的基本思想是將散列值相同的數據存在同一個鏈表中，如果有散列值相同的元素，則加到鏈表的頭部。同樣道理，在查找元素的時候，先計算散列值，然後在對應散列值的鏈表中查找目標元素。

用圖來表達鏈式尋址法的思想：

Dictionary<TKey,TValue>的內部數據結構

Dictionary的內部存儲數據主要是依賴了兩個數組，分別是int[] buckets和Entry[] entries。其中buckets是Dictionary所有操作的入口，類似於上文中解說拉鏈法所用的圖中的那個豎著的數據結構。Entry是一個結構體，用於封裝所有的元素並且增加了next字段用於構建鏈表數據結構。為了便於理解，下文中截取了一段相關的源代碼並增加了註釋。

//數據在Dictionary<TKey,TValue>的存儲形式，所有的鍵值對在Dictionary<TKey,TValue>都是被包裝成一個個的Entry保存在內存中
private struct Entry {
    public int hashCode;    // 散列計算結果的低31位數，默認值為-1
    public int next;        // 下一個Entry的索引值，鏈表的最後一個Entry的next為-1
    public TKey key;        // Entry對象的Key對應於傳入的TKey
    public TValue value;    // Entry對象的Value對應與傳入的TValue
}

private int[] buckets;      //hashCode的桶，是查找所有Entry的第一級數據結構
private Entry[] entries;    //保存真正的數據

下文中以Dictionary<int,string>為例，分析Dictionary在使用過程中內部數據的組織方式。

Dictionary初始化

初始化代碼：

Dictionary<int, string> dictionary = new Dictionary<int, string>();

Dictionary的初始化時，buckets和entries的長度都是0。

添加一個元素

dictionary.Add(1, "xyxy");

向Dictionary中添加這個新元素大致經過了7個步驟：

1. 首先判斷數組長度是否需要擴容（原長度為0，需要擴容）；
2. 對於數組進行擴容，分別創建長度為3的bucket數組和entries數組（使用大於原數組長度2倍的第一個素數作為新的數組長度）；
3. 整數1的hashcode為1；
4. 取低31位數值為1（計算公式：hashcode & 0x7FFFFFFF=1）；
5. 該key的hashcode落到bucket下標為1的位置（計算公式：hashCode % buckets.Length=1）；
6. 將hashcode、key、value包裝起來（封裝到entries數組下標為0的結構體中）；
7. 設置bucket[1]的值為0（因為新元素被封裝到了entries數組下標為0的位置）；

當向Dictionary中添加一個元素后，內部數據結構如下圖（為了便於理解，圖上將bucket和entries中各個鏈表頭結點用線標出了關聯關係）：

添加第二個元素

dictionary.Add(7, "xyxy");

向Dictionary中添加這個元素大致經過了6個步驟：

1. 計算7的hashcode是7；
2. 取低31位數值為7（計算公式：hashcode & 0x7FFFFFFF=1）；
3. 該key的hashcode落到bucket下標為1的位置（計算公式：hashCode % buckets.Length=1）；
4. 將hashcode、key、value包裝起來（封裝到entries數組下標為1的結構體中，跟步驟3計算得到的1沒有關係，只是因為entries數組下標為1的元素是空着的所以放在這裏）；
5. 原bucket[1]為0，所以設置當前結構體的Entry.next為0；
6. 設置bucket[1]為1（因為鏈表的頭部節點位於entries數組下標為1的位置）

當向Dictionary中添加第二個元素后，內部數據結構是這樣的：

添加第三個元素

dictionary.Add(2, "xyxy");

向Dictionary添加這個元素經過了如下5個步驟：

1. 整數2計算的hashcode是2；
2. hashcode取低31位數值為2（計算公式：hashcode & 0x7FFFFFFF=2）；
3. 該key的hashcode落到bucket下標為2的位置（計算公式：hashCode % buckets.Length=2）；
4. 將hashcode、key、value包裝起來（封裝到entries數組下標為2的結構體中，到此entries的數組就存滿了）；
5. 原bucket[2]上為-1，所以bucket[2]節點下並沒有對應鏈表，設置當前結構體的Entry.next為-1；
6. 設置bucket[2]為2（因為鏈表的頭部節點位於entries數組下標為2的位置）

當向Dictionary中添加第三個元素后，內部數據結構：

添加第四個元素

dictionary.Add(4, "xyxy");

通過前面幾個操作可以看出，當前數據結構中entries數組中的元素已滿，如果再添加元素的話，會發生怎樣的變化呢？

假如再對於dictionary添加一個元素，原來申請的內存空間肯定是不夠用的，必須對於當前數據結構進行擴容，然後在擴容的基礎上再執行添加元素的操作。那麼在解釋這個Add方法原理的時候，分為兩個場景分別進行：數組擴容和元素添加。

數組擴容

在發現數組容量不夠的時候，Dictionary首先執行擴容操作，擴容的規則與該數據類型首次初始化的規則相同，即使用大於原數組長度2倍的第一個素數7作為新數組的長度（3*2=6，大於6的第一個素數是7）。

擴容步驟：

1. 新申請一個容量為7的數組，並將原數組的元素拷貝至新數組（代碼：Array.Copy(entries, 0, newEntries, 0, count);）
2. 重新計算原Dictionary中的元素的hashCode在bucket中的位置（注意新的bucket數組中數值的變化）；
3. 重新計算鏈表（注意entries數組中結構體的next值的變化）；

擴容完成后Dictionary的內容數據結構：

添加元素

當前已經完成了entries和bucket數組的擴容，有了充裕的空間來存儲新的元素，所以可以在新的數據結構的基礎上繼續添加元素。

當向Dictionary中添加第四個元素后，內部數據結構是這樣的：

添加這個新的元素的步驟：

1. 整數4計算的hashcode是4；
2. hashcode取低31位數值為4（計算公式：hashcode & 0x7FFFFFFF=4）；
3. 該key的hashcode落到bucket下標為4的位置（計算公式：hashCode % buckets.Length=4）；
4. 將hashcode、key、value包裝起來；（封裝到entries數組下標為3的結構體中)；
5. 原bucket[4]上為-1，所以當前節點下並沒有鏈表，設置當前結構體的Entry.next為-1；
6. 設置bucket[4]為3（因為鏈表的頭部節點位於entries數組下標為3的位置）

眼見為實

畢竟本文的主題是圖文並茂分析Dictionary<Tkey,Tvalue>的原理，雖然已經從代碼層面和理論層面分析了Dictionary<Tkey,Tvalue>的實現，但是如果能夠分析這個數據類型的實際內存數據結果，可以獲得更直觀的感受並且對於這個數據類型能夠有更加深入的認識。由於篇幅的限制，無法將Dictionary<Tkey,Tvalue>的所有操作場景結果都進行內存分析，那麼本文中精選有代表性的兩個場景進行分析：一是該數據類型初始化后添加第一個元素的內存結構，二是該數據類型進行第一次擴容后的數據結構。

Dictionary添加第一個元素后的內存結構

執行代碼：

Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
Console.Read();

打開windbg附加到該進程(由於使用的是控制台應用程序，當前線程是0號線程，因此如果附加進程后默認的不是0號線程時執行~0s切換到0號線程),執行!clrstack -l查看當前線程及線程上使用的所有變量：

0:000> !clrstack -l
OS Thread Id: 0x48b8 (0)
        Child SP               IP Call Site
0000006de697e998 00007ffab577c134 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e998 00007ffa96abc9c8 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e960 00007ffa96abc9c8 *** ERROR: Module load completed but symbols could not be loaded for C:\WINDOWS\assembly\NativeImages_v4.0.30319_64\mscorlib\5c1b7b73113a6f079ae59ad2eb210951\mscorlib.ni.dll
DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)

0000006de697ea40 00007ffa972d39ec System.IO.__ConsoleStream.ReadFileNative(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte[], Int32, Int32, Boolean, Boolean, Int32 ByRef)
    LOCALS:
        <no data>
        <no data>
        <no data>
        <no data>
        <no data>
        <no data>

0000006de697ead0 00007ffa972d38f5 System.IO.__ConsoleStream.Read(Byte[], Int32, Int32)
    LOCALS:
        <no data>
        <no data>

0000006de697eb30 00007ffa96a882d4 System.IO.StreamReader.ReadBuffer()
    LOCALS:
        <no data>
        <no data>

0000006de697eb80 00007ffa97275f23 System.IO.StreamReader.Read()
    LOCALS:
        <no data>

0000006de697ebb0 00007ffa9747a2fd System.IO.TextReader+SyncTextReader.Read()

0000006de697ec10 00007ffa97272698 System.Console.Read()

0000006de697ec40 00007ffa38670909 ConsoleTest.DictionaryDebug.Main(System.String[])
    LOCALS:
        0x0000006de697ec70 = 0x00000215680d2dd8

0000006de697ee88 00007ffa97ba6913 [GCFrame: 0000006de697ee88] 

通過對於線程堆棧的分析很容易看出當前線程上使用了一個局部變量，地址為：0x000001d86c972dd8，使用!do命令查看該變量的內容：

0:000> !do 0x00000215680d2dd8
Name:        System.Collections.Generic.Dictionary`2[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513328
EEClass:     00007ffa9662f610
Size:        80(0x50) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
              MT    Field   Offset                 Type VT     Attr            Value Name
00007ffa964a8538  4001887        8       System.Int32[]  0 instance 00000215680d2ee8 buckets
00007ffa976c4dc0  4001888       10 ...non, mscorlib]][]  0 instance 00000215680d2f10 entries
00007ffa964a85a0  4001889       38         System.Int32  1 instance                1 count
00007ffa964a85a0  400188a       3c         System.Int32  1 instance                1 version
00007ffa964a85a0  400188b       40         System.Int32  1 instance               -1 freeList
00007ffa964a85a0  400188c       44         System.Int32  1 instance                0 freeCount
00007ffa96519630  400188d       18 ...Int32, mscorlib]]  0 instance 00000215680d2ed0 comparer
00007ffa964c6ad0  400188e       20 ...Canon, mscorlib]]  0 instance 0000000000000000 keys
00007ffa977214e0  400188f       28 ...Canon, mscorlib]]  0 instance 0000000000000000 values
00007ffa964a5dd8  4001890       30        System.Object  0 instance 0000000000000000 _syncRoot

從內存結構來看，該變量中就是我們查找的Dic存在buckets、entries、count、version等字段，其中buckets和entries在上文中已經有多次提及，也是本文的分析重點。既然要眼見為實，那麼buckets和entries這兩個數組的內容到底是什麼樣的呢？這兩個都是數組，一個是int數組，另一個是結構體數組，對於這兩個內容分別使用!da命令查看其內容：

首先是buckets的內容：

0:000> !da -start 0 -details 00000215680d2ee8 
Name:        System.Int32[]
MethodTable: 00007ffa964a8538
EEClass:     00007ffa966160e8
Size:        36(0x24) bytes
Array:       Rank 1, Number of elements 3, Type Int32
Element Methodtable: 00007ffa964a85a0
[0] 00000215680d2ef8
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[1] 00000215680d2efc
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                    0     m_value
[2] 00000215680d2f00
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                   -1     m_value

當前buckets中有三個值，分別是：-1、0和-1，其中-1是數組初始化后的默認值，而下錶為1的位置的值0則是上文中添加dic.Add(1, "xyxy");這個指令的結果，代表其對應的鏈表首節點在entries數組中下標為0的位置，那麼entries數組中的數值是什麼樣子的呢？

0:000> !da -start 0 -details 00000215680d2f10 
Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass:     00007ffa9662d1f0
Size:        96(0x60) bytes
Array:       Rank 1, Number of elements 3, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000215680d2f20
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    1     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    1     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000215680d2db0     value
[1] 00000215680d2f38
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[2] 00000215680d2f50
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value

通過對於entries數組的分析可以看出，這個數組也有三個值，其中下標為0的位置已經填入相關內容，比如hashCode為1，key為1，其中value的內容是一個內存地址：000001d86c972db0，這個地址指向的就是字符串對象，它的內容是xyxy，使用!do指令來看下具體內容：

0:000> !do  00000215680d2db0
Name:        System.String
MethodTable: 00007ffcc6b359c0
EEClass:     00007ffcc6b12ec0
Size:        34(0x22) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
String:      xyxy
Fields:
              MT    Field   Offset                 Type VT     Attr            Value Name
00007ffcc6b385a0  4000283        8         System.Int32  1 instance                4 m_stringLength
00007ffcc6b36838  4000284        c          System.Char  1 instance               78 m_firstChar
00007ffcc6b359c0  4000288       e0        System.String  0   shared           static Empty

簡要分析擴容后的內存結構

此次執行的代碼為：

Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
dic.Add(7, "xyxy");
dic.Add(2, "xyxy");
dic.Add(4, "xyxy");
Console.Read();

同樣採取附加進程的方式分析這段代碼執行后的內存結構，本章節中忽略掉如何查找Dictionary變量地址的部分，直接分析buckets數組和entries數組的內容。

首先是buckets數組的內存結構：

0:000> !da -start 0 -details 0000019a471a54f8 
Name:        System.Int32[]
MethodTable: 00007ffcc6b38538
EEClass:     00007ffcc6ca60e8
Size:        52(0x34) bytes
Array:       Rank 1, Number of elements 7, Type Int32
Element Methodtable: 00007ffcc6b385a0
[0] 0000019a471a5508
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    1     m_value
[1] 0000019a471a550c
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    0     m_value
[2] 0000019a471a5510
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    2     m_value
[3] 0000019a471a5514
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[4] 0000019a471a5518
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    3     m_value
[5] 0000019a471a551c
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[6] 0000019a471a5520
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value

然後是entries的內存結構：

0:000> !da -start 0 -details 00000237effb2fa8 
Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass:     00007ffa9662d1f0
Size:        192(0xc0) bytes
Array:       Rank 1, Number of elements 7, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000237effb2fb8
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    1     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    1     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[1] 00000237effb2fd0
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    7     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    7     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[2] 00000237effb2fe8
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    2     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    2     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[3] 00000237effb3000
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    4     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    4     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[4] 00000237effb3018
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[5] 00000237effb3030
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[6] 00000237effb3048
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value

從內存的結構來看，擴容后bucket數組中使用了下標為0、1、2和4這四個位置，entries中使用了0~3存儲了示例中添加的數據，符合前文中理論分析的結果，兩者相互之間具有良好的印證關係。

時間複雜度分析

時間複雜度表達的是數據結構操作數據的時候所消耗的時間隨着數據集規模的增長的變化趨勢。常用的指標有最好情況時間複雜度、最壞情況時間複雜度和均攤時間複雜度。那麼對於Dictionary<Tkey,TValue>來說，插入和查找過程中這些時間複雜度分別是什麼樣的呢？

最好情況時間複雜度：對於查找來說最好的是元素處於鏈表的頭部，查找效率不會隨着數據規模的增加而增加，因此該複雜度為常量階複雜度，即O(1)；插入操作最理想的情況是數組中有空餘的空間，不需要進行擴容操作，此時時間複雜度也是常量階的，即O(1)；

最壞情況時間複雜度：對於插入來說，比較耗時的操作場景是需要順着鏈表查找符合條件的元素，鏈表越長，查找時間越長（下文稱為場景一）；而對於插入來說最壞的情況是數組長度不足，需要動態擴容並重新組織鏈表結構（下文稱為場景二）；

場景一中時間複雜度隨着鏈表長度的增加而增加，但是Dictionary中規定鏈表的最大長度為100，如果有長度超過100的鏈表就需要擴容並調整鏈表結構，所以順着鏈表查找數據不會隨着數據規模的增長而增長，最大時間複雜度是固定的，因此時間複雜度還是常量階複雜度，即O(1);

場景二中時間複雜度隨着數組中元素的數量增加而增加，如果原來的數組元素為n個，那麼擴容時需要將這n個元素拷貝到新的數組中並計算其在新鏈表中的位置，因此該操作的時間複雜度是隨着數組的長度n的增加而增加的，屬於線性階時間複雜度，即O(n)。

綜合場景一和場景二的分析結果得出最壞情況時間複雜度出現在數據擴容過程中，時間複雜度為O(n)。

最好情況時間複雜度和最壞情況時間複雜度都過於極端，只能描述最好的情況和最壞的情況，那麼在使用過程中如何評價數據結構在大部分情況下的時間複雜度？通常對於複雜的數據結構可以使用均攤時間複雜度來評價這個指標。均攤時間複雜度適用於對於一個數據進行連續操作，大部分情況下時間複雜度都很低，只有個別情況下時間複雜度較高的場景。這些操作存在前後連貫性，這種情況下將較高的複雜度攤派到之前的操作中，一般均攤時間複雜度就相當於最好情況時間複雜度。

通過前面的分析可以看出Dictionary恰好就符合使用均攤時間複雜度分析的場景。以插入操作為例，假設預申請的entries數組長度為n，在第n+1次插入數據時必然會遇到一次數組擴容導致的時間消耗較高的場景。將這次較為複雜的操作的時間均攤到之前的n次操作后，每次操作時間的複雜度也是常量階的，因此Dictionary插入數據時均攤時間複雜度也是O(1)。

實踐建議

首先，Dictionary這種類型適合用於對於數據檢索有明顯目的性的場景，比如讀寫比例比較高的場景。其次，如果有大數據量的場景，最好能夠提前聲明容量，避免多次分配內存帶來的額外的時間和空間上的消耗。因為不進行擴容的場景，插入和查找效率都是常量階O(1)，在引起擴容的情況下，時間複雜度是線性階O(n)。如果僅僅是為了存儲數據，使用Dictionary並不合適，因為它相對於List<T>具有更加複雜的數據結構，這樣會帶來額外的空間上面的消耗。雖然Dictionary<TKey,TValue>的TKey是個任意類型的，但是除非是對於判斷對象是否相等有特殊的要求，否則不建議直接使用自定義類作為Tkey。

總結

C#中的Dictionary<TKey,TValue>是藉助於散列函數構建的高性能數據結構，Dictionary解決散列衝突的方式是使用鏈表來保存散列值存在衝突的節點，俗稱拉鏈法。本文中通過圖文並茂的方式幫助理解Dictionary添加元素和擴容過程這兩個典型的應用場景，在理論分析之後使用windbg分析了內存中的實際結構，以此加深對於這種數據類型的深入理解。隨後在此基礎上分析了Dictionary的時間複雜度。Dictionary的最好情況時間複雜度是O(1)，最壞情況複雜度是O(n)，均攤時間複雜度是O(1)，Dictionary在大多數情況下都是常量階時間複雜度，在內部數組自動擴容過程中會產生明顯的性能下降，因此在實際實踐過程中最好在聲明新對象的時候能夠預估容量，儘力避免數組自動擴容導致的性能下降。

參考資料

• Dictionary<TKey,TValue>源代碼(.net framework4.8版本)
• .NET中Dictionary<TKey, TValue>淺析
• 解決hash衝突的三個方法
• 算法複雜度分析（下）：最好、最壞、平均、均攤等時間複雜度概述

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準