1.2 C#基础

一、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）。所以字典更适合查询。