数据结构

听人吹过无数牛逼数据结构对于一个程序员是何等的重要。

只是，对于一个脑子天生有着自己的回路和想法的人来说，这些横来竖去弯弯绕的算法和实现确实是很烧脑的。

在学习这门课程的时候，我深刻地感受到了为什么每个优秀的程序员在这个寒冷凄清的深秋都是锃亮头上凉飕飕。

也许这真的是那种需要时时思考、一刻也不能停歇的学科吧。

虽然这是个认可思考产出和知识能力的时代，但是这种近乎于贩卖脑细胞的方式实在是让人蛋疼。

我想如果要我坚持个整个大学四年都研究算法的话，爆炸的思维把脑袋骨架撑成马云也不是没有可能。

我认可的工作，是能够随着时间获得别人无法掠夺的价值和经验的。

学习也有多种多样，掰开了揉碎了，深入地理解其中每个地方的精髓固然是一种，我却不喜，如果都看清了，还有什么期望呢？

但是既然问题出现了，除了直面解决之外没有任何办法，开始做就好了。

这就是我给自己的目标，开始第一步，然后沉浸进去，只要时间没有被浪费，无论怎样也不算是白活。

况且，以文载道，总是欣喜，我希望能够通过自己的文字给这枯燥的学习中注入活力，那么就开始吧。

教材

用文字来辅佐学习是最近才开始萌发的想法，采用的教材是《数据结构、算法与应用c++描述》机械工业出版社，正好学到了散列函数，权当复习一下（其实只是不想又肝又烧脑地将作业快速完成而已）

散列表

散列表，其实也就是表，表是什么呢？放在c++里，那叫数组，数组有什么特点，顺序存储，而顺序本身就是有序，所以，我们既然用了表，就是为了实现一定程度上的数据有序和空间的易管理性。

啥是散列表嘞？

说到散列表，就要先明确问题的背景，对于所有的数据结构来说，都是为了适应一定的问题而存在的，而我们的散列表的用武之地，是字典对。

很惭愧我到这里已经几乎差不多忘了字典对到底是个什么东西，只好是回去找书又翻了一下概念，最后才明白，于是在这里想要絮叨絮叨一下，字典对这个东东到底是个什么东东。

字典对

其实比起所谓的字典对，我更倾向于用键值组来描述这个概念，键，也就是key，值，也就是value，其实也就是索引和元素值的关系。

其实说到这里会觉得所谓的键值组也并没有什么格外的奇妙，还不就是个储存结构，其实也确实是这样，数组就可以说是一种最普通的键值组，其key就是每个数组元素的数组中的编号（从0开始），而所谓的值，就是数组中的每个具有不同数据格式的元素。

但是如果是换个方式呢？

好比说，如果是给你一连串的字符串和数值对应，偏偏那个字符串才是你需要识别并且进行相应的访问的“键”，那又该怎么办呢？

比如说，如果天王盖地虎对应2，一行白鹭上青天就是7……

首先我们会发现一个问题，那就是个中元素的对应关系其实是很无理的，凭空的一个字符串凭什么定义一个数值的值，但是考虑到人们在申请数组的时候也从来没有设身处地地想一想数组的感受，这似乎也是可以接受的。

接下来是最为蛋疼的一点。

我们似乎还没有见过a[天王盖地虎]，或者是b->一行白鹭上青天，这样的结构。

这也是最关键的——采用随意定义（实际上键值组的概念范围要比数组来得广泛……吧？）的键值组是不能以规范的形式在程序和内存空间中存储的，原因就是他们无法形成有效的索引，学习了两个月的数据结构之后，我所熟悉的东西，说白了就是线性表和链表，两者本质上都是经由一定的索引方式指向空间的对应方法。

重点：

直接且几乎不需要时间复杂度的访问对于c++来说，只有且只能通过指针和指针的直接索引（数组下标）实现，其他的储存方式，说白了其实也就只是对于这两种形式所代表的体系设定的开发和延伸而已。

