1.2 C#基础

2024-01-07 17:57:09

一、Stack栈和Queue队列

相同点:

  1. 都是线性结构。
  2. 插入操作都是限定在表尾进行。
  3. 都可以通过顺序结构和链式结构实现。
  4. 插入与删除的时间复杂度都是O(1),在空间复杂度上两者也一样。
  5. 多链栈和多链队列的管理模式可以相同。
  6. 底层都是由泛型数组实现。

不同点:

  1. 栈先进后出,队列先进先出:删除数据元素的位置不同,栈的删除操作在表尾进行,队列的删除操作在表头进行。
  2. 顺序栈能够实现多栈空间共享,而顺序队列不能。
  3. 应用场景不同

常见栈的应用场景包括

  1. 括号问题的求解,
  2. 深度优先搜索遍历等;
  3. 函数调用和递归实现,
  4. 表达式的转换和求值

常见的队列的应用场景包括

  1. 计算机系统中各种资源的管理,
  2. 消息缓冲器的管理
  3. 广度优先搜索遍历等

二、链表与数组

  1. 数组必须事先定义固定的长度(元素个数),不能适应数据动态地增减的情况。当数据增加时,可能超出原先定义的元素个数;当数据减少时,造成内存浪费;数组可以根据下标直接存取,时间复杂度O(1)。
  2. 链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项。(数组中插入、删除数据项时,需要移动其它数据项,非常繁琐)链表必须根据next指针找到下一个元素。

如果需要快速访问数据,很少或不插入和删除元素,就应该用数组;相反,如果需要经常插入和删除元素就需要用链表数据结构了。

三、字典

介绍

  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)。

底层实现原理

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。
  2. Hash桶算法:对HashCode进行分段显示,常用方法对HashCode直接取余。
  3. 拉链法:分段则会导致key对应的哈希桶相同,拉链法的基本思想就像对冲突的元素,建立一个单链表,头指针存储在对应哈希桶的位置。反之就是通过hash桶对应后,遍历单链表,获取value值。

四、哈希表与字典对比

字典:内部用了Hashtable作为存储结构

  • 如果我们试图找到一个不存在的键,它将返回 / 抛出异常。
  • 它比哈希表更快,因为没有装箱和拆箱,尤其是值类型。
  • 仅公共静态成员是线程安全的。
  • 字典是一种通用类型,这意味着我们可以将其与任何数据类型一起使用(创建时,必须同时指定键和值的数据类型)。
  • Dictionay 是 Hashtable 的类型安全实现, Keys和Values是强类型的。
  • Dictionary遍历输出的顺序,就是加入的顺序

哈希表:

  • 如果我们尝试查找不存在的键,则返回 null。
  • 它比字典慢,因为它需要装箱和拆箱。
  • 哈希表中的所有成员都是线程安全的,
  • 哈希表不是通用类型,Hashtable 是松散类型的数据结构,我们可以添加任何类型的键和值。
  • HashTable是经过优化的,访问下标的对象先散列过,所以内部是无序散列的


五、关于List与字典的遍历与查询效率

  1. List的底层,是一个泛型数组,连续且紧密的顺序存储,一般数据存储在缓存中。而字典是离散(散列)分布,由数组和哈希表共同组成,遍历的时候,会伴有换页的操作,且数组都存储在内存中。而读写速度是:缓存>内存>硬盘。因此List更适合遍历。
  2. 字典的查询效率是通过元素的key值进行取余操作,找的对应的哈希桶,判定哈希桶对应的哈希表的头节点是不是该元素,若不是进行next操作,对哈希表进行遍历,这两个过程都是常数级别的操作。所以是O(1)。而List的查询效率是先遍历,找到对应的值,因此是O(n)。所以字典更适合查询。
    ?

文章来源:https://blog.csdn.net/m0_53930254/article/details/135343241
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。