C#中的数据结构（二）-一起快乐学编程
最近一直很忙，所以写些东西的时间很少，感谢大家的关注与信任。值得肯定的是，今天微信公众平台邀请了我开通了原创功能，因此开通了原创声明、赞赏、留言等功能。
总之呢，非常感谢大家的支持，我会继续努力的！
今天呢，我们聊一聊非常实用、也很常用的一个数据结构--散列表（也叫哈希表）。
C#中，有两个散列表，一个是Dictionary，另一个是Hashtable。二者的核心是一样的，都是散列表，但是也有区别。区别不是我们今天讨论的重点，我在文章最后简单列一下二者的区别。
直接寻址表
上一篇数据结构的文章里面提到了两个动态的集合结构，分别是List<T>和LinkedList<T>。这两个数据结构均支持插入、删除、查找等功能倾楚天下。List<T>的查找是通过下标来快速索引，但是很多时候我们并不一定会用到下标来作为索引，而且很多时候索引的Key并不一定是连续的整形数字。这时候我们引入了一个新的概念，散列表。
散列表是实现字典操作（通过key索引到value）的一种有效的数据结构。散列表也用到了最基本的数据结构--数组。上一篇文章讲到，数组可以在O(1)(时间复杂度，有不懂的同学可以留言给我，有时间的话专门讲一下这个知识点)时间访问数组任何有效的位置。
我们假设一下，当我们的数据量很小的时候，我们有一个集合用来存储关键字，我们把这个集合或者称为数组叫做U。然后我们再有一个集合叫做T，用来一一对应U中的关键字，这个存储的关键字为真正数据的物理地址大地懒。然后我们通过这个物理地址直接索引到存储的value（图中的satellite data，又有直译卫星数据）。大概示意图如下：
这种方式我们成为直接寻址表索引的方式。我们不难看出方数真，当数据量大的时候（这也是为什么上一段开始我们先假设数据量不大的时候了），我们需要维护一个非常大的集合U和集合T傅劲，而且集合U中还存在很多冗余，即用不到的key。
散列表
如果上述集合U，只存储有效的关键字key，我们通过一个固定的算法计算出对应的所在集合T的位置，那么我们就可以大大的缩减了集合U。我们所说的这个算法就是hash function，散列函数。而集合T，我们命名为hash table。我们可以说，关键字key的元素被散列到了hashfunction(key)上（下图中buckets里的值），也可以说hashfunction(key)（下图中buckets里的值）是关键字key的散列值。
这时候只是我们的理想状态，算出的哈希值都是唯一的，但是事实并不是这样，有时候两个不同的关键字key可能散列到相同的位置上，这时候就发生了冲突。
上一篇文章中提到了一种数据结构叫做链表，我们散列后的值并不是直接存储value，而是存储一个链表的表头。如果我们散列后的值相同的时候，我们就把这个值依次的向链表尾部存放，这样通过链接法解决了冲突。
理想的状态是尽量不要让所有的散列值冲突，这样，每次散列函数算出来的散列值，都是唯一的，地址也就唯一，查找的速度就是O(1)了。因此，好的散列算法应该是让散列后的值尽可能的唯一。常用的散列算法有几种，比如乘法散列、除法散列等，有兴趣的同学可以深入了解一下。
思考
1、散列表的删除操作，是怎么进行的呢？
2、上述处理冲突的时候，我说的是链表，那么是单链表还是双链表还是都可以呢？
3、散列表能否保证数据的添加顺序呢？
最后说一下C#中的Dictionary和Hashtable的区别何莉秀。
1、Dictionary有泛型的优势项羽之死，而Hashtable的key和value都是object，优瓦夏因此当key是值类型的时候，会有装箱拆箱的操作。
2、Dictionary的插入是有顺序的，即用迭代器迭代遍历的时候（foreach）的顺序和Add的顺序一致，而Hashtable没有此特性。（有兴趣的同学可以看看C#的源码，这个也正是我上面的思考题3）
3、默认的Hashtable是单线程写入、多线程读取的，换句话说就是线程安全的，而Dictionary不是线程安全的，在读写的时候需要加锁。
4、至于二者的速度，当然各有所长，按需使用吧。
写在最后：
其实散列表内容很多，我这里只是简单说了一下原理，有兴趣的同学可以在网上多找找资料，深入了解一下散列表的内部实现。文中图片本来我自己画了一遍，发现没用专业的画图软件实在太丑了，于是搜索了几张图，如果无意侵权，请告知，我会修正的。
今天真的是太忙了，本来1023开始写的文章，等写完了发现已经1024了清辉阁。1024正好是程序员节，祝大家节日快乐潘若瑶！今天开始，文章就可以留言了，大家有什么问题可以在下方留言啊。当然也可以直接在公众号给我留言，我都会看到的。
感谢大家关注，如果觉得这篇文章不错的话，欢迎推荐给其他正在学编程的同学把索菲·特纳！