【C#】Dictionary和List泛型比较

你的名字 2022-09-25 11:27 189阅读 0赞

这几天做项目被一个问题难倒了，不知如何去动手，问了师哥有点小小的收获，给我普及了一下C\#中dictionary的用法；我们以前做项目的时候用到最多的就是list泛型，来讲一讲两者的比较吧。

#  【Dictionary】 #

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

##    Dictionary的描述 ##

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");
 }

# 【比较】 #

下面是一个小的程序只是为说明List和Dictionary效率的差别。

/// <summary>
 /// 集合类效率测试
 /// </summary>
 public class SetEfficiencyTest
 {
 static List<TestModel> todayList = InitTodayData();
 static List<TestModel> historyList = InitHisoryData();
 
 public static void Run()
 {
 CodeTimer.Time("ListTest", 1, ListTest);
 CodeTimer.Time("DictionaryTest", 1, DictionaryTest);
 }
 
 public static void ListTest()
 {
 List<TestModel> resultList = todayList.FindAll(re =>
 {
 if (historyList.Exists(m => m.UserID == re.UserID && m.BookID == re.BookID))
 {
 return false;
 }
 return true;
 });
 }
 
 public static void DictionaryTest()
 {
 Dictionary<int, List<string>> bDic = new Dictionary<int, List<string>>();
 foreach (TestModel obj in historyList)
 {
 if (!bDic.ContainsKey(obj.UserID))
 {
 bDic.Add(obj.UserID, new List<string>());
 }
 bDic[obj.UserID].Add(obj.BookID);
 }
 
 List<TestModel> resultList = todayList.FindAll(re =>
 {
 if (bDic.ContainsKey(re.UserID) && bDic[re.UserID].Contains(re.BookID))
 {
 return false;
 }
 return true;
 });
 }
 
 /// <summary>
 /// 初始化数据（今日）
 /// </summary>
 /// <returns></returns>
 public static List<TestModel> InitTodayData()
 {
 List<TestModel> list = new List<TestModel>();
 for (int i = 0; i < 10000; i++)
 {
 list.Add(new TestModel() { UserID = i, BookID = i.ToString() });
 }
 return list;
 }
 
 /// <summary>
 /// 初始化数据（历史）
 /// </summary>
 /// <returns></returns>
 public static List<TestModel> InitHisoryData()
 {
 List<TestModel> list = new List<TestModel>();
 Random r = new Random();
 int loopTimes = 60000;
 for (int i = 0; i < loopTimes; i++)
 {
 list.Add(new TestModel() { UserID = r.Next(0, loopTimes), BookID = i.ToString() });
 }
 return list;
 }
 
 /// <summary>
 /// 测试实体
 /// </summary>
 public class TestModel
 {
 /// <summary>
 /// 用户ID
 /// </summary>
 public int UserID { get; set; }
 
 /// <summary>
 /// 书ID
 /// </summary>
 public string BookID { get; set; }
 }
 }

##      输出如下： ##

![Center][]   
      真是想不到，两者效率相差这么多。接下来研究下两者差异巨大的原因。

#   List<T>.Exists()函数的实现： #

public bool Exists(Predicate<T> match)
 {
 return this.FindIndex(match) != -1;
 }
 
 public int FindIndex(Predicate<T> match)
 {
 return this.FindIndex(0, this._size, match);
 }
 public int FindIndex(int startIndex, int count, Predicate<T> match)
 {
 if (startIndex > this._size)
 {
 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.startIndex, ExceptionResource.ArgumentOutOfRange_Index);
 }
 if (count < 0 || startIndex > this._size - count)
 {
 ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_Count);
 }
 if (match == null)
 {
 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
 }
 int num = startIndex + count;
 for (int i = startIndex; i < num; i++)
 {
 if (match(this._items[i]))
 {
 return i;
 }
 }
 return -1;
 }

List<T>.Exists 本质是通过循环查找出该条数据，每一次的调用都会重头循环，所以效率很低。显然，这是不可取的。

#   Dictionary<TKey, TValue>.ContainsKey()函数的实现： #

public bool ContainsKey(TKey key)
 {
 return this.FindEntry(key) >= 0;
 }
 
 // System.Collections.Generic.Dictionary<TKey, TValue>
 private int FindEntry(TKey key)
 {
 if (key == null)
 {
 ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
 }
 if (this.buckets != null)
 {
 int num = this.comparer.GetHashCode(key) & 2147483647;
 for (int i = this.buckets[num % this.buckets.Length]; i >= 0; i = this.entries[i].next)
 {
 if (this.entries[i].hashCode == num && this.comparer.Equals(this.entries[i].key, key))
 {
 return i;
 }
 }
 }
 return -1;
 }

Dictionary<TKey, TValue>.ContainsKey() 内部是通过Hash查找实现的，所以效率比List高出很多。

# 【总结】    #

1.如果需要非常快地添加、删除和查找项目，而且不关心集合中项目的顺序，那么首先应该考虑使Dictionary<TKey, TValue> 
    2.如果您的使用模式很少需要删除和大量添加，而重要的是保持集合的顺序，那么您仍然可以选择 List<T>。 
    3.如果需要在实现快速插入的同时保持顺序，那么使用新的 LinkedList<T> 集合可帮助您提高性能。

[Center]: /images/20220718/ccc1992a786f4b7aaf0cdb43caa161f5.png