Hi~ o( ￣▽￣)ブ
本篇博客分为上下两部分，上半部分主要讲解哈希表的基础知识，下半部分主要是功能代码实现。 φ(≧ω≦*)♪
什么是哈希表
哈希，就是把任意长度的输入通过散列算法变换成固定长度的输出。
哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。
通俗理解的说，就是通过一个函数算法，把需要存储的东西经过这个算法转化成一个更简单的东西（关键码值），然后将这个关键码值作为所存储东西的地址，直接通过地址进行查找，简化了查找算法。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
既然哈希表的核心，就是一个函数，那么，我们就可以通过研究函数的性质来研究哈希表。
︿(￣︶￣)︿
不可逆性
首先来看一个简单的函数：
f(key)=a+b
假如有两个密码3和4，我的加密算法很简单就是3+4，结果是7，
但是通过7我不可能确定那两个密码是3和4，因为有很多种组合。
除非暴力破解。 Σ( ° △ °|||)︴
这就是哈希算法的不可逆性
既然提到了密码，我们就举一个哈希算法在密码学中的应用。
我们登陆知乎的时候都需要输入密码，那么知乎如果明文保存这个密码，那么黑客就很容易窃取大家的密码来登陆，特别不安全。那么知乎就想到了一个方法，使用hash算法生成一个密码的签名，知乎后台只保存这个签名值。由于hash算法是不可逆的，那么黑客即便得到这个签名，也很难计算出原始密码，丝毫没有用处；而如果你在网站登陆界面上输入你的密码，那么知乎后台就会根据加密算法重新计算一下这个hash值，与网站中储存的原hash值进行比对，如果相同，证明你拥有这个账户的密码，那么就会允许你登陆。银行也是如此，银行是万万不敢保存用户密码的原文的，只会保存密码的hash值而已。
“碰撞”现象
那么我们知道，函数一定是映射,但不一定是一一映射,一一映射是一对一的关系 。
函数 eg:y=x^2
x一定唯一对应y值，但y值可能对应多个x值。
同理，对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象被称为碰撞。
由于哈希函数是一个压缩映象，因此，在一 般情况下，很容易产生“碰撞”现象，
那么我们如果希望用哈希表进行查找，即想通过关键字来找到存储位置：那么这个哈希算法当然是一一对应的越多越好。
ლ(•̀ _ •́ ლ)
所以，一个优秀的 hash 算法，将能实现：
正向快速：给定明文和 hash 算法，在有限时间和有限资源内能计算出 hash 值。
逆向困难：给定（若干） hash 值，在有限时间内很难（基本不可能）逆推出明文。
输入敏感：原始输入信息修改一点信息，产生的 hash 值看起来应该都有很大不同。
冲突避免：很难找到两段内容不同的明文，使得它们的 hash 值一致（发生冲突）。即 对于任意两个不同的数据块，其hash值相同的可能性极小；对于一个给定的数据块，找到和它hash值相同的数据块极为困难。
如何构造一个哈希算法：
哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。
所以，使用哈希查找有两个步骤:
1.使用哈希函数将被查找的键转换为数组的索引。（构造哈希函数的方法）
在理想的情况下，不同的键会被转换为不同的索引值，但是在有些情况下我们需要处理多个键被哈希到同一个索引值的情况。所以需要第二步。
2.处理哈希碰撞冲突。
构造哈希函数的方法
对数字的关键字可有下列构造方法：
- 直接定址法2. 数字分析法3. 平方取中法4. 折叠法5. 除留余数法6. 随机数法
若是非数字关键字，则需先对其进行数字化处理
1.直接定址法:
哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a ´ key + b
此法仅适合于：地址集合的大小 = = 关键字集合的大小这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数。
实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。
- 数字分析法:
假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。
此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度
- 平方取中法 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。
此方法适合于: 关键字中的每一位都有某些 数字重复出现频度很高的现象。
- 折叠法将关键字分割成若干部分，然后取它们的叠加和为哈希地址。
有两种叠加处理的方法：移位叠加和间界叠加。
移位叠加:将分 割后的几部分低位对齐相加；
边界叠加:从一端沿分割界来回折叠，然后对齐相加。
此方法适合于: 关键字的数字位数特别多。
- 除留余数法设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子.
理论研究表明，除留余数法的模p取不大于表长且最接近表长m素数时效果最好，且p最好取1.1n～1.7n之间的一个素数（n为存在的数据元素个数）。例如：当n=7时，p最好取11、13等素数。- 随机数法 设定哈希函数为: H(key) = Random(key)其中，Random 为伪随机函数
实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。 ( ˘•ω•˘ )ง⁽˙³˙⁾
处理冲突的方法:
1.开放定址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
Hi=（H（key）+di）% m i=1，2，…，n
其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：
A.线性探测法：
将散列表T[0…m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
（1）插入元素：插入元素时，如果发生冲突，算法将从该槽位向后遍历哈希表，直到找到表中的下一个空槽，并将该值放入到空槽当中。
（2）查找元素：查找元素时，首先散列值所指向的槽，如果没有找到匹配，则继续从该槽向后遍历哈希表，直到：1）找到相应的元素；2）找到一个空槽（指示查找的元素不存在）；3）整个哈希表都遍历完毕（指示该元素不存在并且哈希表已满）
线性探测法存在的缺点：
（1）处理溢出需要另编程序。一般可以设立一个溢出表，用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找；
（2）删除工作很复杂。因为一旦对某一个元素删除后，该位置出现空槽，后续查找到该空槽时会认为该元素不存在。需要一种方法对删除元素进行标记；
（3）由于每次都是线性递增，容易导致堆聚，即存入哈希表的记录在表中都连成一片，后续发生冲突的可能性会越大。
B.二次探测再散列
di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )
这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活，不易产生聚集。
缺点是不能探查到整个散列空间。
C.伪随机探测再散列
di=伪随机数序列。
具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。
2.链地址法
也称为拉链法。其基本思路为：将所有具有相同哈希地址的而不同关键字的元素连接到同一个单链表中。如果选定的哈希表长度为m，则可以将哈希表定义为一个有m个头指针组成的指针数组。凡是给定哈希地址为i的元素，均以节点的形式插入到下标为i的头指针单链表中。并且最新的元素插入到链表的前端，这不仅因为方便，还因为一个经常发生的事实是：最新插入的元素最有可能不久又被访问。
拉链法的优点:
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
拉链法的缺点：
指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
哈希表的基础部分就到这里啦~~
初学者，如果有错误敬请指出。 ヽ(✿ﾟ▽ﾟ)ノ