面试题：C#中List<T>与Dictionary<TKey, TValue>的区别

Question

请详细阐述C#中List<T>与Dictionary<TKey, TValue>这两种集合类型在存储结构、访问方式、性能特点以及适用场景方面的区别。

Answer 1

存储结构

• List：基于数组实现的动态数组结构。它在内存中是连续存储的，当元素数量超过初始容量时，会重新分配内存并将原有元素复制到新的内存位置。
• Dictionary<TKey, TValue>：基于哈希表实现。它使用哈希函数将键映射到特定的存储位置，每个键值对存储在哈希桶中。

访问方式

• List：通过索引访问元素，即list[index]。索引从0开始，这种访问方式时间复杂度为O(1)。
• Dictionary<TKey, TValue>：通过键来访问值，即dictionary[key]。它先通过哈希函数计算键的哈希值，再找到对应的存储位置，时间复杂度在理想情况下为O(1)，但在哈希冲突严重时会退化到O(n)。

性能特点

• List：
  • 查找：顺序查找时间复杂度为O(n)，因为需要遍历整个列表；若事先排序，使用二分查找时间复杂度为O(log n)。
  • 插入和删除：在列表末尾插入和删除元素时间复杂度为O(1)；在中间插入或删除元素时间复杂度为O(n)，因为需要移动后续元素。
  • 遍历：遍历速度较快，因为内存连续，缓存命中率高。
• Dictionary<TKey, TValue>：
  • 查找：理想情况下查找时间复杂度为O(1)，但如果哈希冲突较多，性能会下降。
  • 插入和删除：插入和删除操作在理想情况下时间复杂度也是O(1)，但同样受哈希冲突影响。
  • 遍历：遍历顺序与插入顺序无关，且遍历性能相对List在某些情况下稍低，因为哈希表的内存分布不连续。

适用场景

• List：
  • 当需要按顺序存储元素，并经常通过索引访问元素时，如实现队列、栈等数据结构。
  • 当需要频繁在列表末尾进行插入和删除操作时。
  • 当数据量较小，且查找操作以顺序查找或二分查找为主时。
• Dictionary<TKey, TValue>：
  • 当需要通过键快速查找对应值，且键唯一时，如实现缓存、配置表等。
  • 当插入和删除操作频繁，且需要高效的查找性能时。
  • 当不需要维护元素的顺序，只关注键值对关系时。