那么现在的问题就很简单了，既然键值组（字典对）是无法通过直接的索引实现的，就必须寻求一种方法，能够实现类似于“天王盖地虎——a[1]——2”的关联。

映射

当然了，如果理想的话，最好是对于我们所能想到的每一个字符串，都有一个唯一的数字对应，这个唯一的意思，不仅是某个字符串能够确定出一个数字，同时也代表着一个数字是只有一个字符串才可以使用的，从离散数学的角度上来说，这是寻找一个双射函数的问题。

说来简单，其实并没有这么容易，所谓的字典对并不就是字典那么简单而已，而事实上，字典对这个名字的由来，以及为什么这个储存的形式被命名为字典对，本身就是一个值得思考的问题。

什么是字典对？字典对是键值组的另一个名字，键值组就有键和值两种属性，字典对的键是什么？

一开始我以为，就像是一本字典中的无数词语，他们本身就是字典的值，而他们的排列顺序就是键，但是这种思想实际上是错误的，事实上，键值组的访问一定是直接的，也就是说，当你能够给出一个字典的字母组合的时候，实际上他应该处于哪个地方你就已经确定了，如果我要找一个x打头的词语，我必定不可能从字典最后面的地方开始找。

所以说到这里应该很明确了，所谓的字典对，以我们所熟悉的字典来举例，其实其键就是字母排列的顺序，而值，则应该是对应词语的另一种语言中的表达、注释、语法等，所谓的在哪一页那个地方，其实应该对应于数组的储存格式。

那么字典的排序实际上非常清楚了，字母本身是没有顺序的，但是我们却有一种能够将26个字母映射到对应的数字顺序的方法，所以你看见的无数个字母组合出来的单词序列，其实本身就是个26尽职的大数字。

但是更多的时候，你是不可能找到这样简单粗暴的方法的，别说26，100进制也不行。

好比说你们班上的学生有一百个，偏偏学号是十二位的，那么你要想建立一个毫无重复的对应那就至少需要一个十二位量级的数字，这显然是极大的浪费。

所以，我们必须找到一种映射的方法，这种方法使得我们能够将固有的键值转换为数组的数字序号，这还只是第一个要求，第二个要求是，这个转换必须是连续的，并且还不能将所有的数据过度冗余地聚集在一起。

模除的对应方法、处理和转换

想到这里，其实一个转换的方法已经是很显然的了，是的，就是模除。

说起来我还想起在我第一次看见群里有人发%%%这个符号的时候，还不知道这是膜拜的意思……

将所有的信息用一个统一的数字进行模除（事实上，这个数字就是给定的数组的默认容量），在进行模除之后，就得到了每一个键值组的对应的映射的关系。

之后，在这个数组之中，我们主要实现的有三个操作，分别是插入，删除，寻找。

其中插入比较简单，先进行计算，计算之后进行数组的定位和元素的改变，如果元素已经存在，那么就有两种选择，一种是直接覆盖，一种是存储在之后的非空位置。

寻找是一样的道理，通过数组元素直接的索引来确定对应的位置。

而删除就有说辞了，在删除之后，必须考虑删除元素之后在原位置所造成的隔断是否会对新元素的继续检索造成困难，好比说，如果是若干个能被三整除的数字排在一起，那么将第一个删除之后必定会造成后面的元素无法检索，这里通过设定一个neveruse的变量来记录一个元素是否是被使用过的，如果有，那么即便他已经变成0，检索也要继续进行。

链式散列表

没有什么问题是散列表不能解决的，如果有，就用一个链式散列。

所谓的链式散列其实也很简单，就是将一个元素所对应的储存空间变成能够使用链表来扩充，只不过这也就相当于默认了字典对的不特殊性，即一个索引可以对应多个值，从数学的角度来说，一对多的映射未免有些捞。

总结

但是学习了字典对和散列表的相关概念之后，检查的精准和时空的节省是不能兼得的，这一点我已经是比较清楚了，所以，当程序不需也很难设计得十分精准的时候，不妨就用一些简单粗暴的方式实现，有的时候，框架带来的便利确实胜过细小的慎微。