数据结构与算法(七)

邯郸驿里逢冬至,抱膝灯前影伴身。

也许你开始疑惑,明明是数据结构和算法,为什么只有第一篇文章介绍了数组,然后就一直在介绍算法,别急,这篇文章就是来介绍第二个数据结构的。

字典

在不同的编程语言中,字典有许多其他的名称,比如“散列表”,“映射”,“关联数组”等。

首先,来看为什么会叫“散列表”,给你以下的 字母-数字 对应关系:

A=1

B=2

C=3

D=4

E=5

F=6

G=7

然后给你一串字母“ACE”,那么你立马就会知道这串字母等于135。此过程可以说成解码,或者说成是翻译的过程,这个过程就是散列,上面的A=1,B=2,这样的对应的关系,就是散列函数。

但是,不要误解,密码本不仅仅只有翻译字符串的功能,我们可以赋予它任何解密的功能。在字典中的功能就是快速的通过key找到value。c#中的这个算法是一个哈希算法来做的,这个算法后续的文章中会说。

这个散列函数也要遵循一些条件,对于同一个key,每次计算的都是相同的value,否则,此散列函数无效。

上图表现的关系,通过key值计算出value的存放的地址,所以寻找key的值的时间复杂的大概是O(1),那么,这里为什么要说大概呢?我们再看,有这样的一个情况,如果key1通过散列函数计算出来的值为:1,key2通过散列函数计算出来的值为:1。那么这时候,就不知道你究竟要取哪一个值,那么遇到这个情况要怎么办呢?

经典的做法就是“分离链接”,具体的做法是什么呢?将value处的值不再放key1/key2的值,而是用一个数组来替代。

数组中存放对应的key1与key2的值,与之前不同的是,这里数组的长度为2,数组的第一位存放的是各自value值的标签。通过匹配与key对应的标签,迅速的找到它的值,所以能找到各自的值。

那么受之前的“最坏情况”思想的影响,那么最坏的情况就是一个字典中所有的值都放在一个格子中,那么它的时间复杂度应该是O(N),前文明明说过是O(1),那么还有什么情况这里还没有介绍呢?

找到平衡

归根到底,散列表的效率取决于以下因素

  • 存放的数据大小
  • 格子的长度
  • 散列函数

前2个很容易理解,数据的大小与存放的空间,影响它操作速度,但是与散列函数有什么关系呢?其实关系很大,上文我们已经提到了最坏的情况,这里就不再赘述。

数量与空间的对应关系,前人已经研究出了黄金法则:每增加7个元素就增加10个格子。即“负载因子”为0.7。

准备放7个元素,那么计算机会分配10个格子

准备放14个元素,那么计算机会分配20个格子

但是这个不需要我们编写代码的时候设置,计算机语言已经将这些约束写在了底层,我们直接一般的插入就好,计算机会帮你觉得格子的大小。

知道了这些特性,那么你就可以在某些方面来取代数组,来提升代码性能。

前文中说过,不允许出现重复的key,那么插入一个重复的key值,结果会如何呢?

vs会提示你:已经添加了具有相同键的项

c#中的字典写法

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

字典中的数据都是成对出现的,也称之为“键值对”,前面的int代表键,(key),后面的string就是值(value),一对键值对构成字典中的一个“元素”.其中元素中的键一定要唯一,但是值不需要唯一,因为键唯一之后才能知道具体查找的value的值.

首先,在c#中,使用字典必须要引入一个命名空间:

System.Collection.generic;

这个命名空间包含用于处理集合的泛型类型,那么顾名思义,这个命名空间中还包括其他的数据结构类型,其中就包括前面文章已经出现过的List<T>。当然还有其它的集合,这个后面的文章会介绍.

字典的使用说明

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

1、添加元素

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

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

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

myDictionary.Add(4,"MVC");

2、通过Key查找元素

if(myDictionary.ContainsKey())
{
  Debug.Log("Key:{0},Value:{1}","1", myDictionary[]);
}

3、通过KeyValuePair遍历元素

foreach(KeyValuePair<int,string>kvp in myDictionary)
{
    Debug.Log("Key = {0}, Value = {1}",kvp.Key, kvp.Value);
}

4、仅遍历键 Keys 属性

Dictionary<int,string>.KeyCollection keyCol=myDictionary.Keys;
foreach(intkeyinkeyCol)
{
    Debug.Log("Key = {0}", key);
}

5、仅遍历值 Valus属性

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

foreach(stringvalueinvalueCol)
{
    Debug.Log("Value = {0}", value);
}

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

myDictionary.Remove();

if(myDictionary.ContainsKey())
{
  Debug.Log("Key:{0},Value:{1}","1", myDictionary[]);
}
else
{
   Debug.Log("不存在 Key : 1"); 
}


7、获取与指定的键相关联的值

//我们可以通过下面方面来获取对应key的值
    public static string GetUserField(string fieldName)  
           {  
               string finfo = "";  
               UserFields.TryGetValue(fieldName, out finfo);  
               return finfo;  
           }  

(bool)(UserFields.TryGetValue(fieldName, out finfo))
可将其转为boo类型,它方便的是避免了判断key知否存在而引发“ 给定关键字不在字典中。
的错误。可以通过下面的测试来更进一步了解:
Dictionary<string, string> dic = new Dictionary<string, string>();  
                dic.Add("aaa", "123");  
                dic.Add("bbb", "456");  
                dic.Add("ccc", "789");  
                dic.Add("ddd", "321");  

                string outStr = "999";  
                dic.TryGetValue("ttt", out outStr);  
                Debug.Log(outStr );  
                dic.TryGetValue("bbb", out outStr);  
                Debug.Log(outStr );  

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

方法

属性说明

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:

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

总结

高效的代码中离不开字典,因为O(1)的读取与插入带来了无与伦比的性能优势,

目前为止,我们只是探讨了性能,其实除了这个之外,数据结构的特性也是值得探讨的,这也是下文我们要说的。

…END…

正文完