Skip to main content

Dictionary基本概念

C#中的字典（Dictionary<TKey, TValue>）是一个集合，它存储了一组键值对（key-value pairs）。每个键在字典中都是唯一的，并与一个值相关联。字典提供了非常快速的基于键的数据检索，因为它们是使用哈希表来实现的。

下面是字典Dictionary<TKey, TValue>的一些主要特点和用法：

  1. 键的唯一性：每个键在字典中只能出现一次。尝试使用相同的键添加元素会导致异常，除非你先删除了原有的键值对。
  2. 高效的数据检索：字典提供了近乎O(1)复杂度的检索速度，这意味着无论字典中有多少元素，检索一个键关联的值所需的时间都是常数。
  3. 动态大小：字典可以动态增长以容纳新元素；当你添加元素时，它会根据需要自动调整其内部数组的大小。
  4. 泛型：Dictionary<TKey, TValue>是一个泛型集合，意味着你可以指定键和值的类型，从而提供类型安全性。
  5. 线程不安全：Dictionary<TKey, TValue>不是线程安全的。如果在多个线程中同时修改字典，可能会导致数据损坏。在多线程环境中，你可以使用ConcurrentDictionary<TKey, TValue>来替代。

总结字典​

  1. Dictionary表示键和值的集合。
  2. Dictionary<object, object>是一个泛型。
  3. 他本身有集合的功能有时候可以把它看成数组。
  4. 他的结构是这样的：Dictionary<[key], [value]>。
  5. 他的特点是存入对象是需要与[key]值一一对应的存入该泛型，任何键都是唯一。
  6. 通过某一个一定的[key]去找到对应的值。查找元素的时间复杂度为O(1)。

增删查改时间复杂度​

  1. Dictionary字典类是hash表，Add操作是O(1)。
  2. 其Containskey方法是O(1)，原因是通过hash来查找元素而不是遍历元素。
  3. ContainsValue方法的时间复杂度是O(N)，原因是内部通过遍历key来查找value，而不是通过hash来查找。
  4. ltem[Key]属性根据key来检索value，其时间复杂度也是O(1)。
  5. 基本都是O(1)

底层实现原理Dictionary在构造的时候做了以下几件事：

  1. 初始化一个桶数组this.buckets = new int[prime]
  2. 初始化一个this.entries = new Entry<TKey, TValue>[prime]

Bucket和entries的容量都为大于字典容量的一个最小的质数其中this.buckets主要用来进行Hash碰撞

this.entries用来存储字典的内容，并且标识下一个元素的位置。

实现过程​

  1. 哈希表法

将不定长的二进制数据集映射到一个较短的二进制数据集，一个Key通过HashFunc得到HashCode。

  1. Hash桶算法

对HashCode进行分段显示，常用方法对HashCode直接取余。

  1. 拉链法

分段则会导致key对应的哈希桶相同，拉链法的基本思想就像对冲突的元素，建立一个单链表，头指针存储在对应哈希桶的位置。反之就是通过hash桶对应后，遍历单链表，获取value值。