数据结构性能对比 List、LinkedList、Dictionary
1. ArrayList （List：前传）
ArrayList
是一个特殊数组，
通过添加和删除元素就可以动态改变数组的长度。
ArrayList集合相对于数组的优点：
支持自动改变大小，
可以灵活的插入元素，
可以灵活的删除元素，
可以灵活的访问元素。
ArrayList 自身缺陷：
ArrayList只支持一维，
并且查询和检索的速度较慢。
简而言之
灵活性提升，速度不足。
在C#中数据类型分为两类：值类型和引用类型。值类型
int ，bool， char， double， enum， struct， DateTime等
都是值类型
引用类型
string，Array，class集合 等都是引用类型。
值类型和引用类型的重要特征如下：
差别：
值类型的长度固定，
而引用类型的长度不固定
数据存储：
如果是值类型直接存储在栈中（局部变量），
如果是引用类型，先把数据存储在堆中，然后把堆的地址存储在栈中。
object类:所有类的基类
所有的数据类型都可以转换成object类，
ArrayList 在存储的时候全被转换成object类型存储
这就是为什么ArrayList既可以存储值类型，也可以存储引用类型。
灵活性 换 性能：
当然这也是ArrayList的一个缺点，
由于存储的时候需要把值类型封装成object类型，
取出来的时候需要再把object类型再转换成值类型，
这一装箱和拆箱的过程非常消耗性能。
正所谓，鱼与熊掌，不可兼得。
扩展阅读
装箱：
由值类型封装成object类型的过程称为装箱。
拆箱：
由object类型转换成值类型的过程称为拆箱。
2. List
传承：
List 继承了ArrayList的特点，高灵活性。
改进：
基于ArrayList低性能的弱点，我们进行了改进！
在声明时需要指定类型，避免装箱拆箱操作，提升性能。
只是多写个<int>就极大提高了速度，何乐而不为。
特点：
拥有索引，可进行排序，修改等等。
3. LinkedList
新的问题：
ArrayList或者List虽说灵活性很好，
但都有个缺陷，插入元素或者移除元素时速度较慢，
因为存在：后续元素的位置变化！
厌恶真空：
中间一旦有人缺席，所有人都要前移去补位，牵一发动全身，
因此，没事千万别往ArrayList和List中间踢人或插队。
避免造成连锁反应，途耗性能！
解决方案：
LinkedList每个元素记录下一个元素的位置，
插入或者移除元素时只需要修改标记即可，
不用移动后面的元素，大大提高了效率。
使用方法
ArrayList vs Lis vs LinkedList：
尽量避免用ArrayList，多线程时候可以用ConcurrentBag代替。
插入、删除较多用LinkedList，否则用List。
包(Bag)包可包含重复元素(此处对应List)。
集(Set)集中不能包含重复元素。
4. HashTable
key-value组合，可以添加不同类型的数据，取出之后需要转换成对应类型
Hashtable hashtable = new Hashtable();
hashtable.Add("Name", "HadsNyx");
hashtable.Add("age", 25);
return hashtable;HashTable线程安全，允许单线程写入，多线程读取。
5. Dictionary
key-value组合，必须指定数据类型
特点：
速度较快，不必装箱拆箱
非线程安全（即使这样，也可以用ConcurrentDictionary代替）
HashTable vs Dictionary :
Dictionary效率高，但是人为lock保持线程安全时效率反而低下。
多线程编程用ConcurrentDictionary，只有单线程用Dictionary。
优化小技巧：
由于Dictionary有底层，有桶和链表结构，
有时候将List转为Dictionary进行操作，
(用主键作为key，保证无重复元素)，反而效率更高。
6. 性能排序：
插入性能： LinkedList > Dictionary > HashTable > List
遍历性能：List > LinkedList > Dictionary > HashTable
删除性能： Dictionary > LinkedList > HashTable > List
统计：
Dictionary，3项性能都在前三的位置
LinkedList，3项性能都在前二的位置
小结：
在修改较频繁，且查找和删除也较多时，首选LinkedList,
在主要以删除为主，插入为辅，且查找较少时，首选Dictionary，
在查找频繁，而又无需修改的情况下，则首选List。
总结：
只查找，首选List；
插入为主，查找和删除为辅，首选LinkedList；
删除为主，查找和插入为辅，首选Dictionary；
注意：是插入不是新增，新增都没多大区别
扩展阅读
HashSet<T>和SortedSet<T>
HashSet<T>和SortedSet<T>都属于集
Set:元素不可重复
加入重复元素时并不会报错。
SortedSet还有排序的功能
例如：加入1、3、2，foreach会得到1、2、3
导航图：(右键新窗口中打开，否则404)
array 数组
arraylist 动态数组
list 列表
queue 队列
stack 堆栈
linkedlist 链表
hashtable 哈希表
dictionary 字典
SortedList 排序列表
SortedDictionary 排序字典
hashset 哈希集
sortedset 排序集
PS:
为什么ArrayList的效率会比较低
因为ArrayList是使用数组实现的,若要从数组中删除或插入某一个对象，需要移动后段的数组元素，从而会重新调整索引顺序,调整索引顺序会消耗一定的时间，所以速度上就会比LinkedList要慢许多. 相反,LinkedList是使用链表实现的,若要从链表中删除或插入某一个对象,只需要改变前后对象的引用即可。
array的效率要比List的要高一些，当数组长度不是很大时，两者没什么区别，建议用List<>，毕竟是可变长度，可以Add；特殊应用还是建议用array，
