C#中的数据字典Dictionary

前言

今天上午和往常一样在网上冲浪,看到码甲哥微信群里面在聊一个面试题，比较有意思，这里简单分享下结论中的Dictionary字典。

有50w个int类型的数字，现在需要判断一下里面是否存在重复的数字，请简要说明下。

假如这个题目让我做，第一感觉可能直接向两个for循环，简单做个判断就解决了。可是看到几个大佬的讨论，才发现是我知识浅薄了。

这道题难道考的就是对业务代码循环的应用吗？肯定不是的。

我们知道,在验证一段代码或者一个程序算法的完美指标是空间复杂度和时间复杂度。通过这两个指标来进行评判。

空间复杂度：

是指在一个算法程序在执行过程中，单位时间内临时所占用的存储容量是多少。用S(n)=O(f(n))来表示。

时间复杂度：

是指在一个算法程序执行过程中，所需要花费的时间多少。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称为O(f(n))为算法的时间复杂度。

比如插入排序的时间复杂度是O(n^2),空间复杂度是O(1)。

一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

群里面讨论的过程中，出现有数组array，键值对，还有数据字典Dictionary(键值对的一种)。最后都觉得使用Dictionary存储这50w个int类型的数据，利用其key或者value来判断是否有重复的值。

既然看到这里了，今天咱也就简单复习下Dictionary，看看它到底有什么魅力。

Dictionary<TKey,TValue>字典

根据MSDN上的记载，说它是表示键和值的集合。提供一组键到一组值的映射。每次对字典的添加都包含一个值和与其关联的键。使用其键检索值的速度非常快，接近O(1)。

Dictionary<TKey,TValue>该类是作为哈希表实现的，检索的速度取决于为指定的类型的哈希算法的质量TKey。

其余特性简单总结如下

• 必须包含命名空间System.Collection.Generic

• Dictionary里面的每一个元素都是一个键值对

• 键必须是唯一的，而值不需要唯一

• 键和值都可以是任何类型

• 通过一个键读取一个值的时间复杂度接近O(1)，查找速度非常快，要比list等快很多

• 键值对之间的偏序可以不定义

• 可以实现通过键值查找、插入、删除一个键值对的操作，这些如果用数组实现非常麻烦

下面是关于Dictionary的一些CRUD操作。

定义字典、添加键值、取值、改值、遍历key、遍历value、删除元素、清空所有元素

  //定义
  static Dictionary<int, string> ahuiInfo = new Dictionary<int, string>();
  static void Main(string[] args)
  {
      //添加键值
      ahuiInfo.Add(1,"阿辉");
      ahuiInfo.Add(2, "阿酶");
      ahuiInfo[2] = "阿一"
      //取值
      var name=ahuiInfo[0].ToString();
      Console.WriteLine(""+name
      //修改值
      ahuiInfo[0] = "阿姨";
      Console.WriteLine("" + ahuiInfo[0].ToString()
      //遍历key和value
      foreach (var key in ahuiInfo.Keys)
      {
          Console.WriteLine(""+key.ToString());
      foreach (var value in ahuiInfo.Values)
      {
          Console.WriteLine(" "+value.ToString());
      //遍历字典
      foreach(KeyValuePair<int ,string> kvp in ahuiInfo)
      {
          Console.WriteLine("key="+kvp.Key+"，value="+kvp.Value);
      //删除元素
      ahuiInfo.Remove(0
      //判断键是否存在
      if (ahuiInfo.ContainsKey(0))
      {
          Console.WriteLine("true");
      }
      else
      {
          Console.WriteLine("false");
      }
  }
}