前言
博客编写人：Willam 博客编写时间：2017/3/29 博主邮箱：2930526477@qq.com（有志同道合之人，可以加qq交流交流编程心得）哈希表的代码实现
我之前介绍两种方向的查找算法：
静态查找算法（折半查找、插值查找、斐波那契查找、分块查找）动态查找算法（二叉排序树、平衡二叉树、B-树、B+树）但是，这些查找算法都是通过从表头开始，挨个挨个的比较记录，才得到我们需要查找的关键字的内存存储位置，然后我们现在就想是否可以直接通过关键字key就可以得到我们的内存地址了？这个肯定是有的，那就是今天我们要介绍的哈希表查找。
哈希表查找过程中，我们是通过记录存储位置和关键字构建一个确定的关系f，使得每个关键字key对应一个存储位置f（key），我们称这个为散列技术。其中，这个f我们称为散列函数或者哈希函数。
通过散列技术将记录存储在一块连续的存储空间中，这块连续的空间称为散列表或者哈希表。
哈希表最适合查找与给定的值相等的记录。但是比如如果我们需要在一个十几个同学的哈希表中，查找某个同学，如果使用关键字“男”去查找，你会发现会出现很多条记录，无法达到我们的要求。 另外，我们需要查找一个班级18~28岁之间的同学，也是无法使用哈希表查找完成的，想要对记录进行排序，也是不可行的。.
思考二：哈希函数计算某两个关键字的值相等，咋办？ 其实，这个问题也是我们在建立哈希表时，需要解决的一个最大的问题，我们称这个问题为：冲突，就是两个关键字通过哈希函数得到的存储地址是一样的，这个时候，我们就需要通过冲突解决办法，来解决冲突，在解决冲突的同时也要保证我们的查找和插入效率问题，这个我们在后面会一一介绍。同时为了避免冲突，我们的散列函数也是很重要的，下面我们就介绍几种散列函数的构造方法其实就是直接通过取关键的字的某个线性值作为散列地址：
f(key)=a*key+b,(a,b为常数)例如：我们要存储0-100岁的人口统计表，就可以采用散列函数为：
f(key)=key 数字分析法 假设某公司的员工登记表以员工的手机号作为关键字。手机号一共11位。前3位是接入号，对应不同运营商 的子品牌；中间4位表示归属地；最后4位是用户号。不同手机号前7位相同的可能性很大，所以可以选择后4 位作为散列地址，或者对后4位反转（1234 -> 4321）、循环右移（1234 -> 4123）、循环左移等等之后作 为散列地址。数字分析法通常适合处理关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布比较 均匀，就可以考虑这个方法。
平方取中法 假设关键字是1234，平方之后是1522756，再抽取中间3位227，用作散列地址。平方取中法比较适合于不 知道关键字的分布，而位数又不是很大的情况。
折叠法 将关键字从左到右分割成位数相等的几部分，最后一部分位数不够时可以短些，然后将这几部分叠加求和， 并按散列表表长，取后几位作为散列地址。
比如关键字是9876543210，散列表表长是3位，将其分为四组，然后叠加求和：987 + 654 + 321 + 0 = 1962，取后3位962作为散列地址。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
除留取余数法 此方法为最常用的构造散列函数方法。 f(key) = key mod p (p≤m)，m为散列表长。这种方法不仅可以对关键字直接取模，也可在折叠、平方取中 后再取模。根据经验，若散列表表长为m，通常p为小于或等于表长（最好接近m）的最小质数，可以更好的 减小冲突。
随机数法 f(key) = random(key)，这里random是随机函数。当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。
选取散列函数的参考：
1. 计算散列地址所需的时间； 2. 关键字长度； 3. 散列表大小； 4. 关键字的分布情况； 5. 查找记录的频率。OK，到这里我们已经知道构造散列函数的方法，下面我们就要介绍如何处理冲突这个问题了。
开放地址就是一旦发生冲突，就去寻找下一个空的散列地址，只有散列表足够大，空的散列地址总能找到，并且记录它。至于如何寻找下一个空的散列地址，有三种方法：
1. 线性探测法公式如下：
f(key)=(f(key)+d)%m ,其中d取（0，1,2,3,4.....，m-1），m为散列表的长度如上图所示，散列表的长度为12，而且我们现在已经插入了部分数据了，下面我们继续插入37,。然后，我们使用散列函数计算37的散列地址：
f(37)=f(37)=1但是我们发现1这个位置已经存放了35，那么我们就继续寻找下一个空的散列地址。
f(37)=（f(37)+1）=2发现2这个地址没有内容，所以把37插入到这个位置，得如下图的结果：
线性探测来解决冲突问题，会造成冲突堆积。所谓的冲突堆积就是比如说刚才的37，它本来是属于下标1的元素，现在却占用了下标为2的空间，这会造成待会我们需要存放本来要放在下标为2的元素时，再次发生冲突，这个冲突会一直传播下去，造成查找和插入效率都大大减低。
2 .二次探测法公式如下：
f（key）=（f(key)+d）%m, ,其中d取（0^2，1^2,-1^2,2^2,-2^2,3^2,-3^2,4^2,-4^2...,q^2,-q^2），q<=m/2,m为散列表的长度其实，这个是对线性探测的一个优化，增加了平方可以不让关键字聚集在某一块区域
例如，我们对刚才的那个散列表，插入一个元素：7，通过二次探测的散列函数计算得到的散列地址为：
f(7)=f(7)=7但是，我发现下标为7的位置已经存放了元素：67，所以我需要寻找下一个存储地址：
f(7)=（f(7)+1^2）=8哎呀，突然发现下标为8的地址也存放了56这个元素，所以我们只能继续往下寻找下一个存储地址：
f(7)=（f(7)+（-1^2））=6嗯，发现下标为6的这个地址空间还是空的，所以我就把7插入到这个位置，得到如下结果：
3.随机探测法公式：
f（key）=（f(key)+d）%m, d为随机数列，而m为表长在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避 免或减少堆聚。
再散列函数法（多重散列法）公式如下：
f（key）=RH（key）,其中RH就是不同的散列函数，这些散列函数可以是我们介绍的所有散列函数，只要其中一个发生了冲突，就马上换一个散列函数，知道冲突解决。缺点就是增加了很多计算时间
链地址法所谓的链地址法，其实就是当发生冲突时，我还是把它存放在当前的位置，只是每个位置都是使用链表来存放同义词，这个思路和图的邻接表存储方式很相似。如下图所示：
公共溢出区法 所谓的公共溢出区法，其实就是把那些冲突的元素直接追加到另外一个溢出表中，如下图所示：所以，我们在查找的时候，如果在基本表没哟找到，那么就只能去溢出表中进行顺序查找。这个方法比较适合冲突元素少的情况。
总结： 刚刚我们介绍了，几种冲突的解决办法，在实际的应用中，我们需要根据实际的情况，选择合适的冲突解决办法。
哈希表的代码实现
