dictionary_dictionary 转换类型 - CSDN
dictionary 订阅
Dictionary 展开全文
Dictionary
信息
操作系统
未知
开发语言
开源协议
未知
Dictionary
Comes in handy when you quickly want to find the meaning of a word. 已更新 2008 年 08 月 9 日
收起全文
精华内容
参与话题
  • C#中Dictionary的用法

    千次阅读 2019-03-02 18:01:48
    一、Dictionary简介 在C#中,Dictionary提供快速的基于键值的元素查找。他的结构是这样的:Dictionary<[key], [value]> ,当你有很多元素的时候可以使用它。它包含在System.Collections.Generic名空间...

    一、Dictionary简介

    在C#中,Dictionary提供快速的基于键值的元素查找。他的结构是这样的:Dictionary<[key], [value]> ,当你有很多元素的时候可以使用它。它包含在System.Collections.Generic名空间中。在使用前,你必须声明它的键类型和值类型。

    1、从一组键(Key)到一组值(Value)的映射,每一个添加项都是由一个值及其相关连的键组成

    2、任何键都必须是唯一的

    3、键不能为空引用null(VB中的Nothing),若值为引用类型,则可以为空值

    4、Key和Value可以是任何类型(string,int,custom class 等)

     

    二、Dictionary常用用法

    以 key 的类型为 int , value的类型为string 为例

     1、创建及初始化
     Dictionary<int,string>myDictionary=newDictionary<int,string>();
     
     2、添加元素
    myDictionary.Add(1,"C#");
    myDictionary.Add(2,"C++");
    myDictionary.Add(3,"ASP.NET");
    myDictionary.Add(4,"MVC");
     
     3、通过Key查找元素
    if(myDictionary.ContainsKey(1))
    {
    Console.WriteLine("Key:{0},Value:{1}","1", myDictionary[1]);
     }
     
     4、通过KeyValuePair遍历元素
    foreach(KeyValuePair<int,string>kvp in myDictionary)
    ...{
    Console.WriteLine("Key = {0}, Value = {1}",kvp.Key, kvp.Value);
    }
     
    5、仅遍历键 Keys 属性
    Dictionary<int,string>.KeyCollection keyCol=myDictionary.Keys;
    foreach(intkeyinkeyCol)
    ...{
    Console.WriteLine("Key = {0}", key);
    }
     
    6、仅遍历值 Valus属性
    Dictionary<int,string>.ValueCollection valueCol=myDictionary.Values;
    foreach(stringvalueinvalueCol)
    ...{
    Console.WriteLine("Value = {0}", value);
    }
     
    7、通过Remove方法移除指定的键值
    myDictionary.Remove(1);
    if(myDictionary.ContainsKey(1))
    ...{
    Console.WriteLine("Key:{0},Value:{1}","1", myDictionary[1]);
    }
    else
    {
    Console.WriteLine("不存在 Key : 1"); 

     

    三、其它常见属性和方法的说明:
     
      Comparer:           获取用于确定字典中的键是否相等的 IEqualityComparer。
      Count:                  获取包含在 Dictionary中的键/值对的数目。
      Item:                    获取或设置与指定的键相关联的值。
      Keys:                   获取包含 Dictionary中的键的集合。
      Values:                获取包含 Dictionary中的值的集合。
      Add:                    将指定的键和值添加到字典中。
      Clear:                  从 Dictionary中移除所有的键和值。
      ContainsKey:      确定 Dictionary是否包含指定的键。
      ContainsValue:   确定 Dictionary是否包含特定值。             
      GetEnumerator:  返回循环访问 Dictionary的枚举数。
      GetType:             获取当前实例的 Type。 (从 Object 继承。)
      Remove:             从 Dictionary中移除所指定的键的值。
      ToString:             返回表示当前 Object的 String。 (从 Object 继承。)
      TryGetValue:      获取与指定的键相关联的值。

    注意:本内容来自:https://jingyan.baidu.com/article/9989c7460ab872f648ecfeed.html

     

    展开全文
  • 要使用Dictionary集合,需要导入C#泛型命名空间  System.Collections.Generic(程序集:mscorlib) 步骤阅读 2  Dictionary的描述 1、从一组键(Key)到一组值(Value)的映射,每一个添加项都是由一...
    1.  要使用Dictionary集合,需要导入C#泛型命名空间

       System.Collections.Generic(程序集:mscorlib)

      步骤阅读

    2. 2

       Dictionary的描述

      1、从一组键(Key)到一组值(Value)的映射,每一个添加项都是由一个值及其相关连的键组成

      2、任何键都必须是唯一的

      3、键不能为空引用null(VB中的Nothing),若值为引用类型,则可以为空值

      4、Key和Value可以是任何类型(string,int,custom class 等)

       

      步骤阅读

    3. 3

       Dictionary常用用法:以 key 的类型为 int , value的类型为string 为例

       

       1、创建及初始化

       Dictionary<int,string>myDictionary=newDictionary<int,string>();

       

       2、添加元素

      myDictionary.Add(1,"C#");

      myDictionary.Add(2,"C++");

      myDictionary.Add(3,"ASP.NET");

      myDictionary.Add(4,"MVC");

       

       3、通过Key查找元素

      if(myDictionary.ContainsKey(1))

      {

      Console.WriteLine("Key:{0},Value:{1}","1", myDictionary[1]);

       }

       

       4、通过KeyValuePair遍历元素

      foreach(KeyValuePair<int,string>kvp in myDictionary)

      ...{

      Console.WriteLine("Key = {0}, Value = {1}",kvp.Key, kvp.Value);

      }

       

      5、仅遍历键 Keys 属性

      Dictionary<int,string>.KeyCollection keyCol=myDictionary.Keys;

      foreach(intkeyinkeyCol)

      ...{

      Console.WriteLine("Key = {0}", key);

      }

       

      6、仅遍历值 Valus属性

      Dictionary<int,string>.ValueCollection valueCol=myDictionary.Values;

      foreach(stringvalueinvalueCol)

      ...{

      Console.WriteLine("Value = {0}", value);

      }

       

      7、通过Remove方法移除指定的键值

      myDictionary.Remove(1);

      if(myDictionary.ContainsKey(1))

      ...{

        Console.WriteLine("Key:{0},Value:{1}","1", myDictionary[1]);

      }

      else

      {

      Console.WriteLine("不存在 Key : 1"); 

       }

      步骤阅读

    4. 4

      其它常见属性和方法的说明:

       

        Comparer:           获取用于确定字典中的键是否相等的 IEqualityComparer。

        Count:                  获取包含在 Dictionary中的键/值对的数目。

        Item:                    获取或设置与指定的键相关联的值。

        Keys:                   获取包含 Dictionary中的键的集合。

        Values:                获取包含 Dictionary中的值的集合。

        Add:                    将指定的键和值添加到字典中。

        Clear:                  从 Dictionary中移除所有的键和值。

        ContainsKey:      确定 Dictionary是否包含指定的键。

        ContainsValue:   确定 Dictionary是否包含特定值。             

        GetEnumerator:  返回循环访问 Dictionary的枚举数。

        GetType:             获取当前实例的 Type。 (从 Object 继承。)

        Remove:             从 Dictionary中移除所指定的键的值。

        ToString:             返回表示当前 Object的 String。 (从 Object 继承。)

        TryGetValue:      获取与指定的键相关联的值。

     

    1、用法1: 常规用

      增加键值对之前需要判断是否存在该键,如果已经存在该键而且不判断,将抛出异常。所以这样每次都要进行判断,很麻烦,在备注里使用了一个扩展方法

    public static void DicSample1()
    {
     
        Dictionary<String, String> pList = new Dictionary<String, String>();
        try
        {
            if (pList.ContainsKey("Item1") == false)
            {
                pList.Add("Item1", "ZheJiang");
            }
            if (pList.ContainsKey("Item2")== false)
            {
                pList.Add("Item2", "ShangHai");
            }
            else
            {
                pList["Item2"] = "ShangHai";
            }
            if (pList.ContainsKey("Item3") == false)
            {
                pList.Add("Item3", "BeiJiang");
            }
             
        }
        catch (System.Exception e)
        {
            Console.WriteLine("Error: {0}", e.Message);
        }
       
     
        //判断是否存在相应的key并显示
        if (pList.ContainsKey("Item1"))
        {
            Console.WriteLine("Output: " + pList["Item1"]);
        }
     
        //遍历Key
        foreach (var key in pList.Keys)
        {
            Console.WriteLine("Output Key: {0}", key);
        }
     
        //遍历Value
        foreach (String value in pList.Values)
        {
            Console.WriteLine("Output Value: {0}", value);
        }
        //遍历Key和Value
        foreach (var dic in pList)
        {
            Console.WriteLine("Output Key : {0}, Value : {1} ", dic.Key, dic.Value);
        }
    } 

     

    2、用法2:Dictionary的Value为一个数组

    /// <summary>
    /// Dictionary的Value为一个数组
    /// </summary>
     public static void DicSample2()
     {
         Dictionary<String, String[]> dic = new Dictionary<String, String[]>();
         String[] ZheJiang =  { "Huzhou", "HangZhou", "TaiZhou" };
         String[] ShangHai = { "Budong", "Buxi" };
         dic.Add("ZJ", ZheJiang);
         dic.Add("SH", ShangHai);
         Console.WriteLine("Output :" + dic["ZJ"][0]);
     }

    3、用法3: Dictionary的Value为一个类

    //Dictionary的Value为一个类
    public static void DicSample3()
     {
         Dictionary<String, Student> stuList = new Dictionary<String, Student>();
         Student stu = null;
         for (int i = 0; i < 3; i++ )
         {
             stu = new Student();
             stu.Name = i.ToString();
             stu.Name = "StuName" + i.ToString();
             stuList.Add(i.ToString(), stu);
         }
     
         foreach (var student in stuList)
         {
             Console.WriteLine("Output : Key {0}, Num : {1}, Name {2}", student.Key, student.Value.Name, student.Value.Name);
         }
     }
       
      
    Student类:
    public class Student
    {
        public String Num { get; set; }
        public String Name { get; set; }
    }

     4 备注:Dictionary的扩展方法使用

    /// <summary>
    /// Dictionary的扩展方法使用
    /// </summary>
     public static void DicSample4()
     {
         //1)普通调用
         Dictionary<int, String> dict = new Dictionary<int, String>();
         DictionaryExtensionMethodClass.TryAdd(dict, 1, "ZhangSan");
         DictionaryExtensionMethodClass.TryAdd(dict, 2, "WangWu");
         DictionaryExtensionMethodClass.AddOrPeplace(dict, 3, "WangWu");
         DictionaryExtensionMethodClass.AddOrPeplace(dict, 3, "ZhangWu");
         DictionaryExtensionMethodClass.TryAdd(dict, 2, "LiSi");
     
         //2)TryAdd 和 AddOrReplace 这两个方法具有较强自我描述能力,用起来很省心,而且也简单:
         dict.AddOrPeplace(20, "Orange");
         dict.TryAdd(21, "Banana");
         dict.TryAdd(22, "apple");
     
         //3)像Linq或jQuery一样连起来写  
         dict.TryAdd(10, "Bob")
             .TryAdd(11, "Tom")
             .AddOrPeplace(12, "Jom");
     
         //4) 获取值
         String F = "Ba";
         dict.TryGetValue(31, out F);
         Console.WriteLine("F : {0}",F);
     
         foreach (var dic in dict)
         {
             Console.WriteLine("Output : Key : {0}, Value : {1}", dic.Key, dic.Value);
         }
         //5)下面是使用GetValue获取值
         var v1 = dict.GetValue(111,null);
         var v2 = dict.GetValue(10,"abc");
     
         //6)批量添加
         var dict1 = new Dictionary<int,int>();
         dict1.AddOrPeplace(3, 3);
         dict1.AddOrPeplace(5, 5);
     
         var dict2 = new Dictionary<int, int>();
         dict2.AddOrPeplace(1, 1);
         dict2.AddOrPeplace(4, 4);
         dict2.AddRange(dict1, false);
     }
       
      扩展方法所在的类
    public static class DictionaryExtensionMethodClass
    {
        /// <summary>
        /// 尝试将键和值添加到字典中:如果不存在,才添加;存在,不添加也不抛导常
        /// </summary>
        public static Dictionary<TKey, TValue> TryAdd<TKey, TValue>(this Dictionary<TKey, TValue> dict, TKey key, TValue value)
        {
            if (dict.ContainsKey(key) == false)
                dict.Add(key, value);
            return dict;
        }
     
        /// <summary>
        /// 将键和值添加或替换到字典中:如果不存在,则添加;存在,则替换
        /// </summary>
        public static Dictionary<TKey, TValue> AddOrPeplace<TKey, TValue>(this Dictionary<TKey, TValue> dict, TKey key, TValue value)
        {
            dict[key] = value;
            return dict;
        }
     
        /// <summary>
        /// 获取与指定的键相关联的值,如果没有则返回输入的默认值
        /// </summary>
        public static TValue GetValue<TKey, TValue>(this Dictionary<TKey, TValue> dict, TKey key, TValue defaultValue)
        {
            return dict.ContainsKey(key)?dict[key] : defaultValue;
        }
     
        /// <summary>
        /// 向字典中批量添加键值对
        /// </summary>
        /// <param name="replaceExisted">如果已存在,是否替换</param>
        public static Dictionary<TKey, TValue> AddRange<TKey, TValue>(this Dictionary<TKey, TValue> dict, IEnumerable<KeyValuePair<TKey, TValue>> values, bool replaceExisted)
        {
            foreach (var item in values)
            {
                if (dict.ContainsKey(item.Key) == false || replaceExisted)
                    dict[item.Key] = item.Value;
            }
            return dict;
        }
     
     
    }

     

    使用方法

        //定义
        Dictionary<string, string> openWith = new Dictionary<string, string>();

     

        //添加元素
        openWith.Add("txt", "notepad.exe");
        openWith.Add("bmp", "paint.exe");
        openWith.Add("dib", "paint.exe");
        openWith.Add("rtf", "wordpad.exe");

     

        //取值
        Console.WriteLine("For key = \"rtf\", value = {0}.", openWith["rtf"]);

     

        //更改值
        openWith["rtf"] = "winword.exe";
        Console.WriteLine("For key = \"rtf\", value = {0}.", openWith["rtf"]);

     

        //遍历key
        foreach (string key in openWith.Keys)
        {
            Console.WriteLine("Key = {0}", key);
        }

     

     

        //遍历value
        foreach (string value in openWith.Values)
        {
            Console.WriteLine("value = {0}", value);
        }
    
        //遍历value, Second Method
        Dictionary<string, string>.ValueCollection valueColl = openWith.Values;
        foreach (string s in valueColl)
        {
            Console.WriteLine("Second Method, Value = {0}", s);
        }

     

    //遍历字典 foreach (KeyValuePair<string, string> kvp in openWith) { Console.WriteLine("Key = {0}, Value = {1}", kvp.Key, kvp.Value); }

     

     

        //添加存在的元素
        try
        {
            openWith.Add("txt", "winword.exe");
        }
        catch (ArgumentException)
        {
            Console.WriteLine("An element with Key = \"txt\" already exists.");
        }

     

     

     

        //删除元素
        openWith.Remove("doc");
        if (!openWith.ContainsKey("doc"))
        {
            Console.WriteLine("Key \"doc\" is not found.");
        }

     

     

        //判断键存在
        if (openWith.ContainsKey("bmp")) // True 
        {
            Console.WriteLine("An element with Key = \"bmp\" exists.");
        }

     

    参数为其它类型

        //参数为其它类型 
        Dictionary<int, string[]> OtherType = new Dictionary<int, string[]>();
        OtherType.Add(1, "1,11,111".Split(','));
        OtherType.Add(2, "2,22,222".Split(','));
        Console.WriteLine(OtherType[1][2]);

     

    参数为自定义类型

    首先定义类

        class DouCube
        {
            public int Code { get { return _Code; } set { _Code = value; } } private int _Code;
            public string Page { get { return _Page; } set { _Page = value; } } private string _Page;
        } 

    然后

     

        //声明并添加元素
        Dictionary<int, DouCube> MyType = new Dictionary<int, DouCube>();
        for (int i = 1; i <= 9; i++)
        {
            DouCube element = new DouCube();
            element.Code = i * 100;
            element.Page = "http://www.doucube.com/" + i.ToString() + ".html";
            MyType.Add(i, element);
        }

     

        //遍历元素
        foreach (KeyValuePair<int, DouCube> kvp in MyType)
        {
            Console.WriteLine("Index {0} Code:{1} Page:{2}", kvp.Key, kvp.Value.Code, kvp.Value.Page);
        } 

     

     

    常用属性

        名称    说明
        Comparer     获取用于确定字典中的键是否相等的 IEqualityComparer<T>。
        Count        获取包含在 Dictionary<TKey, TValue> 中的键/值对的数目。
        Item         获取或设置与指定的键相关联的值。
        Keys         获取包含 Dictionary<TKey, TValue> 中的键的集合。
        Values       获取包含 Dictionary<TKey, TValue> 中的值的集合。

    常用方法
        名称    说明
        Add                 将指定的键和值添加到字典中。
        Clear               从 Dictionary<TKey, TValue> 中移除所有的键和值。
        ContainsKey         确定 Dictionary<TKey, TValue> 是否包含指定的键。
        ContainsValue       确定 Dictionary<TKey, TValue> 是否包含特定值。
        Equals(Object)      确定指定的 Object 是否等于当前的 Object。 (继承自 Object。)
        Finalize            允许对象在“垃圾回收”回收之前尝试释放资源并执行其他清理操作。 (继承自 Object。)
        GetEnumerator       返回循环访问 Dictionary<TKey, TValue> 的枚举器。
        GetHashCode         用作特定类型的哈希函数。 (继承自 Object。)
        GetObjectData       实现 System.Runtime.Serialization.ISerializable 接口,并返回序列化 Dictionary<TKey, TValue> 实例所需的数据。
        GetType             获取当前实例的 Type。 (继承自 Object。)
        MemberwiseClone     创建当前 Object 的浅表副本。 (继承自 Object。)
        OnDeserialization    实现 System.Runtime.Serialization.ISerializable 接口,并在完成反序列化之后引发反序列化事件。
        Remove              从 Dictionary<TKey, TValue> 中移除所指定的键的值。
        ToString            返回表示当前对象的字符串。 (继承自 Object。)
        TryGetValue         获取与指定的键相关联的值。

    展开全文
  • Dictionary基本用法

    千次阅读 2019-01-28 11:24:35
    C#中字典Dictionary的用法 各位看官如果在此博客中没有找到自己碰到问题的答案,可联系博主,进行更新哦 1.创建Dictionary Dictionary&amp;amp;lt;int, string&amp;amp;gt; dic = new Dictionary&amp;...

    C#中字典Dictionary的用法

    1.创建Dictionary
    Dictionary<int, string> dic = new Dictionary<int, string>();
    
    2.Dictionary添加元素
    //dic.Add(Key,Value);
    dic.Add(1, "张三");
    dic.Add(2, "李四");
    dic.Add(3, "王五");
    dic.Add(4, "李六");
    dic.Add(5, "赵七");
    dic[6] = "斗帝";//public TValue this[TKey key] { get; set; }
    

    3.遍历

    //遍历Key和Value
    for (int i = 0; i < dic.Count; i++)
    	Console.WriteLine($"Key:{dic.Keys.ToArray()[i]},Value:{dic.Values.ToArray()[i]}");
    foreach(KeyValuePair<int, string> kvp in dic)
    	Console.WriteLine($"Key:{kvp.Key},Value:{kvp.Value}");
    //遍历Key
    foreach(var key in dic.Keys)
    	Console.WriteLine($"Key:{key}");
    //遍历Value
    foreach(var value in dic.Values)
    	Console.WriteLine($"Value:{value}");    
    

    4.根据Key值取Value

    //确定key在字典集中存在
    string value = dic[1];
    //不确定key是否存在字典集当中
    value = dic.FirstOrDefault(d=>d.key == 1).Value;
    

    5.根据Value值取Key

    //lambada表达式
    int key = dic.FirstOrDefault(d => d.Value == "李四").Key;
    //linq to object
    key = (from query in dic.AsEnumerable()
           where query.Value == "王五"
           select new 
           { 
           		query.Key 
           }
           ).Select(d => d.Key).ToList().FirstOrDefault();
    

    6.判断Key是否存在

    bool keyBool = false;
    keyBool = dic.Keys.Contain(key);
    keyBool = dic.ContainsKey(key);
    

    7.判断Value是否存在

    bool valueBool = false;
    valueBool = dic.Values.Contain(key);
    valueBool = dic.ContainsValue(key);
    

    8.移除元素

    //移除单个元素
    dic.Remove(key);
    //移除所有
    dic.Clear();
    
    展开全文
  • 浅析C# Dictionary实现原理

    千次阅读 多人点赞 2019-03-04 11:15:25
    浅析C# Dictionary实现原理(转载https://flycode.co/archives/225519) ... 三、Dictionary实现 1. Entry结构体 2. 其它关键私有变量 3. Dictionary – Add操作 4. Dictionary – Find...

    浅析C# Dictionary实现原理(转载https://flycode.co/archives/225519

    目录



    一、前言

    本篇文章配图以及文字其实整理出来很久了,但是由于各种各样的原因推迟到现在才发出来,还有之前立Flag的《多线程编程》的笔记也都已经写好了,只是说还比较糙,需要找个时间整理一下才能和大家见面。

    对于C#中的Dictionary类相信大家都不陌生,这是一个Collection(集合)类型,可以通过Key/Value(键值对的形式来存放数据;该类最大的优点就是它查找元素的时间复杂度接近O(1),实际项目中常被用来做一些数据的本地缓存,提升整体效率。

    那么是什么样的设计能使得Dictionary类能实现O(1)的时间复杂度呢?那就是本篇文章想和大家讨论的东西;这些都是个人的一些理解和观点,如有表述不清楚、错误之处,请大家批评指正,共同进步。

    二、理论知识

    对于Dictionary的实现原理,其中有两个关键的算法,一个是Hash算法,一个是用于应对Hash碰撞冲突解决算法。

    1、Hash算法

    Hash算法是一种数字摘要算法,它能将不定长度的二进制数据集给映射到一个较短的二进制长度数据集,常见的MD5算法就是一种Hash算法,通过MD5算法可对任何数据生成数字摘要。而实现了Hash算法的函数我们叫她Hash函数。Hash函数有以下几点特征。

    1. 相同的数据进行Hash运算,得到的结果一定相同。HashFunc(key1) == HashFunc(key1)
    2. 不同的数据进行Hash运算,其结果也可能会相同,(Hash会产生碰撞)。key1 != key2 => HashFunc(key1) == HashFunc(key2).
    3. Hash运算时不可逆的,不能由key获取原始的数据。key1 => hashCode但是hashCode ==> key1

    下图就是Hash函数的一个简单说明,任意长度的数据通过HashFunc映射到一个较短的数据集中。

    1548491108167

    关于Hash碰撞下图很清晰的就解释了,可从图中得知Sandra Dee 和 John Smith通过hash运算后都落到了02的位置,产生了碰撞和冲突。
    1548485331574
    常见的构造Hash函数的算法有以下几种。

    1. 直接寻址法:取keyword或keyword的某个线性函数值为散列地址。即H(key)=key或H(key) = a•key + b,当中a和b为常数(这样的散列函数叫做自身函数)

    2. 数字分析法:分析一组数据,比方一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体同样,这种话,出现冲突的几率就会非常大,可是我们发现年月日的后几位表示月份和详细日期的数字区别非常大,假设用后面的数字来构成散列地址,则冲突的几率会明显减少。因此数字分析法就是找出数字的规律,尽可能利用这些数据来构造冲突几率较低的散列地址。

    3. 平方取中法:取keyword平方后的中间几位作为散列地址。

    4. 折叠法:将keyword切割成位数同样的几部分,最后一部分位数能够不同,然后取这几部分的叠加和(去除进位)作为散列地址。

    5. 随机数法:选择一随机函数,取keyword的随机值作为散列地址,通经常使用于keyword长度不同的场合。

    6. 除留余数法:取keyword被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅能够对keyword直接取模,也可在折叠、平方取中等运算之后取模。对p的选择非常重要,一般取素数或m,若p选的不好,容易产生碰撞.

    2、Hash桶算法

    说到Hash算法大家就会想到Hash表,一个Key通过Hash函数运算后可快速的得到hashCode,通过hashCode的映射可直接Get到Value,但是hashCode一般取值都是非常大的,经常是2^32以上,不可能对每个hashCode都指定一个映射。

    因为这样的一个问题,所以人们就将生成的HashCode以分段的形式来映射,把每一段称之为一个Bucket(桶),一般常见的Hash桶就是直接对结果取余。

    假设将生成的hashCode可能取值有2^32个,然后将其切分成一段一段,使用8个桶来映射,那么就可以通过bucketIndex = HashFunc(key1) % 8这样一个算法来确定这个hashCode映射到具体的哪个桶中。

    大家可以看出来,通过hash桶这种形式来进行映射,所以会加剧hash的冲突。

    3、解决冲突算法

    对于一个hash算法,不可避免的会产生冲突,那么产生冲突以后如何处理,是一个很关键的地方,目前常见的冲突解决算法有拉链法(Dictionary实现采用的)、开放定址法、再Hash法、公共溢出分区法,本文只介绍拉链法与再Hash法,对于其它算法感兴趣的同学可参考文章最后的参考文献。

    1. 拉链法:这种方法的思路是将产生冲突的元素建立一个单链表,并将头指针地址存储至Hash表对应桶的位置。这样定位到Hash表桶的位置后可通过遍历单链表的形式来查找元素。

    2. 再Hash法:顾名思义就是将key使用其它的Hash函数再次Hash,直到找到不冲突的位置为止。

    对于拉链法有一张图来描述,通过在冲突位置建立单链表,来解决冲突。

    1548485607652

    三、Dictionary实现

    Dictionary实现我们主要对照源码来解析,目前对照源码的版本是.Net Framwork 4.7。地址可戳一戳这个链接 源码地址:Link

    这一章节中主要介绍Dictionary中几个比较关键的类和对象,然后跟着代码来走一遍插入、删除和扩容的流程,相信大家就能理解它的设计原理。

    1. Entry结构体

    首先我们引入Entry这样一个结构体,它的定义如下代码所示。这是Dictionary种存放数据的最小单位,调用Add(Key,Value)方法添加的元素都会被封装在这样的一个结构体中。

    private struct Entry {
        public int hashCode;    // 除符号位以外的31位hashCode值, 如果该Entry没有被使用,那么为-1
        public int next;        // 下一个元素的下标索引,如果没有下一个就为-1
        public TKey key;        // 存放元素的键
        public TValue value;    // 存放元素的值
    }

    2. 其它关键私有变量

    除了Entry结构体外,还有几个关键的私有变量,其定义和解释如下代码所示。

    private int[] buckets;      // Hash桶
    private Entry[] entries;    // Entry数组,存放元素
    private int count;          // 当前entries的index位置
    private int version;        // 当前版本,防止迭代过程中集合被更改
    private int freeList;       // 被删除Entry在entries中的下标index,这个位置是空闲的
    private int freeCount;      // 有多少个被删除的Entry,有多少个空闲的位置
    private IEqualityComparer<TKey> comparer;   // 比较器
    private KeyCollection keys;     // 存放Key的集合
    private ValueCollection values;     // 存放Value的集合

    上面代码中,需要注意的是buckets、entries这两个数组,这是实现Dictionary的关键。

    3. Dictionary – Add操作

    经过上面的分析,相信大家还不是特别明白为什么需要这么设计,需要这么做。那我们现在来走一遍Dictionary的Add流程,来体会一下。

    首先我们用图的形式来描述一个Dictionary的数据结构,其中只画出了关键的地方。桶大小为4以及Entry大小也为4的一个数据结构。

    1548491185593

    然后我们假设需要执行一个Add操作,dictionary.Add("a","b"),其中key = "a",value = "b"

    1. 根据key的值,计算出它的hashCode。我们假设”a”的hash值为6(GetHashCode("a") = 6)。

    2. 通过对hashCode取余运算,计算出该hashCode落在哪一个buckets桶中。现在桶的长度(buckets.Length)为4,那么就是6 % 4最后落在index为2的桶中,也就是buckets[2]

    3. 避开一种其它情况不谈,接下来它会将hashCode、key、value等信息存入entries[count]中,因为count位置是空闲的;继续count++指向下一个空闲位置。上图中第一个位置,index=0就是空闲的,所以就存放在entries[0]的位置。

    4. Entry的下标entryIndex赋值给buckets中对应下标的bucket。步骤3中是存放在entries[0]的位置,所以buckets[2]=0

    5. 最后version++,集合发生了变化,所以版本需要+1。只有增加、替换和删除元素才会更新版本

      上文中的步骤1~5只是方便大家理解,实际上有一些偏差,后文再谈Add操作小节中会补充。

    完成上面Add操作后,数据结构更新成了下图这样的形式。

    1548492100757

    这样是理想情况下的操作,一个bucket中只有一个hashCode没有碰撞的产生,但是实际上是会经常产生碰撞;那么Dictionary类中又是如何解决碰撞的呢。

    我们继续执行一个Add操作,dictionary.Add("c","d"),假设GetHashCode(“c”)=6,最后6 % 4 = 2。最后桶的index也是2,按照之前的步骤1~3是没有问题的,执行完后数据结构如下图所示。

    1548493287583

    如果继续执行步骤4那么buckets[2] = 1,然后原来的buckets[2]=>entries[0]的关系就会丢失,这是我们不愿意看到的。现在Entry中的next就发挥大作用了。

    如果对应的buckets[index]有其它元素已经存在,那么会执行以下两条语句,让新的entry.next指向之前的元素,让buckets[index]指向现在的新的元素,就构成了一个单链表。

    entries[index].next = buckets[targetBucket];
    ...
    buckets[targetBucket] = index;

    实际上步骤4也就是做一个这样的操作,并不会去判断是不是有其它元素,因为buckets中桶初始值就是-1,不会造成问题。

    经过上面的步骤以后,数据结构就更新成了下图这个样子。

    1548494357566

    4. Dictionary – Find操作

    为了方便演示如何查找,我们继续Add一个元素dictionary.Add("e","f")GetHashCode(“e”) = 7; 7% buckets.Length=3,数据结构如下所示。

    1548494583006

    假设我们现在执行这样一条语句dictionary.GetValueOrDefault("a"),会执行以下步骤.

    1. 获取key的hashCode,计算出所在的桶位置。我们之前提到,”a”的hashCode=6,所以最后计算出来targetBucket=2
    2. 通过buckets[2]=1找到entries[1],比较key的值是否相等,相等就返回entryIndex,不想等就继续entries[next]查找,直到找到key相等元素或者next == -1的时候。这里我们找到了key == "a"的元素,返回entryIndex=0
    3. 如果entryIndex >= 0那么返回对应的entries[entryIndex]元素,否则返回default(TValue)。这里我们直接返回entries[0].value

    整个查找的过程如下图所示.

    1548495296415

    将查找的代码摘录下来,如下所示。

    // 寻找Entry元素的位置
    private int FindEntry(TKey key) {
        if( key == null) {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }
    
        if (buckets != null) {
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF; // 获取HashCode,忽略符号位
            // int i = buckets[hashCode % buckets.Length] 找到对应桶,然后获取entry在entries中位置
            // i >= 0; i = entries[i].next 遍历单链表
            for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
                // 找到就返回了
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
            }
        }
        return -1;
    }
    ...
    internal TValue GetValueOrDefault(TKey key) {
        int i = FindEntry(key);
        // 大于等于0代表找到了元素位置,直接返回value
        // 否则返回该类型的默认值
        if (i >= 0) {
            return entries[i].value;
        }
        return default(TValue);
    }

    5. Dictionary – Remove操作

    前面已经向大家介绍了增加、查找,接下来向大家介绍Dictionary如何执行删除操作。我们沿用之前的Dictionary数据结构。

    1548494583006

    删除前面步骤和查找类似,也是需要找到元素的位置,然后再进行删除的操作。

    我们现在执行这样一条语句dictionary.Remove("a"),hashFunc运算结果和上文中一致。步骤大部分与查找类似,我们直接看摘录的代码,如下所示。

    public bool Remove(TKey key) {
        if(key == null) {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }
    
        if (buckets != null) {
            // 1. 通过key获取hashCode
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            // 2. 取余获取bucket位置
            int bucket = hashCode % buckets.Length;
            // last用于确定是否当前bucket的单链表中最后一个元素
            int last = -1;
            // 3. 遍历bucket对应的单链表
            for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                    // 4. 找到元素后,如果last< 0,代表当前是bucket中最后一个元素,那么直接让bucket内下标赋值为 entries[i].next即可
                    if (last < 0) {
                        buckets[bucket] = entries[i].next;
                    }
                    else {
                        // 4.1 last不小于0,代表当前元素处于bucket单链表中间位置,需要将该元素的头结点和尾节点相连起来,防止链表中断
                        entries[last].next = entries[i].next;
                    }
                    // 5. 将Entry结构体内数据初始化
                    entries[i].hashCode = -1;
                    // 5.1 建立freeList单链表
                    entries[i].next = freeList;
                    entries[i].key = default(TKey);
                    entries[i].value = default(TValue);
                    // *6. 关键的代码,freeList等于当前的entry位置,下一次Add元素会优先Add到该位置
                    freeList = i;
                    freeCount++;
                    // 7. 版本号+1
                    version++;
                    return true;
                }
            }
        }
        return false;
    }

    执行完上面代码后,数据结构就更新成了下图所示。需要注意varsion、freeList、freeCount的值都被更新了。

    1548496815179

    6. Dictionary – Resize操作(扩容)

    有细心的小伙伴可能看过了Add操作以后就想问了,buckets、entries不就是两个数组么,那万一数组放满了怎么办?接下来就是我所要介绍的Resize(扩容)这样一种操作,对我们的buckets、entries进行扩容。

    6.1 扩容操作的触发条件

    首先我们需要知道在什么情况下,会发生扩容操作;第一种情况自然就是数组已经满了,没有办法继续存放新的元素。如下图所示的情况。

    1548498710430

    从上文中大家都知道,Hash运算会不可避免的产生冲突,Dictionary中使用拉链法来解决冲突的问题,但是大家看下图中的这种情况。

    1548498901496

    所有的元素都刚好落在buckets[3]上面,结果就是导致了时间复杂度O(n),查找性能会下降;所以第二种,Dictionary中发生的碰撞次数太多,会严重影响性能,也会触发扩容操作。

    目前.Net Framwork 4.7中设置的碰撞次数阈值为100.

    public const int HashCollisionThreshold = 100;

    6.2 扩容操作如何进行

    为了给大家演示的清楚,模拟了以下这种数据结构,大小为2的Dictionary,假设碰撞的阈值为2;现在触发Hash碰撞扩容。

    1548499708530

    开始扩容操作。

    1.申请两倍于现在大小的buckets、entries
    2.将现有的元素拷贝到新的entries

    完成上面两步操作后,新数据结构如下所示。

    1548499785441

    3、如果是Hash碰撞扩容,使用新HashCode函数重新计算Hash值

    上文提到了,这是发生了Hash碰撞扩容,所以需要使用新的Hash函数计算Hash值。新的Hash函数并一定能解决碰撞的问题,有可能会更糟,像下图中一样的还是会落在同一个bucket上。

    1548500174305

    4、对entries每个元素bucket = newEntries[i].hashCode % newSize确定新buckets位置

    5、重建hash链,newEntries[i].next=buckets[bucket]; buckets[bucket]=i;

    因为buckets也扩充为两倍大小了,所以需要重新确定hashCode在哪个bucket中;最后重新建立hash单链表.

    1548500290419

    这就完成了扩容的操作,如果是达到Hash碰撞阈值触发的扩容可能扩容后结果会更差。

    在JDK中,HashMap如果碰撞的次数太多了,那么会将单链表转换为红黑树提升查找性能。目前.Net Framwork中还没有这样的优化,.Net Core中已经有了类似的优化,以后有时间在分享.Net Core的一些集合实现。

    每次扩容操作都需要遍历所有元素,会影响性能。所以创建Dictionary实例时最好设置一个预估的初始大小。

    private void Resize(int newSize, bool forceNewHashCodes) {
        Contract.Assert(newSize >= entries.Length);
        // 1. 申请新的Buckets和entries
        int[] newBuckets = new int[newSize];
        for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;
        Entry[] newEntries = new Entry[newSize];
        // 2. 将entries内元素拷贝到新的entries总
        Array.Copy(entries, 0, newEntries, 0, count);
        // 3. 如果是Hash碰撞扩容,使用新HashCode函数重新计算Hash值
        if(forceNewHashCodes) {
            for (int i = 0; i < count; i++) {
                if(newEntries[i].hashCode != -1) {
                    newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
                }
            }
        }
        // 4. 确定新的bucket位置
        // 5. 重建Hahs单链表
        for (int i = 0; i < count; i++) {
            if (newEntries[i].hashCode >= 0) {
                int bucket = newEntries[i].hashCode % newSize;
                newEntries[i].next = newBuckets[bucket];
                newBuckets[bucket] = i;
            }
        }
        buckets = newBuckets;
        entries = newEntries;
    }

    7. Dictionary – 再谈Add操作

    在我们之前的Add操作步骤中,提到了这样一段话,这里提到会有一种其它的情况,那就是有元素被删除的情况。

    1. 避开一种其它情况不谈,接下来它会将hashCode、key、value等信息存入entries[count]中,因为count位置是空闲的;继续count++指向下一个空闲位置。上图中第一个位置,index=0就是空闲的,所以就存放在entries[0]的位置。

    因为count是通过自增的方式来指向entries[]下一个空闲的entry,如果有元素被删除了,那么在count之前的位置就会出现一个空闲的entry;如果不处理,会有很多空间被浪费。

    这就是为什么Remove操作会记录freeList、freeCount,就是为了将删除的空间利用起来。实际上Add操作会优先使用freeList的空闲entry位置,摘录代码如下。

    private void Insert(TKey key, TValue value, bool add){
        
        if( key == null ) {
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
        }
    
        if (buckets == null) Initialize(0);
        // 通过key获取hashCode
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        // 计算出目标bucket下标
        int targetBucket = hashCode % buckets.Length;
        // 碰撞次数
        int collisionCount = 0;
        for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                // 如果是增加操作,遍历到了相同的元素,那么抛出异常
                if (add) {      
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
                }
                // 如果不是增加操作,那可能是索引赋值操作 dictionary["foo"] = "foo"
                // 那么赋值后版本++,退出
                entries[i].value = value;
                version++;
                return;
            }
            // 每遍历一个元素,都是一次碰撞
            collisionCount++;
        }
        int index;
        // 如果有被删除的元素,那么将元素放到被删除元素的空闲位置
        if (freeCount > 0) {
            index = freeList;
            freeList = entries[index].next;
            freeCount--;
        }
        else {
            // 如果当前entries已满,那么触发扩容
            if (count == entries.Length)
            {
                Resize();
                targetBucket = hashCode % buckets.Length;
            }
            index = count;
            count++;
        }
    
        // 给entry赋值
        entries[index].hashCode = hashCode;
        entries[index].next = buckets[targetBucket];
        entries[index].key = key;
        entries[index].value = value;
        buckets[targetBucket] = index;
        // 版本号++
        version++;
    
        // 如果碰撞次数大于设置的最大碰撞次数,那么触发Hash碰撞扩容
        if(collisionCount > HashHelpers.HashCollisionThreshold && HashHelpers.IsWellKnownEqualityComparer(comparer)) 
        {
            comparer = (IEqualityComparer<TKey>) HashHelpers.GetRandomizedEqualityComparer(comparer);
            Resize(entries.Length, true);
        }
    }

    上面就是完整的Add代码,还是很简单的对不对?

    8. Collection版本控制

    在上文中一直提到了version这个变量,在每一次新增、修改和删除操作时,都会使version++;那么这个version存在的意义是什么呢?

    首先我们来看一段代码,这段代码中首先实例化了一个Dictionary实例,然后通过foreach遍历该实例,在foreach代码块中使用dic.Remove(kv.Key)删除元素。

    1548504444217

    结果就是抛出了System.InvalidOperationException:"Collection was modified..."这样的异常,迭代过程中不允许集合出现变化。如果在Java中遍历直接删除元素,会出现诡异的问题,所以.Net中就使用了version来实现版本控制。

    那么如何在迭代过程中实现版本控制的呢?我们看一看源码就很清楚的知道。

    1548504844162

    在迭代器初始化时,就会记录dictionary.version版本号,之后每一次迭代过程都会检查版本号是否一致,如果不一致将抛出异常。

    这样就避免了在迭代过程中修改了集合,造成很多诡异的问题。

    展开全文
  • C# Dictionary用法总结

    2020-10-26 11:43:01
    1、常规用法 增加键值对之前需要判断是否存在该键,如果已经存在该键而且不判断... Dictionary<String, String> pList = new Dictionary<String, String>(); try { if (pList.ContainsKey("Item1") ==
  • C# Dictionary源码剖析

    千次阅读 2016-05-06 00:38:50
    Dictionary是Hashtable的一种泛型实现(也是一种哈希表)实现了IDictionary反应接口和非泛型接口等,将键映射到相应的值。任何非 null 对象都可以用作键。
  • Dictionary

    2017-05-23 16:31:32
    A dictionary is represented by a list of words with some number of spaces before certain words. Dictionary format can be described as a set of constraints on sequences of consecutive words starting ...
  • Dictionary排序

    万次阅读 2012-03-09 15:58:46
    有时候由于某些要求会对Dictionary排序,一般有两种方法。 1、使用SortedDictionary。 这种自动会对保存的值进行排序。 static void Main(string[] args) { SortedDictionary testDictioary = new ...
  • Data Dictionary

    千次阅读 2013-10-20 15:31:00
    Data Dictionary
  • C# Dictionary用法

    2015-06-19 10:25:57
    C# Dictionary用法总结 1、用法1: 常规用  增加键值对之前需要判断是否存在该键,如果已经存在该键而且不判断,将抛出异常。所以这样每次都要进行判断,很麻烦,在备注里使用了一个扩展方法 ...
  • Scripting.Dictionary 详解

    万次阅读 2011-12-20 10:55:15
    许多Microsoft的编程语言,如Visual Basic、VBScript和Jscript,都提供集合(collection)。可以把集合想象为数组,可以... VBScript和Jscript都提供类似的对象,通称Scripting.Dictionary对象或Dictionary对象。它类
  • c# Dictionary集合

    千次阅读 2008-04-03 13:01:00
    using System;using System.Collections.Generic;public class Example...{ public static void Main() ...{ // Create a new dictionary of strings, with string keys. // Dictionar
  • Dictionary Learning Tools for Matlab

    千次阅读 2012-05-22 10:38:11
    Dictionary Learning Tools for Matlab. Karl Skretting, University of Stavanger. Contents on this page: Relevant papers and links to other pages: A brief introduction, Spa
  • Python Dictionary

    千次阅读 2010-12-28 12:49:00
    1基本定义Python ... The general syntax of a dictionary is as follows:dict = {'Alice': '2341', 'Beth': '9102', 'Cecil': '3258'}The values of a dictionary can be of any type, but the keys must be of a
  • VB中的Dictionary对象

    千次阅读 2011-08-31 20:05:12
    简单的理解:Dictionary对象相当于二维数组,但比二维数组更灵活,可以随时操纵其中某个键,而二维数组还要遍历。 1. Dictionary对象的成员概要 当增加一个键/条目对时,如果该键已存在;或者删除一个键/条目对...
  • c# dictionary 深度剖析

    万次阅读 2018-08-05 16:49:22
    主要思想:http://www.cnblogs.com/wangjun1234/p/3719635.html 代码剖析;...   笔记: hash算法:除留余数法 F(key)%m ...内部有两个数组,一个bucket,一个装数据的entries, 一个entry有key,value,ha...
  • C#数据结构-Dictionary实现

    千次阅读 2018-03-28 17:07:18
    在看过一篇大神写的《带你看懂Dictionary的内部实现》,对Dictionary的内部实现有了一个清晰的了解,但纸上得来终觉浅,作为程序员,还是自己调试一下代码,记忆更深刻,为此专门拷贝出C#的Dictionary源码,因为源码...
  • python的dictionary(map)实现

    千次阅读 2012-05-10 12:53:45
    转自:http://www.laurentluce.com/posts/python-dictionary-implementation/ This post describes how dictionaries are implemented in the Python language. Dictionaries are indexed by keys and they ...
  • C# Dictionary的遍历理解

    万次阅读 2016-09-10 10:58:05
    C# Dictionary容器类的理解 本文章由cartzhang编写,转载请注明出处。 所有权利保留。 文章链接:http://blog.csdn.net/cartzhang/article/details/52490249 作者:cartzhang一、Dictionary容器类的内部实现在C#...
  • C# Dictionary和SortedDictionary简介

    千次阅读 2019-05-10 11:40:12
    SortedDictionary泛型类是检索运算复杂度为 O(logn) 的二叉搜索树,其中n是字典中的元素数。就这一点而言,它与SortedList泛型类相似。这两个类具有相似的对象模型,并且都具有 O(logn) 的检索运算复杂度。...
1 2 3 4 5 ... 20
收藏数 235,494
精华内容 94,197
关键字:

dictionary